Binary Tree Completeness Check, Then B-Tree Indexes and Why Not Index Every Column

This phone-screen round started with a short binary-tree coding problem and then followed the tree into database internals: B-trees, and when to add indexes. On reflection, the candidate judged the coding problem to be a variant of the complete-binary-tree check; the exact variation was not recorded, so practice the standard form in Part 1. ### Clarifying Questions - Is an empty tree considered complete? - Is the tree given as linked nodes, or as a level-order array with markers for missing children? - How large and how deep can the tree be? Does recursion depth or the size of a work queue matter? - For the database parts, which engine does the team use, and is the workload read-heavy or write-heavy? ### Part 1 — Is the binary tree complete? Given the root of a binary tree, return whether the tree is complete. A binary tree is complete when every level except possibly the last is completely filled, and all nodes on the last level are as far left as possible. ```python class TreeNode: def __init__(self, val: int, left: "TreeNode | None" = None, right: "TreeNode | None" = None): self.val = val self.left = left self.right = right def is_complete_tree(root: TreeNode | None) -> bool: ... ``` Examples: - Levels `[1]`, `[2, 3]`, `[4, 5, 6]`, where 4 and 5 are the children of 2 and 6 is the left child of 3: complete. - The same tree with 6 as the right child of 3: not complete, because the position to the left of 6 on the last level is empty. - Root 1 with children 2 and 3, where 2 has no children and 3 has a left child 4: not complete, even though no node has a right child without a left child. ```hint Positions, not parent-child pairs Visit the nodes in an order in which "as far left as possible" becomes something you can observe directly, and ask what one empty position tells you about every position after it. ``` #### What This Part Should Cover - A precise reading of "complete", including the last level - Correct handling of a gap followed by a node, including gaps that span different subtrees - Time and space complexity ### Part 2 — From binary trees to B-trees The interviewer then steered the follow-ups toward B-trees and back to databases. Explain how a B-tree, and the B+ tree variant most databases use for indexes, differs from a balanced binary search tree, and why a database index is a B-tree rather than a binary tree. ```hint Count the expensive steps Count how many steps a lookup takes when every node visited may cost a page read, and what you could change about a node to need fewer of them. ``` #### What This Part Should Cover - Fan-out, tree height and the number of page reads per lookup - How a B-tree stays balanced on inserts and deletes - How the B+ tree layout serves range scans and ordered reads ### Part 3 — Adding indexes, and why not index every column The interviewer asked a series of questions about adding indexes to database tables, ending with: why not simply add an index on every column? Explain what an index costs, when the database will or will not use one, and how you would decide which indexes a table should have. ```hint Follow a write An index is an extra, separately ordered copy of some of the table's data. Follow one INSERT, UPDATE or DELETE through every copy it has to touch. ``` #### What This Part Should Cover - The write, storage, memory and maintenance cost of each additional index - Cases where the planner ignores an index: low selectivity, small tables, expressions on the column, composite-index column order - Choosing indexes from the real query workload, including composite, covering and partial indexes - Finding indexes that are missing or unused ### What a Strong Answer Covers - A short, correct completeness check that handles gaps across subtrees, tested on edge-case trees - B-tree reasoning grounded in disk pages and fan-out rather than in asymptotic notation alone - Index trade-offs argued from both the read side and the write side, with a concrete table and queries - Practical judgment: which indexes to add, which to drop, and how to verify the choice on a running database ### Follow-up Questions - Solve Part 1 again by numbering positions instead of tracking a gap. On what trees can those numbers grow dangerously large, and how do you guard against it? - A table has a composite index on `(a, b)`. Which of `WHERE a = ?`, `WHERE b = ?`, `WHERE a = ? AND b > ?` and `ORDER BY a, b` can use it efficiently? - A write-heavy table is mostly queried by a low-cardinality `status` column, looking for the rare rows still in one particular state. Would you index it, and how? - How do you find out, on a running database, that an index is never used or that a frequent query needs one?