Inorder Traversal of binary trees

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,in order traversal has a priority order (left tree, root, right tree) ,in the above tree node D’s left subtree is completed so next is itself root node D then right subtree 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, the left-sub tree is inordered and now node B will be accessed next right subtree 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,because node E has no child nodes. from node B , search pointer moves to the node A , because inorder operations are already performed on the node B, now node A will be the root node, this root node will be accessed

Inorder Traversal of binary trees 8

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

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 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

Default image
Vishal Devxo
Vishal Devxo is a DevOps engineer and a Backend developer, he spends all his time for creating good tutorials with better visuals and blogging, developed some projects based on Python-Django, some hacking modules and scripts in python