loader image

Binary Tree Traversal Algorithm Without Recursion

In this tutorial, you will learn the implementation of different tree traversal algorithms, which were specified recursively in the last tutorial, by means of non-recursive procedures using stacks.

Pre-order Traversal Without Recursion

The following operations are performed to traverse a binary tree in pre-order using a stack:

  1. Start with root node and push onto stack.
  2. Repeat while the stack is not empty
    1. POP the top element (PTR) from the stack and process the node.
    2. PUSH the right child of PTR onto to stack.
    3. PUSH the left child of PTR onto to stack.

Consider the following tree.

pre order traversal using stack example 1 3

Start with node 4 and push it onto the stack.

pre order traversal using stack example 2 3

Since the stack is not empty, POP 4 from the stack, process it and PUSH its left(7) and right(18) child onto the stack.

pre order traversal using stack example 3 4

Repeat the same process since the stack is not empty. POP 7 from the stack, process it and PUSH its left(8) and right (13) child onto the stack.

pre order traversal using stack example 4 3

Again, POP 8 from the stack and process it. Since it has no right or left child we don’t have to PUSH anything to the stack.

pre order traversal using stack example 5 3

Now POP 13 from the stack and process it. We don’t have to PUSH anything to the stack because it also doesn’t have any subtrees.

pre order traversal using stack example 6 3

POP 18 from the stack, process it and PUSH its left(5) and right(2) child to the stack.

pre order traversal using stack example 7 3

Similarly POP 5 and 2 from the stack one after another. Since both these nodes don’t have any child, we don’t have to PUSH anything onto the stack.

pre order traversal using stack example 8 4
pre order traversal using stack example 9png 2

The nodes are processed in the order [ 4, 7, 8, 3, 18, 5, 2 ]. This is the required preorder traversal of the given tree.

The formal algorithm is given below:

1. Set TOP = 1. STACK[1] = NULL and PTR = ROOT.
2. Repeat Steps 3 to 5 while PTR ≠ NULL:
3.    Apply PROCESS to PTR->DATA.
4.    If PTR->RIGHT ≠ NULL, then:
‎        Set TOP = TOP + 1, and STACK[TOP] = PTR->RIGHT.
‎      [End of If]
5.    If PTR->LEFT ≠ NULL, then:
‎         Set PTR = PTR -> LEFT.
‎      Else:
‎         Set PTR = STACK[TOP] and TOP = TOP - 1.
‎      [End of If]
‎   [End of Step 2 loop.]
6. Exit.

In-order Traversal Without Recursion

The following operations are performed to traverse a binary tree in in-order using a stack:

  1. Start from the root, call it PTR.
  2. Push PTR onto stack if PTR is not NULL.
  3. Move to left of PTR and repeat step 2.
  4. If PTR is NULL and stack is not empty, then Pop element from stack and set as PTR.
  5. Process PTR and move to right of PTR , go to step 2.

Consider the following tree.

in order traversal using stack example 1

Start with node 4 and call it PTR. Since PTR is not NULL, PUSH it onto the stack.

in order traversal using stack example 2

Move to the left of node 4. Now PTR is node 7, which is not NULL. So PUSH it onto the stack.

in order traversal using stack example 3

Again, move to the left of node 7. Now PTR is node 8, which is not NULL. So PUSH it onto the stack.

in order traversal using stack example 4

When we move again to the left of node 8, PTR becomes NULL. So POP 8 from the stack. Process PTR (8).

in order traversal using stack example 5

Move to the right child of PTR(8), which is NULL. So POP 7 from the stack and process it. Now PTR points to 7.

in order traversal using stack example 6

Move to the right child(13) of PTR and PUSH it onto the stack.

in order traversal using stack example 7

Move to the left of node 13, which is NULL. So POP 13 from the stack and process it.

in order traversal using stack example 8 1

Since node 13 don’t have any right child, POP 4 from the stack and process it. Now PTR points to node 4.

in order traversal using stack example 9 1

Move to the right of node 4 and put it on to the stack. Now PTR points to node 18.

in order traversal using stack example 10

Move to the left(5) child of 18 and put it onto the stack. Now PTR points to node 5.

in order traversal using stack example 11

Move to the left of node 5, which is NULL. So POP 5 from the stack and process it.

in order traversal using stack example 12

Now, move to the right of node 5, which is NULL. So POP 18 from the stack and process it.

in order traversal using stack example 13 1

Move to the right(2) of node 18 and PUSH it on to the stack.

in order traversal using stack example 14 1

Since node 2 has left child, POP 2 from the stack and process it. Now the stack is empty and node 2 has no right child. So stop traversing.

in order traversal using stack example 15

The nodes are processed in the order [ 8, 7, 13, 4, 5, 18, 2 ] . This is the required in order traversal of the given tree.

The formal algorithm is given below:

1. Set TOP = 1, STACK[1] = NULL and PTR = ROOT.
2. Repeat while PTR ≠ NULL:
‎      (a) Set TOP = TOP + 1 and STACK[TOP] = PTR.
‎      (b) Set PTR = PTR->LEFT.
‎   [End of loop.]
3. Set PTR = STACK[TOP] and TOP = TOP - 1.
4. Repeat Steps 5 to 7 while PTR ≠ NULL:
5.    Apply PROCESS to PTR->INFO.
6.    If PTR->RIGHT ≠ NULL, then:
‎         (a) Set PTR = PTR->RIGHT.
‎         (b) Go to Step 3.
‎      [End of If]
7. Set PTR = STACK[TOP] and TOP = TOP -1.
‎   [End of Step 4 loop.]
8. Exit.

Post-order Traversal Without Recursion

The post order traversal algorithm is more difficult to implement than the previous two algorithms. The following operations are performed to traverse a binary tree in post-order using a stack:

  1. Start from the root, call it PTR.
  2. Push PTR onto stack if PTR is not NULL.
  3. Move to left of PTR and repeat step 2.
  4. If PTR has a right child R, then PUSH -R onto the stack.
  5. Pop and process positive element from stack and set as PTR.
  6. If a negative node is popped, (PTR = -N), then set PTR = N and go to step 2.

The formal algorithm is given below:

1. Set TOP = 1. STACK[1] = NULL and PTR = ROOT.
2. Repeat Steps 3 to 5 while PTR ≠ NULL:
3.    Set TOP = TOP + 1 and STACK[TOP] = PTR.
4.    If PTR->RIGHT ≠ NULL. then: [Push on STACK. ]
‎         Set TOP = TOP + 1 and STACK[TOP] = PTR->-RIGHT.
‎      [End of If structure.]
5.    Set PTR = PTR->LEFT. [Updates pointer PTR.]
‎   [End of Step 2 loop.]
6. Set PTR = STACK[TOP] and TOP = TOP - 1.
7. Repeat while PTR > 0:
‎      (a) Apply PROCESS to PTR->INFO.
‎      (b) Set PTR = STACK[TOP] and TOP = TOP - 1.
‎   [End of loop.]
8. If PTR < 0, then:
‎      (a) Set PTR = -PTR.
‎      (b) Go to Step 2.
‎   [End of If structure]
9. Exit.
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments