Question 1

How do you choose between DFS and BFS?

Accepted Answer

Do not open by listing mechanics — the interviewer wants your selection logic. Derive the answer from the requirement. I pick BFS when: I need the shortest path or the matching node closest to the root (BFS walks levels in order, so the first hit is the nearest); the result must be grouped by level; the tree is very deep and the recursion limit is a risk. I pick DFS when: I need to walk all paths; I am aggregating over subtrees (postorder — children before the parent); I am building a hierarchy top-down (preorder); I need sorted output from a BST (inorder). Then compare memory — the strongest part of the answer: "Both are O(n) in time; the difference is memory. DFS is O(h), the tree height; BFS is O(w), the widest level. BFS wins on a narrow deep tree, DFS on a wide shallow one. In a complete binary tree the last level holds half the nodes, so BFS costs O(n) memory there." Close with a concrete example: "Postorder DFS to compute folder sizes on a file system; BFS for 'friends two hops away' in a social graph."

Question 2

Explain the difference between preorder, inorder and postorder. What is each used for in practice?

Accepted Answer

Start with the unifying rule — it lets you hold all three at once: "The names say WHEN the node itself is processed. Left always comes before right; only the node's position moves." Preorder (node → left → right): node first. Use: copying or serialising a tree — you cannot build children before creating the parent. Also printing a hierarchy top-down (a menu, an org chart). Inorder (left → node → right): node in the middle. Use: getting the sorted sequence from a BST. This is the most-asked fact, and also the simplest way to validate a BST — if the inorder result is not ascending, it is not a BST. Postorder (left → right → node): node last. Use: deletion (children must be freed before the parent), computing folder sizes, evaluating an expression tree — in each case the parent's result depends on its children's. A strong closer: "My practical rule is — if the parent is needed BEFORE the children, preorder; AFTER, postorder; if I need sorted output, inorder."

Question 3

When would you replace a recursive traversal with an iterative one?

Accepted Answer

State the reason in one sentence: "Recursion uses the call stack, and that stack is bounded — typically a few tens of thousands of frames. If the tree depth exceeds that, I get a StackOverflowError, or in JS RangeError: Maximum call stack size exceeded." Then make the risk concrete: "In a balanced tree h ≈ log n, so even a million nodes is only ~20 deep — recursion is perfectly safe. The problem appears in a degenerate tree: a BST built from sorted data becomes a chain and h = n. So my rule is: recursion when I control the depth, iteration when the depth comes from external data." Give examples of uncontrolled depth: user-supplied JSON, the DOM, a file system, an expression tree from a parser. All of these can be deepened by hostile input, which makes it a security concern (DoS) as well. Add an implementation detail too: "The iterative version keeps its own stack array on the heap, and the heap is far larger than the call stack. In preorder, watch out to push right before left — pop order is reversed."

Question 4

How do you compute a tree's height? What do you return for an empty tree?

Accepted Answer

Give the recursive definition, since the code falls straight out of it: "A node's height is the maximum of its children's heights plus one. Base case: an empty node." Express the code in one line: height(n) = n == null ? -1 : 1 + max(height(n.left), height(n.right)). Then discuss the base-case convention EXPLICITLY — this is what interviewers are actually waiting for here: "There are two conventions. Measuring height in edges, an empty tree is −1 and a single node is 0. Measuring in nodes, an empty tree is 0 and a single node is 1. Both are valid, but mixing them produces off-by-one bugs. I usually take the edge convention (−1) because it lines up with depth." The strongest move in this answer is asking the interviewer to disambiguate: "Which convention do you expect?" That signals an engineer who can spot ambiguity. Add complexity too: O(n) time — each node once; O(h) memory — the recursion stack.

Question 5

How does traversal of an n-ary tree (say the DOM or a file system) differ from a binary tree?

Accepted Answer

State the core difference in one sentence: "Instead of left/right there is a children list, so the two recursive calls become one loop. Preorder, postorder and BFS stay the same — you simply iterate over each child." Then highlight the important nuance: inorder is meaningless for an n-ary tree, because with 5 children there is no natural definition of putting the node "in the middle". Raising that yourself is a strong signal. Clarify complexity: still O(n) time — each node visited once (all children lists together are n−1 edges). Memory is O(h) for DFS, O(w) for BFS. Close with a real-world example, since this question usually arrives in a practical context: "querySelectorAll in the DOM is conceptually a preorder DFS; computing folder sizes is postorder DFS; 'nearest matching ancestor' in a UI is actually an upward traversal, which needs a parent pointer." Add one practical warning too: real DOM or file system trees can be very deep, and symlinks can make a file system genuinely cyclic — in that case you must track visited nodes in a Set, or the traversal loops forever.

Traversal	Order	Structure	Memory	Typical use
Preorder	node → left → right	Stack (or recursion)	O(h)	Copying, serialisation
Inorder	left → node → right	Stack (or recursion)	O(h)	Sorted output from a BST
Postorder	left → right → node	Stack (or recursion)	O(h)	Deletion, aggregation (folder size)
BFS / level-order	Level by level	Queue	O(w) — the widest level	Shortest path, grouping by level

Tree basics and traversal