Can you do Iterative Pre-order Traversal of a Binary Tree without Recursion?

Yes, it is possible to perform an iterative pre-order traversal of a binary tree without using recursion. You can use a stack to simulate the recursive call stack and traverse the tree in a pre-order manner. Here’s an example implementation in C#:

using System;
using System.Collections.Generic;

public class TreeNode
{
    public int Value { get; set; }
    public TreeNode Left { get; set; }
    public TreeNode Right { get; set; }
}

public class BinaryTree
{
    public TreeNode Root { get; set; }

    public void PreOrderTraversal()
    {
        if (Root == null)
            return;

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(Root);

        while (stack.Count > 0)
        {
            TreeNode node = stack.Pop();
            Console.Write(node.Value + " ");

            // Push the right child first to ensure left child is processed first (pre-order)
            if (node.Right != null)
                stack.Push(node.Right);
            if (node.Left != null)
                stack.Push(node.Left);
        }
    }
}

// Usage
BinaryTree tree = new BinaryTree();
tree.Root = new TreeNode { Value = 1 };
tree.Root.Left = new TreeNode { Value = 2 };
tree.Root.Right = new TreeNode { Value = 3 };
tree.Root.Left.Left = new TreeNode { Value = 4 };
tree.Root.Left.Right = new TreeNode { Value = 5 };

tree.PreOrderTraversal();

The above code performs an iterative pre-order traversal of a binary tree. It uses a stack to keep track of nodes to be processed. Here’s how it works:

  1. Create an empty stack and push the root node onto the stack.
  2. While the stack is not empty, do the following:
    • Pop a node from the stack and process it (print the value or perform any desired operation).
    • Push the right child onto the stack (if it exists) before the left child (to maintain the pre-order traversal order).
  3. Repeat step 2 until all nodes are processed.

In the above example, the pre-order traversal will print: 1 2 4 5 3, which is the pre-order traversal sequence of the binary tree.

By using an iterative approach with a stack, you can traverse a binary tree in a pre-order manner without recursion, which can be useful in scenarios where recursive function calls are not desirable or efficient.

error: Content is protected !!