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 orders | Preorder, inorder, postorder |
|---|---|
| Breadth-first | Level order with a queue |
| Space | O(h) for DFS, O(w) for BFS, O(1) for Morris |
| Key fact | Inorder 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
- Pushing the left child before the right in iterative preorder, which reverses the visit order.
- Forgetting to reverse the result in the two-order postorder trick.
- Flipping the zigzag direction per node instead of per level.
- Not restoring the temporary links in Morris traversal.
- Building the left subtree first when reconstructing from postorder, where the right subtree must come first.
Tree Traversal Interview Questions: questions with worked answers
1 Inorder traversal without recursion
easySimulate 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.
pythondef 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 resjavaList<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 Preorder traversal without recursion
easyPreorder 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.
pythondef 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 resjavaList<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 Postorder traversal without recursion
mediumPostorder 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.
pythondef 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]javaList<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 Morris inorder traversal in O(1) extra space
hardTemporarily 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.
pythondef 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 resjavaList<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 Level order traversal from the bottom up
easyDo 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.
pythonfrom 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]javaList<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 Zigzag level order traversal
mediumTraverse 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).
pythonfrom 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 resjavaList<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 Vertical order traversal
mediumGive 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.
pythonfrom 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)]javaList<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 All root-to-leaf paths as strings
easyDo 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).
pythondef 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 resjavaList<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 Build a tree from inorder and postorder traversals
mediumThe 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.
pythondef 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)javaint 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 Flatten a binary tree into a linked list in preorder
mediumReuse 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.
pythondef 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.rightjavavoid 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 Populate next right pointers in each node
mediumLink 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.
pythondef 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 rootjavaNode 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 Rebuild a binary search tree from its preorder traversal
hardEach 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.
pythondef 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'))javaint 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
- Trie (Prefix Tree) Interview Questions
- Two pointers interview questions with worked solutions
- Union-Find (Disjoint Set Union) Interview Questions
- Array interview questions with worked solutions
- Backtracking interview questions with worked solutions
- BFS (Breadth-First Search) Interview Questions
- Binary search interview questions with worked solutions
- Binary Search Tree Interview Questions and Answers
- Binary Tree Interview Questions and Answers
- Bit manipulation interview questions with worked solutions
- Bitmask DP Interview Questions
- Cyclic sort pattern interview questions with worked solutions