🌳 Mastering Binary Tree Traversal (with Java Code Examples)

A binary tree is a tree data structure where each node has at most two children, typically referred to as the left and right children. Traversing a binary tree means visiting each node in a specific order, which is essential for various operations such as searching, inserting, deleting, or simply processing the nodes.

Binary tree traversal forms the backbone of many algorithms and data structures, particularly in search trees and graphs. It's often a fundamental topic in coding interviews and competitive programming.

In this blog, we will explore the three main types of binary tree traversal and their variations, along with Java code examples for each.

📚 Types of Binary Tree Traversal

There are three major types of binary tree traversal:

1. In-order Traversal
2. Pre-order Traversal
3. Post-order Traversal

Additionally, we will also look at Level-order Traversal (also known as Breadth-First Traversal) using a queue.

Let’s break each one down with their definitions, steps, and Java code examples.

1. In-order Traversal (Left, Root, Right)

In-order traversal visits the nodes of the binary tree in the following order: left subtree, root node, right subtree. This traversal is commonly used to obtain nodes of a binary search tree in sorted order.

Steps for In-order Traversal:

1. Traverse the left subtree recursively.
2. Visit the root node.
3. Traverse the right subtree recursively.

Code Snippet: In-order Traversal (Recursive)

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

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

Code Snippet: In-order Traversal (Iterative)

An iterative approach can also be used by simulating the recursive stack with a stack data structure.

public void inorderTraversalIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);  // Push current node to stack
            current = current.left;  // Move to left subtree
        }

        current = stack.pop();  // Pop the node from the stack
        System.out.print(current.val + " ");  // Visit root
        current = current.right;  // Move to right subtree
    }
}

2. Pre-order Traversal (Root, Left, Right)

Pre-order traversal visits the nodes in the following order: root node, left subtree, right subtree. This traversal is useful for copying a tree or prefix expression evaluation.

Steps for Pre-order Traversal:

1. Visit the root node.
2. Traverse the left subtree recursively.
3. Traverse the right subtree recursively.

Code Snippet: Pre-order Traversal (Recursive)

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

Code Snippet: Pre-order Traversal (Iterative)

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

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

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");  // Visit root

        if (node.right != null) stack.push(node.right);  // Push right child
        if (node.left != null) stack.push(node.left);  // Push left child
    }
}

3. Post-order Traversal (Left, Right, Root)

Post-order traversal visits the nodes in the following order: left subtree, right subtree, root node. This traversal is typically used for deleting a tree or postfix expression evaluation.

Steps for Post-order Traversal:

1. Traverse the left subtree recursively.
2. Traverse the right subtree recursively.
3. Visit the root node.

Code Snippet: Post-order Traversal (Recursive)

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

Code Snippet: Post-order Traversal (Iterative)

Post-order traversal can also be done iteratively using a stack, which is a bit more complicated due to the need to ensure that the root is visited after its children.

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

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

    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);  // Push root to stack2

        if (node.left != null) stack1.push(node.left);  // Push left child
        if (node.right != null) stack1.push(node.right);  // Push right child
    }

    while (!stack2.isEmpty()) {
        System.out.print(stack2.pop().val + " ");  // Visit root
    }
}

4. Level-order Traversal (Breadth-First Search)

Level-order traversal, also known as Breadth-First Search (BFS), visits the nodes level by level from top to bottom. This is usually implemented using a queue.

Steps for Level-order Traversal:

1. Start with the root node.
2. Use a queue to store nodes and visit them level by level.
3. For each node, first visit the node, then enqueue its left and right children (if they exist).

Code Snippet: Level-order Traversal

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

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");  // Visit root

        if (node.left != null) queue.offer(node.left);  // Enqueue left child
        if (node.right != null) queue.offer(node.right);  // Enqueue right child
    }
}

📏 Time Complexity

• In-order, Pre-order, Post-order Traversals: All of these traversals have a time complexity of O(n), where n is the number of nodes in the tree. This is because each node is visited exactly once.
• Level-order Traversal: Similarly, the time complexity is O(n) since each node is enqueued and dequeued exactly once.

🔄 Summary of Traversal Techniques

🧠 Interview Tips

• Tree Structure: Ensure you understand the structure of the binary tree and its different types (full binary tree, perfect binary tree, etc.).
• Recursive & Iterative: Be comfortable with both recursive and iterative approaches to traversal.
• Edge Cases: Handle cases such as empty trees, trees with one node, and trees with unbalanced structures.
• Complexity: All traversal algorithms have a time complexity of O(n) where n is the number of nodes in the tree, but the space complexity may vary based on the algorithm used (recursive calls use O(h) stack space, where h is the height of the tree).

📝 Conclusion

Binary tree traversal is a fundamental concept in computer science. By mastering in-order, pre-order, post-order, and level-order traversal, you’ll be well-equipped to handle a wide variety of problems involving trees. This knowledge is crucial for tasks like tree manipulation, searching, sorting, and even in building more complex algorithms.

The key is to practice these traversal techniques and understand the differences in their use cases. Whether you are preparing for interviews or solving algorithmic challenges, binary tree traversal is an indispensable skill.

"A good understanding of binary trees and their traversal is the foundation for mastering complex data structures like heaps, AVL trees, and graphs."