Binary tree and BST interview questions, with answers

The questions, with answers

1. 1.What is the difference between a binary tree and a binary search tree?

   A binary tree is any tree where each node has at most two children. A binary search tree adds an ordering rule: every value in a node's left subtree is less than the node, and every value in its right subtree is greater. The word "subtree" is the part candidates get wrong — the rule is not just about the immediate children. A node with value 10 whose left child is 5 and whose left child's right child is 12 is not a BST, even though 5 < 10 and 12 > 5.

2. 2.What are the tree traversals, and when do you use each?

   Inorder visits left subtree, node, right subtree — on a BST that yields the values in sorted order, which is the standard way to check a BST or to get the k-th smallest element. Preorder visits node, left, right — the order you'd use to copy a tree or serialise it, since the root comes first. Postorder visits left, right, node — the order for deleting a tree or evaluating an expression tree, since children are handled before the parent. Level order (breadth-first) visits level by level using a queue, and is what you want for "print each level" or "minimum depth" questions.

   def inorder(node):
       if node is None:
           return
       inorder(node.left)
       print(node.val)
       inorder(node.right)

3. 3.What is the difference between height and depth, and what are the minimum and maximum heights of a tree with n nodes?

   Depth of a node is the number of edges from the root to it; height of a node is the number of edges on the longest path from it down to a leaf. The height of the tree is the height of the root. A single node has height 0 — say which convention you're using, because some textbooks count nodes and get 1.

   With n nodes, the minimum height is ⌊log₂ n⌋ (a complete tree) and the maximum is n − 1 (a chain, every node with one child). That gap is the entire reason balanced trees exist.

   def height(node):
       if node is None:
           return -1          # empty tree; a single node then has height 0
       return 1 + max(height(node.left), height(node.right))

4. 4.Why are BST operations O(h), and why do we need balanced trees?

   Search, insert and delete in a BST each walk one path from the root downward, comparing at each node, so they cost O(h) where h is the height. In a balanced tree h is O(log n) and those operations are fast. But inserting already-sorted keys into a plain BST produces a chain with h = n − 1, and every operation becomes O(n) — no better than a linked list. Self-balancing trees (AVL, red-black) rotate nodes on insert and delete to keep h within a constant factor of log n, which is what makes the O(log n) guarantee real. Java's TreeMap and C++ std::map are red-black trees for this reason.

5. 5.How do you check whether a binary tree is a valid BST?

   The wrong answer, which interviewers wait for, is checking that each node is greater than its left child and less than its right child. That passes trees that violate the rule deeper down. The correct approach carries a valid range: the root may be anything; a left child must lie below its parent's value; a right child above; and every node must lie within the bounds inherited from all its ancestors. Alternatively, do an inorder traversal and check the sequence is strictly increasing. Both are O(n).

   def is_bst(node, lo=float('-inf'), hi=float('inf')):
       if node is None:
           return True
       if not (lo < node.val < hi):
           return False
       return is_bst(node.left, lo, node.val) and is_bst(node.right, node.val, hi)

6. 6.How do you find the lowest common ancestor of two nodes?

   In a BST, use the ordering: start at the root; if both values are smaller, go left; if both are larger, go right; otherwise the current node is the split point and therefore the LCA. That is O(h) and needs no extra space. In a plain binary tree there's no ordering to exploit, so recurse: if the current node is null or is one of the targets, return it; recurse left and right; if both sides return a node, the current node is the LCA; otherwise return whichever side found something. That is O(n).

   def lca_bst(root, p, q):
       node = root
       while node:
           if p < node.val and q < node.val:
               node = node.left
           elif p > node.val and q > node.val:
               node = node.right
           else:
               return node

7. 7.What do full, complete, perfect and balanced mean for a binary tree?

   Full: every node has 0 or 2 children — no node has exactly one. Complete: every level is fully filled except possibly the last, and the last level's nodes are as far left as possible — this is the shape a binary heap has, which is why a heap fits in an array. Perfect: every internal node has two children and all leaves are at the same depth, so it has exactly 2^(h+1) − 1 nodes. Balanced: the heights of the left and right subtrees of every node differ by at most one (the AVL definition). These are independent properties; a tree can be full without being complete and complete without being full.

8. 8.How do you do a level order traversal?

   Breadth-first search with a queue. Enqueue the root; then repeatedly dequeue a node, visit it, and enqueue its children. To process one level at a time — needed for "print by level", "right side view" or "zigzag" questions — record the queue's size at the start of each level and process exactly that many nodes before moving on. Time O(n); the queue holds at most one level, which in the worst case is about n/2 nodes, so space is O(n).

   from collections import deque
   
   def level_order(root):
       if root is None:
           return []
       levels, q = [], deque([root])
       while q:
           size = len(q)
           level = []
           for _ in range(size):
               node = q.popleft()
               level.append(node.val)
               if node.left:
                   q.append(node.left)
               if node.right:
                   q.append(node.right)
           levels.append(level)
       return levels

How the diagnostic asks it

One question from the DSA bank, exactly as a sitting would show it. The bank has 3 on trees (binary trees/bst) and 30 across DSA.