**Traversals in Binary tree**

- The traversal operation is frquently used operation on a binary tree.
- This operation is used to visit each node in the tree exactly once.
__There are 6(six) possible ways a tree can be traversed and they are as follows:__

- R T
_{L } T_{Y } _{}T_{L }R T_{R}- T
_{L} T_{R } R_{} - T
_{R} T_{L} R - T
_{R} R_{ } T_{L} - R T
_{R} T_{L}

*where, *T_{L} is left sub-treesof the node R.

T_{R} is right sub-trees of the node R.

__Out of these six possible traversals, only three are fundamental , they are categorized as given below:__

- R T
_{L } T_{R } (preorder) - T
_{L} R T_{R} (inorder) - T
_{L} T_{R} R (post order)

__Example:__

__Inorder__

1) The given binary tree is

Find out the inorder, preorder and postorder traversals.

__Solution:__

__Inorder:__Left root right

Step:1 LC **A **RC

Step:2 _**B**_**A** RC

Step:3 D**B**HE**A**RC

Step:4 DBHE**A**_C_

Step:5 DBHE**A**IFJ**C**G

Step:6 DBHEAIFJCG

**Algorithm**

- ptr=ROOT
- if(ptr≠NULL) then
- inorder(ptr→LC)
- visit(ROOT)
- inorder(ptr→RC)
- end if
- stop

__Preoder:__Root LC RC

Step:1 **A** LC RC

Step:2 **A **B_ C _

Step:3 **A**BDEH **C**FIJG

Step:4 **A**BDEH**C**FIJG

Step:5 ABDEHCFIJG

**Algorithm**

- ptr=ROOT
- if(ptr≠NULL) then
- visit(ROOT)
- preorder(ptr→LC)
- preorder(ptr→RC)
- end if
- stop

__Postorder __:__ __LC RC Root

Step:1 LC RC **A**

Step:2 DHE**B **IJEG**C** **A**

Step:3 DHEBIJEGC**A**

Step:4 DHEBIJEGCA

**Algorithm**

- ptr=ROOT
- if (ptr≠NULL) then
- postorder(ptr→LC)
- postorder(ptr→RC)
- visit(ROOT)
- end if
- stop

**2**) To construct inorder, preoder and post order traversals for below binary tree:

__Solution:__

__Inorder:__ left root right

Step:1 LC **n**_{6}_{ }RC

Step:2 n_{1} n_{2} n_{3} n_{4 }n_{5} **n**_{6} n_{7 }n_{8 }n_{9}

Step:3 n_{1} n_{2} n_{3} n_{4} n_{5 } n_{6} n_{7 }n_{8 }n_{9}

__Preoder__: Root LC RC

Step:1 **n**_{6} LC RC

Step:2 **n**_{6} n_{2} n_{1} n_{4} n_{3} n_{5 }**n**_{9}_{ }n_{7 }n_{8 }_{ }

Step:3 **n**_{6} n_{2} n_{1 }n_{4} n_{3} n_{5 }n_{9} n_{7 }n_{8}_{}

__Postorder__:LC RC root

Step1: LC RC **n**_{6}

Step:2 n_{1 }n_{3} n_{5} n_{4} n_{2 }n_{8 }n_{7 }n_{9 }**n**_{6}

Step:3 n_{1} n_{3} n_{5} n_{4} n_{2} n_{8} n_{7 }n_{9 }n_{6}

**Formation of Binary tree from its traversals**

- From a single traversal, it is not possible to construct a unqiue binary tree.
- But, if two traversals are known then, we can construct a unique binary tree.
- Out of two traversals, one should be inorder traversal and another preorder or postorder.
- If the two traversals are preorder and postorder then, a binary tree cannot be constructed uniquely.

__Example 1:__

Construct the binary tree from the inorder and preorder traversals of a binary tree as given below:

*Inorder:*D B H E A I F J C G

*Preoder:*A B D E H C F I J G

**Solution**:

The following steps need to be followed:

- From the preoder traversal, it is evident that
**A** is the root node. - In inorder traversal, all the nodes which are on the left side of
**A **belong to the left sub tree and those which are on right side of **A** belong to the right subtree. - Now the problem reduces to form subtreees and the same procedure can be applied repeatedly.

__Step:1__

__Step:2__

(i) In left subtree , B will be the root(**B **D E H)

(ii) In right subtree, C will be the root(**C** F I J G)

__Step:3__

(i) In right subtree of B, E is the root from the preoder **E** H.

From inorder, H will be left subtree of E.

(ii) From left subtree of C, F is the root from the preorder **F** I J

From inorder, I is left of F and J is right of **F**. So,

So, the final binary tree from inorder and preorder is

__Example:2__

Construct a binary tree from the inorder and postorder traversals given below:

__Inorder:__ n_{1} n_{2 } n_{3 }n_{4} n_{5 }n_{6 }n_{7 }n_{8 }n_{9}

__Postorder:__ n_{1} n_{3} n_{5 } n_{4} n_{2} n_{8} n_{7} n_{9} n_{6}

__Solution__:

__Step:1__

n_{6} is the root from postorder.

**Left subtree: **^{ }n_{1 }n_{2} n_{3 }n_{4 }n_{5}

**Right subtree: **n_{7} n_{8 } n_{9 }

__Step:2__

From postorder : n_{2} is the root of left subtree.

From postorder: n_{9} is the root for right subtree.

__Step:3__

n_{4} is the root of n_{2} right subtree.

n_{7} is the root of n_{9} left subtree.

**Merging two binary trees together**

- Merge operation is applicable to trees which are reprsented by using a linked structure .
- There are two ways that this operation can be carried out.

__Approach 1:__

Suppose T_{1} and T_{2} are two binary trees. T_{2} can be merged with T_{1} if all the nodes from T_{2}, one by one , are inserted into the binary tree T_{1}

__Approach 2:__

When the entire tree T_{2} can be include as a subtree of T_{1} To achieve this, we need that in either tree . There must be atleast one null subtree.

(i) Before performing merging, we have to test for compatibility. If in both trees the root node has both the left and right subtrees, then the merge will be fail.

(ii) If T_{1} has left subtree(right subtree) empty. Then T_{2} will be added to the left subtree(the right subtree) of the T_{1} and vice-versa.

(iii) If T_{1} is a tree with n_{1} nodes and T_{2} is a tree with n_{2} nodes. Then the resultant tree T after merging is

T(n_{1}+n_{2}) =T_{1}(n_{1}) +T_{2}(n_{2})

__If the binary tree contains an arithmetic expression, __

Then ,its

- Inorder will give infix expression
- Preorder will give prefix expression
- Postorder will give postfix expression.