Binary tree traversals

Binary tree traversals are methods for visiting all the nodes in a binary tree in a specific order. There are several types of traversals, each serving different purposes.

There are three ways which we use to traverse a tree

Let's go through each of these traversals step by step:

1. In-Order Traversal

In an in-order traversal, the nodes are traversed in a left-root-right order. This means that for any given node, you first visit its left subtree, then the node itself, and finally its right subtree.

In-Order Traversal Recursion and Non Recursion Algorithm

• Traverse the left subtree in an in-order manner.
• Visit the current node (e.g., print the node's data).
• Traverse the right subtree in an in-order manner.

Use Case: In a Binary Search Tree (BST), an in-order traversal retrieves the nodes in sorted order.

inorder (root)
    if root ≠ NULL, then
        inorder(root->left)
        Print root → info
        inorder(root->right)

inorder (root)
1. If root = NULL, then print "Empty tree" and exit.
2. top = -1		//Initialize stack top]
3. ptr = root.  //Initialize ptr with root of the binary tree]
4. Repeat step 5, while stack is not empty or ptr ≠  NULL 	//Pushes left-most path onto stack]
5. If ptr ≠  NULL, then
	a. Push(ptr)		//[Push current node address onto stack]
	b. ptr = ptr>left	//Move ptr to left subtree]
Else:
	C. ptr = popl		//[Pop from stack, stored address and assign it to ptr
	d. Print ptr → info	//Print node data]
	e. ptr = ptr→right	//Move ptr to right subtree]
6. Exit	

2. Pre-Order Traversal

In a pre-order traversal, the nodes are traversed in a root-left-right order. This means that you visit the node first, then its left subtree, and finally its right subtree.

Pre-Order Traversal Recursion and Non Recursion Algorithm

• Visit the current node (e.g., print the node's data).
• Traverse the left subtree in a pre-order manner.
• Traverse the right subtree in a pre-order manner.

Use Case: Pre-order traversal is useful for creating a copy of the tree or for prefix notation expressions.

preorder (root)
    if root ≠ NULL, then
        Print root → info
        preorder(root->left)
        preorder(root->right)

preorder (root)
1. If root = NULL, then print "Empty tree" and exit.
2. top = -1	//[Initialize stack top]
3. Push(root)	//[Push root address onto stack]
4. ptr = root.	//[Initialize ptr with root of the binary tree]
5. Repeat steps 6 and 7, while stack is not empty
6. ptr = pop)	//[Get stored address and assign to ptr]
7. If ptr ≠ NULL, then
	(a) Print ptr→info	//[Print node info]
	(b) Push(ptr>right)	//[Store address of right subtree]
	(c) Push(ptr>left)	//[ Store address of left subtree]
8. Exit	

3. Post-Order Traversal

In post-order traversal, the nodes are traversed in a left-right-root order. Here, you first visit the left and right subtrees and then the node itself.

Post-Order Traversal Recursion and Non Recursion Algorithm

• Traverse the left subtree in a post-order manner.
• Traverse the right subtree in a post-order manner.
• Visit the current node (e.g., print the node's data).

Use Case: Post-order traversal is used in deleting the tree or in postfix notation expressions.

postorder (root)
    if root ≠ NULL, then
        postorder(root->left)
        postorder(root->right)
        Print root → info 

postorder (root)
1. If root = NULL, then print "Empty tree" and exit.
2. top = -1		//[Initialize stack topl
3. ptr = root.		//[Initialize ptr with root of the binary tree]
4. tmp = NULL		//[Initialize pointer variable, tmp to NULL]
5. Repeat steps 6 thru 8, while ptr> left ≠ NULL
6. Push (ptr)
7. ptr = ptr>left
8. Repeat steps a and b, while ptr ≠ NULL
	a. If ptr>right = NULL or ptr>right = tmp
		i.   Print ptr> info
		ii.  tmp = ptr
		iii. ptr = popl
	b. Else:
		i. Push(ptr)
		ii. ptr = ptr>right
		iii. Repeat steps (a) and (b), while ptr> left ≠ NULL
			(a) Push(ptr)
			(b) ptr = ptr->left
9. Exit    

Example tree traversals

Consider a tree with the structure:

    A
   / \
  B   C
 / \   \
D   E   F 

• In-Order: D, B, E, A, C, F
• Pre-Order: A, B, D, E, C, F
• Post-Order: D, E, B, F, C, A

Each traversal serves different purposes and offers a unique view of the elements in the binary tree.

Construction of a Binary Tree from its Traversals

It is sometimes necessary to construct (or reconstruct) a binary tree from its traversals. We require a minimum of two traversals to construct a unique binary tree. We need one of these two combinations:

1. inorder traversal and preorder traversal, or
2. inorder traversal and postorder traversal.

1. If the preorder traversal is given, then the first node in the linear order is the root node. If the postorder traversal is given, then the last node is the root node.
2. Once the root node is known, the nodes in the left subtree and the right subtree are established by using inorder sequence.
3. The above two steps are repeated to form subtrees and finally the required binary tree.