Tree Traversal Techniques

What is Tree Traversal?

Traversing a tree means visiting every node in the tree exactly once in a systematic way. For a binary tree, at any given node, we have three basic operations we can perform:

1. Process the current node (e.g., print its value). We'll call this 'Root'.
2. Traverse its left subtree. We'll call this 'Left'.
3. Traverse its right subtree. We'll call this 'Right'.

The order in which we perform these three operations gives us our main traversal types:

• Preorder: Root -> Left -> Right
• Inorder: Left -> Root -> Right
• Postorder: Left -> Right -> Root

Let's dive into how to implement these, starting with the most intuitive approach: recursion.

1. Recursive Traversals

The recursive nature of a tree (a tree is a root node with two children, which are themselves roots of smaller trees) lends itself beautifully to recursive algorithms. The logic of a recursive traversal function directly mirrors the definition of the traversal itself.

To get a clear overview of these recursive traversals, let's watch a short video.

As you saw in the video, the code for all three recursive traversals is strikingly similar, with only a single line moved. Let's look at the Java code for each.

First, here is a standard TreeNode class that we will use in our examples:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

Now, let's look at the implementation for each traversal, which you can find in the article "Mastering Binary Tree Traversal".

Preorder Traversal: Root -> Left -> Right

Use Case: Often used to create a copy of a tree, as you can create the root node before you recursively create its children.

public void preorderTraversal(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");  // 1. Visit root
    preorderTraversal(root.left);      // 2. Visit left subtree
    preorderTraversal(root.right);     // 3. Visit right subtree
}

Inorder Traversal: Left -> Root -> Right

Use Case: Its most famous application is on a Binary Search Tree (BST), where an inorder traversal visits the nodes in ascending sorted order.

public void inorderTraversal(TreeNode root) {
    if (root == null) return;
    inorderTraversal(root.left);      // 1. Visit left subtree
    System.out.print(root.val + " ");  // 2. Visit root
    inorderTraversal(root.right);     // 3. Visit right subtree
}

Postorder Traversal: Left -> Right -> Root

Use Case: This is useful for deleting a tree from memory. You must delete the children before you can delete the parent node.

public void postorderTraversal(TreeNode root) {
    if (root == null) return;
    postorderTraversal(root.left);      // 1. Visit left subtree
    postorderTraversal(root.right);     // 2. Visit right subtree
    System.out.print(root.val + " ");  // 3. Visit root
}

2. Iterative Traversals

While recursion is elegant, interviewers will often ask for an iterative solution. This demonstrates a deeper understanding of the traversal mechanics and how to manage the program state explicitly using a stack. It also avoids potential StackOverflowError on very deep trees.

The key idea is to use a Stack to simulate the function call stack that recursion uses behind the scenes.

Iterative Preorder Traversal

This is the most straightforward iterative traversal. The logic closely follows the "visit, go left, go right" pattern.

Here is the standard algorithm and code for iterative preorder:

1. Create an empty stack and push the root node to it.
2. Loop as long as the stack is not empty.
3. Pop a node from the stack and process it (e.g., add its value to a list).
4. Push its right child to the stack (if it's not null).
5. Push its left child to the stack (if it's not null).

We push the right child first so that the left child is on top of the stack, ensuring it gets processed first, thus maintaining the Root -> Left -> Right order.

public List<Integer> preorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val); // Visit root

        // Push right child first, so left child is processed first
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    return result;
}

Iterative Inorder Traversal

The iterative inorder algorithm is slightly different and less direct than preorder, but it beautifully simulates the recursive descent to the leftmost node.

Here is the algorithm:

1. Initialize an empty stack and a current node pointer set to root.
2. Loop as long as current is not null OR the stack is not empty.
3. Go Left: While current is not null, push it onto the stack and set current = current.left.
4. Visit Root: When current becomes null, it means we've gone as far left as possible. Pop a node from the stack, process it.
5. Go Right: Set current to the popped node's right child. The loop will then repeat, finding the leftmost node of this new subtree.

public List<Integer> inorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        // 1. Go as far left as possible
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        // 2. current is null, so pop from stack
        current = stack.pop();
        result.add(current.val); // 3. Visit the node

        // 4. Move to the right subtree
        current = current.right;
    }
    return result;
}

Iterative Postorder Traversal

Iterative postorder is the trickiest of the three. A clever and easy-to-remember approach uses two stacks.

The idea is to perform a modified preorder traversal (Root -> Right -> Left) and use a second stack to reverse the order of visited nodes.

1. Push the root node onto stack1.
2. Loop while stack1 is not empty.
3. Pop a node from stack1 and push it onto stack2.
4. Push the popped node's left child to stack1 (if not null).
5. Push the popped node's right child to stack1 (if not null).
6. After the loop, the nodes in stack2 are in postorder. Pop them all and add to your result list.

Effectively, stack1 produces the order Root -> Right -> Left. When this is pushed onto stack2 and then popped, the resulting order is the reverse: Left -> Right -> Root, which is exactly postorder.

You can find the code for this in the "Mastering Binary Tree Traversal" article under the section "Code Snippet: Post-order Traversal (Iterative)".

Conclusion

You have now learned the three fundamental depth-first traversals for binary trees, covering both the elegant recursive solutions and the more explicit, stack-based iterative solutions that are common in interviews.

Key Takeaways:

• Recursive vs. Iterative: Recursion is concise and intuitive. Iteration gives you more control, avoids recursion depth limits, and demonstrates mastery of stacks.
• Traversal Orders & Use Cases:
  • Preorder (Root-L-R): Useful for copying a tree.
  • Inorder (L-Root-R): Produces a sorted sequence from a BST.
  • Postorder (L-R-Root): Essential for safely deleting a tree.
• Complexity: All three traversals visit each node once, so the time complexity is O(N). The space complexity is O(H), where H is the height of the tree, for both the recursion call stack and the explicit stack in iterative methods. In the worst case (a skewed tree), H can be N.

A Glimpse into Advanced Traversals: For a great competitive programming challenge, you can try to perform all three traversals in a single pass using one stack. This involves storing a state with each node on the stack. The article "Preorder Inorder Postorder Traversals in One Traversal" on the takeuforward site (ID: [LINK](https://takeuforward.org/data-structure/preorder-inorder-postorder-traversals-in-one-traversal)) is an excellent resource if you want to explore this advanced technique.

Preview of the next lesson:
We've focused on "depth-first" traversals today. In our next lesson, we will explore a different strategy: "breadth-first" traversal, also known as level-order traversal. Instead of going deep, we will visit the tree level by level, for which we will use a queue instead of a stack.