Binary tree preorder traversal without recursion

We have seen preorder traversal algorithm for a binary tree, but it was a recursive version. In this article, we'll take a look at the iterative implementation.

The preorder binary tree traversal algorithm can be described:

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

 

 

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

 

Algorithm

To implement preorder 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: If the current is not null:
  • Push the current node to the stack
  • Print current
  • Set current = current.Left
• Step 4: If the current is null:
  • Pop a node from the stack
  • Set current = poppedNode.Right
  • Go to step 3
• Step 5: If the current is null and stack is empty then the traversal completed

Code

    public void PreorderTraversal(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)
        {
            if (current != null)
            {
                stack.Push(current);

                //print value
                Console.WriteLine(current.Value);
                current = current.Left;
            }
            else
            {
                TreeNode poppedNode = stack.Pop();
                current = poppedNode.Right;
            }
        }
    }

Time Complexity: O(n)