Inorder Traversal of binary trees

Last Updated on

To inorder a non-empty binary tree, below operations are preformed recursively of each node

  1. traversing the left subtree
  2. visiting root node
  3. traversing the right subtree
Inorder Traversal of binary trees 1

the word “in” specifies that the root node is accessed in the middle of both left and right subtrees

let’s see one example:

Inorder Traversal of binary trees 2

step1: in the above binary tree, node A is the root node and the left subtree root node B will be accessed first and next root node will be assessed, then last right subtree node C will be accessed

Inorder Traversal of binary trees 3

step 2:search goes on until a leaf node is detected and, here in the above example form node A, left subtree is node B, node b has left subtree node D, node D has left leaf node G, now node G will be accessed.

Inorder Traversal of binary trees 4

step 3:node G is the leaf node so,search pointer goes back to the node D which is the parent node of node G,here node D is the root node ,inorder traversal has a priority order (left tree,root, right tree) ,in the baove tree node D’s left subtree is completed so next is itself root node D then right sub tree root node H will be accessed

Inorder Traversal of binary trees 5

step 4:here the root node will be node H, now node H will be accessed this is a leaf node so, the search pointer will be back to its parent node D

Inorder Traversal of binary trees 6

step 5:search pointer will be transferred to the node D,node D has already done with the inorder traverse ,next search pointer will be moved to the node B,which is the parent node of node D, here in the above tree,node B is the root node ,left-sub tree is inordered and now node B will be accessed next right sub tree of node B is node E ,node E is a leaf node ,this leaf node will be accessed

Inorder Traversal of binary trees 7

step 6:search pointer will be moved from node E to its parent node B,beacuse node E has no child nodes.from node B ,search pointer moves to the node A ,because inorder oprartionsa aree already performed on the node B,now node A will be root node ,this root node will be accessed

Inorder Traversal of binary trees 8

step 7:when node C becomes root node ,first operation should be don eon the left sub tree ,search pointer will be moved to the node F as show in the above image,for node F there is no left sub tree but there is right sub tree which conatins a single leaf node I ,after accessing node F the pointer moves to the node I and this node will be accssed

Inorder Traversal of binary trees 9

step 8:search pointer will be moved back to the leaves parent node F,and node F’s inorder is completed so ,again the pointer moves to the node F’s parent node node C,as shown in the above diagram node C will be accessed and there is no right sub-tree for node C,now above binary tree is completely traversed in inorder method