Binary tree inorder traversal without recursion

We have seen inorder traversal algorithm for a binary tree, but it was a recursive version. In this article, we'll take a look at the non-recursive approach

The inorder binary tree traversal algorithm can be described:

• Visit the left subtree
• Visit the root
• Visit the right-subtree

During inorder traversal, nodes will be printed in the following order: 5, 4, 7, 2, 3, 8. The animated image displays the inorder traversal algorithm.

Algorithm

To implement inorder traversal without recursive we will use Stack to store the traversal

• Step 1: Create an empty stack
• Step 2: Set current node as root
• Step 3: Push the current node to the stack and set current = current.Left until the current is null
• Step 4: If the current is null and the stack is not empty then:
  • Pop a node from the stack
  • Print the poppedNode, set current = poppedNode.Right
  • Go to step 3
• Step 5: If the current is null and stack is empty then the traversal completed

let's see step by step how the algorithm works on the example

• Step 1: create an empty stack
• Step 2: set current node as root
• Step 3: push the current node to the stack and set current = current.Left until the current is null
  • current = 2
  • push 2 to the stack (Stack: 2)
  • current = 4
  • push 4 to the stack (Stack: 4, 2)
  • current = 5
  • push 5 to the stack (Stack: 5, 4, 2)
  • current = null
• Step 4: pop 5 from the stack
  • pop 5 from the stack (Stack: 4, 2)
  • print 5
  • current = null. node 5 is a leaf it doesn't have a right child
  • goto Step 3
• Step 3: do nothing, because current equals null
• Step 4: pop 4 from the stack
  • pop 4 from the stack (Stack: 2)
  • print 4 (Output: 5, 4)
  • current = 7
  • goto Step 3
• Step 3: push 7 to the stack
  • push 7 to the stack (Stack: 7, 2)
  • current = null, node 7 is a leaf it doesn't have a left child
  • goto Step 4
• Step 4: pop 7 from the stack
  • pop 7 from the stack (Stack: 2)
  • print 7 (Output: 5, 4, 7)
  • current = null, node 7 is a leaf it doesn't have a right child
  • goto Step 3
• Step 3: do nothing, because current equals null
• Step 4: pop 2 from the stack
  • pop 2 from the stack (Stack: empty)
  • print 2 (Output: 5, 4, 7, 2)
  • current = 3
  • goto Step 3
• Step 3: push 3 to the stack
  • push 3 to the stack (Stack: 3)
  • current = null, 3doesn't have a left node
  • goto Step 4
• Step 4: pop 3 from the stack
  • pop 3 from the stack (Stack: empty)
  • print 3 (Output: 5, 4, 7, 2, 3)
  • current = 8
  • goto Step 3
• Step 3: push 8 to the stack
  • push 8 to the stack (Stack: 8)
  • current = null, 8 doesn't have a left node
  • goto Step 4
• Step 4: pop 8 from the stack
  • pop 8 from the stack (Stack: empty)
  • print 8 (Output: 5, 4, 7, 2, 3, 8)
  • current = null

the traversal is completed: current equals null and the stack is empty

Code

    public void InorderTraversal(TreeNode root)
    {
        if (root == null)
        {
            return;
        }

        var stack = new Stack<TreeNode>();

        //TreeNode is a reference type, need this to do not break the tree.
        TreeNode current = root;
 
        while (current != null || stack.Count != 0)
        {
            while (current != null)
            {
                stack.Push(current);
                current = current.Left;
            }

            TreeNode poppedNode = stack.Pop();

            //print value
            Console.WriteLine(poppedNode.Value);

            current = poppedNode.Right;
        }
    }

Time Complexity: O(n)

Video Lesson