Skip to content
Tech Interview Prep
Technical interview guide

Trees

Hierarchical node structures built on the same pointer discipline as linked lists, traversed via recursion or an explicit stack/queue.

Read
44 min
Practice MCQs
25
Interview Q&A
25
Edition
v6
Editorial status
Reviewed

Scope: Language-neutral, with ordered-map guarantees cited from the C++ standard containers and java.util as of Java 21.

Curated: · Written: · Reviewed:

25 questions

MCQ-1A binary tree is defined recursively, and this function is meant to return the largest value stored in it: ```python def tree_max(node): if node is None: return 0 return max(node.val, tree_max(node.left), tree_max(node.right)) ``` It is called on this tree, whose values are all negative: ``` -5 / \ -2 -8 / \ -9 -3 ``` What does tree_max return?
MCQ-3A build tool must report each package's total footprint: its own artifact plus everything it pulls in, transitively. It fills that in with this walk (Python 3, run exactly as written): ```python def size(p, acc): acc += p.own p.total = acc for d in p.deps: size(d, acc) ``` The dependency tree, with each package's own artifact size: | package | own (MB) | deps | | --- | --- | --- | | app | 5 | core, net | | core | 30 | math, io | | math | 20 | - | | io | 40 | sockets | | sockets | 15 | - | | net | 50 | - | size(app, 0) is called once. What value does the run write into io.total?
MCQ-4A service walks a binary tree level by level to aggregate per-level metrics. It uses a queue and snapshots `len(q)` at the start of each level. The tree is: ``` 1 / \ 2 3 / \ \ 4 5 6 ``` Immediately after the loop finishes processing the level that contains 2 and 3, what does the queue hold, front to back?
MCQ-17A build tool stores each target's dependencies as an n-ary tree. Target A has children [B, C, D]; B has children [E, F]; C has children [G]; D, E, F and G are leaves. The tool must emit a target only after every target it depends on, and must list siblings in the order given. Which sequence does it emit?
MCQ-6A range-scan service emits keys by running an inorder traversal over a binary tree it assumes is a BST. The tree it just received has root 20, left child 10, right child 30; node 10 has left child 5 and right child 25. The service's validator checks each node only against its immediate children, and it passed this tree. Which sequence does the inorder traversal emit?
MCQ-13A serialization format must round-trip arbitrary binary trees with distinct keys using exactly two traversal sequences and no null markers. Which pair makes reconstruction unique, and what does the second sequence contribute?
MCQ-15In an iterative post-order traversal of a binary tree using an explicit stack, how is visited state tracked to avoid infinite reprocessing of right subtrees?
MCQ-22A layout service checks that an icon tree is its own mirror before rendering it flipped. The check walks the root's left subtree inorder, walks the root's right subtree inorder, reverses the second walk, and passes the tree when the two sequences are equal; null children are never written out. It passes a tree that renders wrong after the flip: the root is 4, the left subtree is node 2 whose only child is a right child 2, and the right subtree is node 2 whose only child is a right child 2, with ids repeating across nodes. Which change to the check rejects this tree?
MCQ-11A service stores an org chart as a binary tree: node 1 is the root, with left child 2 and right child 3; node 2 has left child 4 and right child 5. Ids were assigned in insertion order, so the tree is not ordered by id. A function finds the lowest common ancestor of two ids by descending from the root: if both ids are less than the current node's id it moves left, if both are greater it moves right, otherwise it returns the current node. What does it return for ids 4 and 5, and what is the correct lowest common ancestor?
MCQ-23A service stores a binary tree in a flat array using the complete-tree layout: the root at index 0, and the children of index i at 2i+1 and 2i+2. The tree has 500 nodes, but its shape is arbitrary: one branch is a chain of 30 left children hanging off the root. How many array slots does the layout need to hold this tree?
MCQ-2A service builds an in-memory index over a binary tree and stores a `height` field on every node; downstream code sizes buffers from it. The tree is ``` A / \ B C / \ D E ``` and the builder is ```python def annotate(node, depth=0): if node is None: return -1 h = 1 + max(annotate(node.left, depth + 1), annotate(node.right, depth + 1)) node.depth = depth node.height = depth return h ``` After `annotate(root)` runs, for which node does the stored `height` equal that node's true height (edges on the longest downward path to a leaf; a leaf has height 0)?
MCQ-19An order-statistics BST caches a subtree size at every node and computes rank(k), the number of stored keys less than k, by summing left-subtree sizes along the search path from the root. Keys are inserted in this order: 50, 30, 70, 20, 40, 60, 80. The delete routine unlinks the target node and frees it, but never adjusts any cached size. After deleting 20, what does rank(60) return?
MCQ-21The interviewer draws this binary tree on the whiteboard and asks for its diameter: the number of edges on the longest path between any two nodes. The leaves are G, H and B. ``` R / \ A B / \ C D / \ E F / \ G H ``` What do you answer?
MCQ-12When computing a tree diameter or maximum path sum in a binary tree using bottom-up postorder DFS, how must the value returned by a recursive subcall differ from the candidate value considered for the global optimum?
MCQ-5A team's BST validator walks the tree and at each node checks only that the left child's key is smaller and the right child's key is larger. On this tree it reports the tree as valid: ``` 20 / \ 10 30 / \ 25 35 / 5 ``` A second validator instead carries a permitted (low, high) interval down the recursion, narrowing it at each node, and visits the left subtree before the right. Which key does the second validator reject first, and against which interval is that key checked?
MCQ-7A service builds an in-memory index by inserting 65,536 records into a plain binary search tree (no rebalancing) in ascending key order, then serves point lookups. A lookup for the largest key performs how many key comparisons?
MCQ-24A service inserts 65,536 integer keys into a plain (unbalanced) binary search tree in ascending order, then looks up the largest key. The lookup performs 65,536 comparisons. A teammate reports the operation as O(log n) because log₂ 65,536 = 16. Which correction is right?
MCQ-14A service inserts 50,000 already-sorted integer keys into a plain binary search tree with no rebalancing, then runs a recursive in-order traversal. CPython's default recursion limit is 1000. What happens?
MCQ-8A code review is checking a BST delete routine that must remove a node with two children. Which replacement keeps the ordering invariant intact?
MCQ-16A price service stores quotes in this BST, and a background job emits a sorted snapshot with Morris traversal: ``` 50 / \ 30 70 / \ 20 40 ``` While the job runs, a reader thread does ordinary BST lookups on the same tree. Lookups for 20, 30, 40, 50 and 70 return the right node, but lookups for 25 and 45 spin in a tight loop instead of returning. Once the job finishes the tree is intact. What explains the two spinning lookups?
MCQ-10When rebalancing an AVL tree after an insertion, what is the asymptotic time complexity and the maximum number of pointer updates required to execute a single rotation?
MCQ-9An on-disk index stores 16 million 8-byte keys. Pages are 4 KB, and a B-tree node packs keys with 8-byte child pointers to a fanout of 256. A colleague proposes replacing it with a red-black tree in which every node occupies its own 4 KB page. Both structures are O(log n). For a point lookup, roughly how many page reads does each take?
MCQ-20A Java service keeps an in-memory index of 1,000,000 order IDs in an ArrayList, kept sorted by Collections.binarySearch for lookups and System.arraycopy for insertions. At 20,000 inserts/sec the p99 insert latency is 250 ms and the box is CPU-saturated. What does the measurement show?
MCQ-18A service holds 50 million keys in an in-memory index on one machine. It must sustain 100,000 point lookups and 20,000 ceiling queries (smallest key >= x) per second, plus 5,000 inserts per second, and every query has to see the inserts already applied. Ceiling queries today copy all 50 million keys into an array and sort them, about 1.3 x 10^9 key comparisons, close to a second each. Which change sustains the load and keeps ceiling queries under 1 ms?
MCQ-25A service holds 40 million order records in memory, keyed by a 64-bit timestamp, on a 16-core box. It serves 30,000 point lookups per second by exact timestamp and 200 range queries per second, each returning about 5,000 records in ascending timestamp order; range results must reflect inserts within 100 ms, and inserts run at 5,000/s. The current hash map answers a point lookup in 80 ns, but a range query scans all 40 million entries in 210 ms, and the p99 budget is 50 ms. What should the team do?