Trees
Hierarchical node structures built on the same pointer discipline as linked lists, traversed via recursion or an explicit stack/queue.
Try answering in your head first, then click a question to check the model answer.
Q1.Why does an unbalanced BST degrade search to O(n) instead of the expected O(log n)?(show answer)
If elements are inserted in already-sorted order (e.g. 1, 2, 3, 4, 5...), each new node only ever has a right child, producing a tree that's effectively a linked list — every search must traverse potentially the entire chain, giving O(n). A balanced BST keeps both subtrees roughly equal in size at every node, which is what guarantees the O(log n) height that makes search fast; self-balancing trees (AVL, red-black) enforce this automatically.
Q2.Explain the three common depth-first traversal orders and one use case for each.(show answer)
In-order (left, root, right) visits a BST's nodes in sorted order — useful for extracting sorted data. Pre-order (root, left, right) visits the root before its subtrees — useful for copying/serializing a tree, since you can reconstruct it by reading nodes in that same order. Post-order (left, right, root) visits children before their parent — useful for safely deleting a tree bottom-up, or evaluating an expression tree, since you need the operands' values before applying the operator at the parent.
Q3.How would you determine if a binary tree is height-balanced?(show answer)
Recursively compute the height of each subtree; at every node, check that the heights of the left and right subtrees differ by at most 1, and that both subtrees are themselves balanced. An efficient implementation computes height and checks balance in the same bottom-up recursive pass (O(n) total) rather than recomputing height separately for every node (which would be O(n²)).
Q4.Why would you choose BFS (level-order) over DFS when searching a tree for the shallowest node matching a condition?(show answer)
BFS visits nodes level by level, so the first matching node it finds is guaranteed to be at the minimum depth — it can stop immediately once found. DFS dives deep down one branch before backtracking, so it could find a much deeper match first and would need to explore the entire tree (or track the best depth seen) to guarantee finding the shallowest one.