Tree Traversal Pattern

Overview

Systematic methods to visit all nodes in a tree. Different traversals serve different purposes: inorder for BST sorted output, preorder for serialization, postorder for deletion, level-order for breadth-first operations.

When to Use

• BST operations (inorder = sorted)
• Serialization/deserialization (preorder/postorder)
• Expression trees (postorder evaluation)
• Level-based problems (BFS)
• Finding depth/height
• Ancestor/descendant relationships

Template Code

Inorder Traversal (Recursive)

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorder(root, result);
    return result;
}

private void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inorder(node.left, result);
    result.add(node.val);
    inorder(node.right, result);
}

Inorder Traversal (Iterative)

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

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

        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }

    return result;
}

Preorder Traversal (Iterative)

public List<Integer> preorderIterative(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);

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

    return result;
}

Postorder Traversal (Iterative)

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

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

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.addFirst(node.val);  // Add to front

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

    return result;
}

Morris Inorder Traversal (O(1) Space)

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

    while (current != null) {
        if (current.left == null) {
            result.add(current.val);
            current = current.right;
        } else {
            // Find inorder predecessor
            TreeNode predecessor = current.left;
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }

            if (predecessor.right == null) {
                // Create thread
                predecessor.right = current;
                current = current.left;
            } else {
                // Remove thread
                predecessor.right = null;
                result.add(current.val);
                current = current.right;
            }
        }
    }

    return result;
}

Level Order Traversal

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

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

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);

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

        result.add(level);
    }

    return result;
}

Vertical Order Traversal

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

    Map<Integer, List<Integer>> columnMap = new TreeMap<>();
    Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
    queue.offer(new Pair<>(root, 0));

    while (!queue.isEmpty()) {
        Pair<TreeNode, Integer> p = queue.poll();
        TreeNode node = p.getKey();
        int col = p.getValue();

        columnMap.computeIfAbsent(col, k -> new ArrayList<>()).add(node.val);

        if (node.left != null) queue.offer(new Pair<>(node.left, col - 1));
        if (node.right != null) queue.offer(new Pair<>(node.right, col + 1));
    }

    result.addAll(columnMap.values());
    return result;
}

Binary Tree Right Side View

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

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

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();

            if (i == size - 1) {  // Last node in level
                result.add(node.val);
            }

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

    return result;
}

Boundary Traversal

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

    if (!isLeaf(root)) result.add(root.val);

    // Left boundary (excluding leaves)
    TreeNode node = root.left;
    while (node != null) {
        if (!isLeaf(node)) result.add(node.val);
        node = node.left != null ? node.left : node.right;
    }

    // Leaves (left to right)
    addLeaves(root, result);

    // Right boundary (excluding leaves, bottom-up)
    List<Integer> rightBoundary = new ArrayList<>();
    node = root.right;
    while (node != null) {
        if (!isLeaf(node)) rightBoundary.add(node.val);
        node = node.right != null ? node.right : node.left;
    }
    Collections.reverse(rightBoundary);
    result.addAll(rightBoundary);

    return result;
}

private boolean isLeaf(TreeNode node) {
    return node.left == null && node.right == null;
}

private void addLeaves(TreeNode node, List<Integer> result) {
    if (node == null) return;
    if (isLeaf(node)) {
        result.add(node.val);
        return;
    }
    addLeaves(node.left, result);
    addLeaves(node.right, result);
}

Serialize and Deserialize (Preorder)

public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serializeHelper(root, sb);
    return sb.toString();
}

private void serializeHelper(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append("null,");
        return;
    }
    sb.append(node.val).append(",");
    serializeHelper(node.left, sb);
    serializeHelper(node.right, sb);
}

public TreeNode deserialize(String data) {
    Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
    return deserializeHelper(queue);
}

private TreeNode deserializeHelper(Queue<String> queue) {
    String val = queue.poll();
    if (val.equals("null")) return null;

    TreeNode node = new TreeNode(Integer.parseInt(val));
    node.left = deserializeHelper(queue);
    node.right = deserializeHelper(queue);
    return node;
}

Construct Tree from Inorder + Preorder

public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> inorderIndex = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderIndex.put(inorder[i], i);
    }
    return build(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1, inorderIndex);
}

private TreeNode build(int[] preorder, int preStart, int preEnd,
                       int[] inorder, int inStart, int inEnd,
                       Map<Integer, Integer> inorderIndex) {
    if (preStart > preEnd) return null;

    int rootVal = preorder[preStart];
    TreeNode root = new TreeNode(rootVal);

    int inRoot = inorderIndex.get(rootVal);
    int leftSize = inRoot - inStart;

    root.left = build(preorder, preStart + 1, preStart + leftSize,
                      inorder, inStart, inRoot - 1, inorderIndex);
    root.right = build(preorder, preStart + leftSize + 1, preEnd,
                       inorder, inRoot + 1, inEnd, inorderIndex);

    return root;
}

Time & Space Complexity

Traversal	Time	Space (Recursive)	Space (Iterative)
Inorder	O(n)	O(h)	O(h)
Preorder	O(n)	O(h)	O(h)
Postorder	O(n)	O(h)	O(h)
Level order	O(n)	-	O(w)
Morris	O(n)	-	O(1)

h = height, w = max width

Common Interview Questions

1. Inorder Traversal - Recursive and iterative
2. Preorder Traversal - Recursive and iterative
3. Postorder Traversal - Recursive and iterative
4. Level Order Traversal - BFS with queue
5. Zigzag Level Order - Alternate direction
6. Vertical Order Traversal - By column
7. Binary Tree Right Side View - Rightmost per level
8. Boundary Traversal - Anticlockwise boundary
9. Serialize/Deserialize Binary Tree - Multiple approaches
10. Construct Tree from Traversals - Preorder+Inorder, Postorder+Inorder
11. Flatten Binary Tree to Linked List - Preorder in-place
12. Kth Smallest in BST - Inorder with counter
13. Validate BST - Inorder should be sorted
14. Recover BST - Two swapped nodes, use Morris

Tips & Tricks

• Inorder of BST gives sorted sequence
• Preorder: process before children (top-down)
• Postorder: process after children (bottom-up)
• Morris traversal uses O(1) space by creating temporary threads
• For iterative, use stack for DFS, queue for BFS
• Level order size tracking: int size = queue.size() before inner loop
• To construct tree: need inorder + (preorder or postorder)