Binary Trees

Binary trees are the most frequently tested data structure in coding interviews. Every node holds a value and references to at most two children — left and right. This simplicity produces a staggering variety of problems. Master the traversals, and you have the tools to tackle all of them.

The TreeNode

Java 25 keeps the node definition clean:

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

    TreeNode(int val) {
        this.val = val;
    }

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

Most interview platforms define TreeNode exactly like this. Do not waste time adding getters, setters, or builder patterns. The interviewer wants algorithm logic, not boilerplate.

Recursive Traversals

Recursive traversals are three lines of code wrapped in a null check. The order of the “visit” step determines the traversal type.

Preorder (Root → Left → Right)

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

Inorder (Left → Root → Right)

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

Postorder (Left → Right → Root)

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

All three run in O(n) time and O(h) space, where h is the tree height (recursion stack depth). For a balanced tree, h = O(log n). For a skewed tree, h = O(n).

Iterative Traversals

Interviewers ask for iterative versions to verify you understand how recursion maps to explicit stack management. This is a frequent follow-up: “Now do it without recursion.”

Iterative Preorder

Push right child first so left is processed first (LIFO order):

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

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

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return result;
}

Iterative Inorder

Walk left as far as possible, then pop and go right:

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

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }
    return result;
}

This pattern — “push all lefts, pop, go right” — appears so often that you should be able to write it from memory in under a minute.

Morris Traversal (O(1) Space Inorder): Morris traversal eliminates the stack by temporarily threading right pointers of predecessors back to the current node. It achieves O(n) time with O(1) extra space:

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, visit node
                predecessor.right = null;
                result.add(current.val);
                current = current.right;
            }
        }
    }
    return result;
}

Morris traversal modifies the tree temporarily but restores it. Interviewers appreciate this as an advanced follow-up.

Iterative Postorder (Two-Stack Method)

Postorder is the trickiest iterative traversal. The two-stack approach reverses a modified preorder:

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

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

    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);
        if (node.left != null) stack1.push(node.left);
        if (node.right != null) stack1.push(node.right);
    }

    while (!stack2.isEmpty()) {
        result.add(stack2.pop().val);
    }
    return result;
}

The trick: stack1 produces a root-right-left order. Stack2 reverses it to left-right-root — postorder.

Level-Order Traversal (BFS)

Level-order uses a queue and processes nodes level by level:

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;
}

The levelSize variable captures the queue size at the start of each level. This separates levels cleanly without sentinel nodes.

Classic Problem: Maximum Depth

A one-liner that tests recursive thinking:

int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Time: O(n). Space: O(h). This same pattern — recursive decomposition into left and right subtrees — forms the template for dozens of tree problems.

Classic Problem: Symmetric Tree

Check whether a tree mirrors itself around its center:

boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}

boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    return t1.val == t2.val
        && isMirror(t1.left, t2.right)
        && isMirror(t1.right, t2.left);
}

The key insight: the left subtree’s left child mirrors the right subtree’s right child, and vice versa.

Classic Problem: Construct Binary Tree from Preorder and Inorder

Given preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7], reconstruct the tree.

Algorithm: The first element of preorder is always the root. Find that root in inorder — everything to its left belongs to the left subtree, everything to its right belongs to the right subtree. Recurse.

int preorderIdx = 0;
Map<Integer, Integer> inorderMap = new HashMap<>();

TreeNode buildTree(int[] preorder, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    return build(preorder, 0, inorder.length - 1);
}

TreeNode build(int[] preorder, int left, int right) {
    if (left > right) return null;

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

    int inorderIdx = inorderMap.get(rootVal);
    root.left = build(preorder, left, inorderIdx - 1);
    root.right = build(preorder, inorderIdx + 1, right);

    return root;
}

The HashMap provides O(1) lookup for the root’s position in inorder, bringing the total time to O(n).

Classic Problem: Lowest Common Ancestor (LCA)

Find the lowest node that has both p and q as descendants (a node counts as its own descendant):

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    if (left != null && right != null) return root;
    return left != null ? left : right;
}

How it works: If both left and right recursive calls return non-null, the current node is the LCA. If only one side returns non-null, that side contains both target nodes (or the found node is the ancestor of the other).

Time: O(n). Space: O(h). This elegant recursion is a top-10 interview classic.

Classic Problem: Diameter of Binary Tree

The diameter is the longest path between any two nodes (measured in edges). This path does not need to pass through the root.

int diameter = 0;

int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return diameter;
}

int depth(TreeNode node) {
    if (node == null) return 0;

    int leftDepth = depth(node.left);
    int rightDepth = depth(node.right);

    diameter = Math.max(diameter, leftDepth + rightDepth);
    return 1 + Math.max(leftDepth, rightDepth);
}

At each node, the longest path passing through that node equals leftDepth + rightDepth. Track the global maximum across all nodes. The function returns depth (for parent calculations) while updating diameter as a side effect.

Classic Problem: Serialize and Deserialize Binary Tree

Convert a tree to a string and reconstruct it. The BFS approach handles this cleanly:

String serialize(TreeNode root) {
    if (root == null) return "";
    StringBuilder sb = new StringBuilder();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node == null) {
            sb.append("null,");
        } else {
            sb.append(node.val).append(",");
            queue.offer(node.left);
            queue.offer(node.right);
        }
    }
    return sb.toString();
}

TreeNode deserialize(String data) {
    if (data.isEmpty()) return null;
    String[] values = data.split(",");
    TreeNode root = new TreeNode(Integer.parseInt(values[0]));
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    int i = 1;
    while (!queue.isEmpty() && i < values.length) {
        TreeNode parent = queue.poll();

        if (!values[i].equals("null")) {
            parent.left = new TreeNode(Integer.parseInt(values[i]));
            queue.offer(parent.left);
        }
        i++;

        if (i < values.length && !values[i].equals("null")) {
            parent.right = new TreeNode(Integer.parseInt(values[i]));
            queue.offer(parent.right);
        }
        i++;
    }
    return root;
}

This produces a level-order serialization where null markers capture the tree structure completely.

BFS vs DFS: The Decision Guide

Choosing between BFS and DFS determines both correctness and efficiency on tree problems:

Use BFS When	Use DFS When
Finding minimum depth (BFS stops at first leaf)	Exploring all root-to-leaf paths
Level-by-level processing (right-side view, zigzag)	Problems requiring backtracking
Finding shortest path in unweighted tree	Checking subtree properties (BST validation)
Tree width or level sums	Computing height, diameter, or balance

Rule of thumb: If the answer lives at a specific level or the shallowest occurrence matters, use BFS. If you need to trace paths from root to leaf or aggregate subtree results, use DFS.

Edge Cases and Interviewer Tips

• Empty tree: Always check root == null first. Forgetting this causes NullPointerException in every tree problem.
• Single node: A tree with one node has height 0, depth 0, and diameter 0. Test your code against this.
• Skewed tree: A tree where every node has only a left (or only a right) child. This is the worst case for stack depth — O(n) space.
• Duplicate values: Unless the problem states otherwise, assume values can repeat. This affects LCA and search logic.

When the interviewer says “optimize,” consider whether iterative conversion reduces overhead (no recursion stack limit) or whether Morris traversal eliminates space. When they say “what if the tree is very deep,” they want you to recognize stack overflow risk with recursion and propose an iterative alternative.

State your traversal choice and its time-space complexity before writing code. This frames the solution and earns communication points.