Autocoder

Tree Traversal Interview Questions

Last updated 2026-11-19

A traversal visits every node of a tree in a defined order, and most tree questions depend on choosing the right one. Interviewers ask for iterative versions to see that you understand what the recursion stack is doing, and for reconstruction problems to test how well you know what each order encodes.

Java snippets assume class TreeNode { int val; TreeNode left, right; } and, where needed, a Node with an extra next field. Python snippets assume the same shapes. The problems cover depth-first orders, level orders, in-place tricks like Morris and rebuilding trees from traversals, each with Python and Java code, complexity and edge cases. For problems built on top of these orders see binary tree interview questions and binary search tree interview questions.

Depth-first ordersPreorder, inorder, postorder
Breadth-firstLevel order with a queue
SpaceO(h) for DFS, O(w) for BFS, O(1) for Morris
Key factInorder of a BST is sorted

The pattern and when to spot it

Pick the traversal by what the question needs. Preorder visits a node before its children, so it is natural for copying or serialising a tree. Inorder gives sorted order on a BST. Postorder visits children first, which suits deleting a tree or computing values from the bottom up. Level order handles anything about depth, levels or the nearest node, and uses a queue.

Reconstruction questions rely on what each order reveals. Preorder and postorder give the root first or last, while inorder splits the left and right subtrees around the root. Two orders that include inorder uniquely identify a tree when values are distinct; preorder with postorder alone does not for trees with single children. For O(1) extra space, Morris threading borrows empty right pointers and restores them as it goes.

Common mistakes

Tree Traversal Interview Questions: questions with worked answers

  1. 1

    Inorder traversal without recursion

    easy

    Simulate the call stack. Push the node and move left as far as possible, then pop, visit and move to the right child. Inorder visits left subtree, node, right subtree, which gives sorted order for a binary search tree. Time O(n), space O(h). Edge cases: empty tree, skewed tree (stack holds n nodes), a node with only a right child.

    python
    def inorder(root):
        res, st, cur = [], [], root
        while cur or st:
            while cur:
                st.append(cur)
                cur = cur.left
            cur = st.pop()
            res.append(cur.val)
            cur = cur.right
        return res
    java
    List<Integer> inorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !st.isEmpty()) {
            while (cur != null) { st.push(cur); cur = cur.left; }
            cur = st.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
  2. 2

    Preorder traversal without recursion

    easy

    Preorder visits node, left, right. Use a stack: pop a node, visit it, then push the right child before the left so the left is processed first. Pushing in that order is the whole trick. Time O(n), space O(h). Edge cases: empty tree, only right children, nodes with a single child.

    python
    def preorder(root):
        res, st = [], [root] if root else []
        while st:
            n = st.pop()
            res.append(n.val)
            if n.right: st.append(n.right)
            if n.left: st.append(n.left)
        return res
    java
    List<Integer> preorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> st = new ArrayDeque<>();
        st.push(root);
        while (!st.isEmpty()) {
            TreeNode n = st.pop();
            res.add(n.val);
            if (n.right != null) st.push(n.right);
            if (n.left != null) st.push(n.left);
        }
        return res;
    }
  3. 3

    Postorder traversal without recursion

    medium

    Postorder is left, right, node. A simple way: do a modified preorder that visits node, right, left, then reverse the result. The reverse of node-right-left is left-right-node. A single-stack version tracks the last visited node, but the reverse trick is easier to get right. Time O(n), space O(h). Edge cases: empty tree, a root with only one child, forgetting the final reversal.

    python
    def postorder(root):
        res, st = [], [root] if root else []
        while st:
            n = st.pop()
            res.append(n.val)
            if n.left: st.append(n.left)
            if n.right: st.append(n.right)
        return res[::-1]
    java
    List<Integer> postorder(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null) return res;
        Deque<TreeNode> st = new ArrayDeque<>();
        st.push(root);
        while (!st.isEmpty()) {
            TreeNode n = st.pop();
            res.addFirst(n.val);
            if (n.left != null) st.push(n.left);
            if (n.right != null) st.push(n.right);
        }
        return res;
    }
  4. 4

    Morris inorder traversal in O(1) extra space

    hard

    Temporarily thread the tree. For a node with a left child, find its inorder predecessor, the rightmost node of the left subtree, and point its right link back to the node. Next time the walk reaches the node, that link already exists, so the left subtree is done: remove the link, visit the node and go right. The tree is restored by the end. Time O(n), each edge is walked at most twice, space O(1). Edge cases: empty tree, the tree must be restored (remove every thread), concurrent readers would see the modified links, nodes with no left child are visited directly.

    python
    def morris_inorder(root):
        res, cur = [], root
        while cur:
            if not cur.left:
                res.append(cur.val)
                cur = cur.right
            else:
                pred = cur.left
                while pred.right and pred.right is not cur:
                    pred = pred.right
                if pred.right is None:
                    pred.right = cur
                    cur = cur.left
                else:
                    pred.right = None
                    res.append(cur.val)
                    cur = cur.right
        return res
    java
    List<Integer> morrisInorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left == null) { res.add(cur.val); cur = cur.right; }
            else {
                TreeNode pred = cur.left;
                while (pred.right != null && pred.right != cur) pred = pred.right;
                if (pred.right == null) { pred.right = cur; cur = cur.left; }
                else { pred.right = null; res.add(cur.val); cur = cur.right; }
            }
        }
        return res;
    }
  5. 5

    Level order traversal from the bottom up

    easy

    Do an ordinary level-order traversal with a queue, collecting one list per level, and then reverse the list of levels. Inserting each level at the front of a linked list achieves the same without a final reversal. Time O(n), space O(w) plus output. Edge cases: empty tree (empty list), a single node, skewed trees giving one node per level.

    python
    from collections import deque
    def level_order_bottom(root):
        res = []
        if not root:
            return res
        dq = deque([root])
        while dq:
            level = []
            for _ in range(len(dq)):
                n = dq.popleft()
                level.append(n.val)
                if n.left: dq.append(n.left)
                if n.right: dq.append(n.right)
            res.append(level)
        return res[::-1]
    java
    List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> res = new LinkedList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int i = q.size(); i > 0; i--) {
                TreeNode n = q.poll();
                level.add(n.val);
                if (n.left != null) q.add(n.left);
                if (n.right != null) q.add(n.right);
            }
            res.addFirst(level);
        }
        return res;
    }
  6. 6

    Zigzag level order traversal

    medium

    Traverse level by level, and alternate the direction of reading: left to right on even levels, right to left on odd ones. Collect each level in normal order, then reverse the odd ones, or fill a deque from the appropriate end. The queue itself always processes left to right. Time O(n), space O(w). Edge cases: empty tree, single node, flipping the direction flag every level (not every node).

    python
    from collections import deque
    def zigzag(root):
        res, ltr = [], True
        if not root:
            return res
        dq = deque([root])
        while dq:
            level = []
            for _ in range(len(dq)):
                n = dq.popleft()
                level.append(n.val)
                if n.left: dq.append(n.left)
                if n.right: dq.append(n.right)
            res.append(level if ltr else level[::-1])
            ltr = not ltr
        return res
    java
    List<List<Integer>> zigzag(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        boolean ltr = true;
        while (!q.isEmpty()) {
            LinkedList<Integer> level = new LinkedList<>();
            for (int i = q.size(); i > 0; i--) {
                TreeNode n = q.poll();
                if (ltr) level.addLast(n.val); else level.addFirst(n.val);
                if (n.left != null) q.add(n.left);
                if (n.right != null) q.add(n.right);
            }
            res.add(level);
            ltr = !ltr;
        }
        return res;
    }
  7. 7

    Vertical order traversal

    medium

    Give the root column 0, a left child column - 1 and a right child column + 1. Traverse with BFS or DFS recording (column, row, value), then sort by column, then row, then value, and group by column. Sorting inside a column is what makes nodes in the same position come out in value order. Time O(n log n), space O(n). Edge cases: nodes sharing the same row and column (sort by value), empty tree, a skewed tree spanning many columns.

    python
    from collections import deque, defaultdict
    def vertical_order(root):
        if not root:
            return []
        cols = defaultdict(list)
        dq = deque([(root, 0, 0)])
        while dq:
            n, r, c = dq.popleft()
            cols[c].append((r, n.val))
            if n.left: dq.append((n.left, r + 1, c - 1))
            if n.right: dq.append((n.right, r + 1, c + 1))
        return [[v for _, v in sorted(cols[c])] for c in sorted(cols)]
    java
    List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        TreeMap<Integer, List<int[]>> cols = new TreeMap<>();
        Map<TreeNode, int[]> pos = new HashMap<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root); pos.put(root, new int[]{0, 0});
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            int[] p = pos.get(n);
            cols.computeIfAbsent(p[1], k -> new ArrayList<>()).add(new int[]{p[0], n.val});
            if (n.left != null) { pos.put(n.left, new int[]{p[0] + 1, p[1] - 1}); q.add(n.left); }
            if (n.right != null) { pos.put(n.right, new int[]{p[0] + 1, p[1] + 1}); q.add(n.right); }
        }
        for (List<int[]> col : cols.values()) {
            col.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
            List<Integer> vals = new ArrayList<>();
            for (int[] e : col) vals.add(e[1]);
            res.add(vals);
        }
        return res;
    }
  8. 8

    All root-to-leaf paths as strings

    easy

    Do a preorder DFS carrying the path so far as a string. At a leaf, record the finished path. Build the string by appending an arrow and the value, passing a new string down so no undo step is needed. Time O(n * h) for building strings, space O(h) plus output. Edge cases: empty tree (empty list), a single node (just its value), negative values (the minus sign is part of the value).

    python
    def binary_tree_paths(root):
        res = []
        def go(n, path):
            if not n:
                return
            path += str(n.val)
            if not n.left and not n.right:
                res.append(path)
                return
            go(n.left, path + '->')
            go(n.right, path + '->')
        go(root, '')
        return res
    java
    List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        go(root, "", res);
        return res;
    }
    private void go(TreeNode n, String path, List<String> res) {
        if (n == null) return;
        path += n.val;
        if (n.left == null && n.right == null) { res.add(path); return; }
        go(n.left, path + "->", res);
        go(n.right, path + "->", res);
    }
  9. 9

    Build a tree from inorder and postorder traversals

    medium

    The last postorder element is the root. Find it in the inorder array to split the left and right subtrees. Build the right subtree first, because moving backwards through postorder yields root, right, left. A map from value to inorder index keeps each lookup O(1). Values must be distinct. Time O(n), space O(n). Edge cases: a single node, skewed trees, duplicates make the answer ambiguous, building right before left is essential.

    python
    def build_tree(inorder, postorder):
        idx = {v: i for i, v in enumerate(inorder)}
        pos = len(postorder) - 1
        def build(lo, hi):
            nonlocal pos
            if lo > hi:
                return None
            node = TreeNode(postorder[pos]); pos -= 1
            m = idx[node.val]
            node.right = build(m + 1, hi)
            node.left = build(lo, m - 1)
            return node
        return build(0, len(inorder) - 1)
    java
    int pos;
    Map<Integer, Integer> idx = new HashMap<>();
    TreeNode buildTree(int[] in, int[] post) {
        for (int i = 0; i < in.length; i++) idx.put(in[i], i);
        pos = post.length - 1;
        return build(post, 0, in.length - 1);
    }
    private TreeNode build(int[] post, int lo, int hi) {
        if (lo > hi) return null;
        TreeNode node = new TreeNode(post[pos--]);
        int m = idx.get(node.val);
        node.right = build(post, m + 1, hi);
        node.left = build(post, lo, m - 1);
        return node;
    }
  10. 10

    Flatten a binary tree into a linked list in preorder

    medium

    Reuse the right pointers. For each node with a left child, find the rightmost node of the left subtree, attach the original right subtree to it, move the left subtree to the right and clear the left link. Then continue with the next right node. This runs in place with O(1) extra space, similar to a Morris traversal. Time O(n), space O(1). Edge cases: empty tree, a tree with only left children (all move to the right), clearing every left pointer, nodes without a left child are skipped.

    python
    def flatten(root):
        cur = root
        while cur:
            if cur.left:
                pred = cur.left
                while pred.right:
                    pred = pred.right
                pred.right = cur.right
                cur.right = cur.left
                cur.left = None
            cur = cur.right
    java
    void flatten(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode pred = cur.left;
                while (pred.right != null) pred = pred.right;
                pred.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
  11. 11

    Populate next right pointers in each node

    medium

    Link every node to its right neighbour on the same level. Walk level by level using the next pointers already built: for the current level, thread the children of each node onto a dummy-headed chain, then move to the start of the next level. It works for any binary tree, not just perfect ones, and uses O(1) space instead of a queue. Time O(n), space O(1). Edge cases: empty tree, a tree with gaps where a node has only one child, the last node on each level pointing to null.

    python
    def connect(root):
        cur = root
        while cur:
            dummy = Node(0)
            tail = dummy
            while cur:
                if cur.left:
                    tail.next = cur.left
                    tail = tail.next
                if cur.right:
                    tail.next = cur.right
                    tail = tail.next
                cur = cur.next
            cur = dummy.next
        return root
    java
    Node connect(Node root) {
        Node cur = root;
        while (cur != null) {
            Node dummy = new Node(0), tail = dummy;
            while (cur != null) {
                if (cur.left != null) { tail.next = cur.left; tail = tail.next; }
                if (cur.right != null) { tail.next = cur.right; tail = tail.next; }
                cur = cur.next;
            }
            cur = dummy.next;
        }
        return root;
    }
  12. 12

    Rebuild a binary search tree from its preorder traversal

    hard

    Each value must stay within an upper bound inherited from its ancestors. Consume the preorder array with a shared index. A value above the bound does not belong to this subtree, so return null. Otherwise take it as the root, build the left subtree with the root value as the bound, then the right subtree with the inherited bound. No sorting is needed. Time O(n), space O(h). Edge cases: a single value, strictly decreasing input (a left chain), strictly increasing input (a right chain), distinct values assumed.

    python
    def bst_from_preorder(pre):
        i = 0
        def build(bound):
            nonlocal i
            if i == len(pre) or pre[i] > bound:
                return None
            node = TreeNode(pre[i]); i += 1
            node.left = build(node.val)
            node.right = build(bound)
            return node
        return build(float('inf'))
    java
    int i;
    TreeNode bstFromPreorder(int[] pre) {
        i = 0;
        return build(pre, Integer.MAX_VALUE);
    }
    private TreeNode build(int[] pre, int bound) {
        if (i == pre.length || pre[i] > bound) return null;
        TreeNode node = new TreeNode(pre[i++]);
        node.left = build(pre, node.val);
        node.right = build(pre, bound);
        return node;
    }

Frequently asked questions

What is the difference between inorder, preorder and postorder?

They differ in when the node is visited relative to its subtrees: before both (preorder), between them (inorder) or after both (postorder). Inorder on a BST yields ascending values.

Why do interviewers ask for iterative traversal?

It shows that you understand the call stack and can avoid recursion limits on deep trees. An explicit stack makes the control flow visible.

Which two traversals determine a binary tree uniquely?

Inorder together with preorder, or inorder together with postorder, when values are distinct. Preorder with postorder alone can be ambiguous.

How often do traversal questions appear in coding rounds?

Very often, either directly or as part of a larger tree problem. The DSA coding round guide shows where trees fit in the preparation plan.

Related guides

More in DSA Interview Questions

See all in this section