Trees

What you'll learn

• Tree Terminology

  Understanding tree vocabulary is essential before diving into implementations. | Term | Definition | |------|-----------| | Root | The topmost node with no parent | | Leaf | A node with no children | | Parent | A node that has one or mor…

• Binary Trees

  A binary tree is a tree where each node has at most 2 children, referred to as the left child and right child.

• Properties of Binary Trees

  | Property | Formula | |----------|---------| | Max nodes at level i | 2^i (level starts at 0) | | Max nodes in tree of height h | 2^(h+1) - 1 | | Min height for n nodes | floor(log2(n)) | | Number of leaf nodes | floor(n/2) + 1 (for a c…

• Types of Binary Trees

  Full Binary Tree: Every node has 0 or 2 children (never just 1). Complete Binary Tree: All levels are fully filled except possibly the last, which is filled left to right. Perfect Binary Tree: All internal nodes have 2 children and all l…

• Binary Search Tree (BST)

  A BST is a binary tree with an ordering invariant: for every node, all values in the left subtree are less than the node, and all values in the right subtree are greater. Invariant: left

• Diameter of a Binary Tree

  Sample Input / Output Input tree A: Output: 4 — the longest path is 4 → 2 → 1 → 3 → 6 (4 edges) Input tree B (complete binary tree): Output: 3 — e.g., path 4 → 2 → 1 → 3 (or any path between two leaves at level 2) Input tree C (left-skew…

• Lowest Common Ancestor (LCA)

  Sample Input / Output Input tree A (BST): - lca(2, 8) → 6 (split point at root) - lca(2, 4) → 2 (one is ancestor of the other) - lca(3, 5) → 4 Input tree B (simple tree): - lca(4, 5) → 2 - lca(4, 3) → 1 Input tree C (single path): - lca(…

• Path Sum Problems

  Sample Input / Output Input tree A: - hasPathSum(root, 22) → true (path 5 → 4 → 11 → 2) - hasPathSum(root, 26) → true (path 5 → 8 → 13) - hasPathSum(root, 100) → false Input tree B (single node): - hasPathSum(root, 5) → true - hasPathSum…

• Validate BST

  Sample Input / Output Input tree A (valid BST): Output: true Input tree B (looks locally valid but globally invalid): Output: false — node 3 is in 5's right subtree but 3 Common mistake: Only checking node.left.val parent) | Aggregate su…

• Bottom-up: Return values

  Each recursive call returns computed information to its caller. The parent combines results from its children to produce its own answer. This is the most natural recursive pattern for tree problems. Time complexity: O(n) for single-pass…

• Top-down: Parameters and helper functions

  When the original function signature doesn't have enough parameters to carry path state downward, introduce a helper function with additional parameters tracking the current state (e.g., max value seen on the path from root to current no…

• Lateral: Outer-scope collection

  When you need to collect results in a list during traversal, declare the list in the enclosing function scope so all recursive calls can append to it. This is preferred over merging returned lists (which costs O(n^2) due to repeated list…

• Combining patterns

  Many problems use more than one pattern simultaneously. The diameter problem is a classic example: it returns height bottom-up while updating a global maximum laterally.

• Serialization and Deserialization

  Converting a tree to a string and back. Common approaches: 1. Preorder with nulls: Record null markers for missing children. - Serialize: 1,2,4,#,#,5,#,#,3,#,6,#,# - Unique reconstruction guaranteed 2. Level-order with nulls: BFS recordi…

• Tree DP Pattern

  Many tree problems follow a bottom-up dynamic programming pattern: 1. Define what information each node needs from its children 2. Compute the answer at each node using children's results 3. Return the needed information to the parent Ex…

• Complexity Summary

  | Operation | BST Average | BST Worst | Balanced BST | |-----------|-------------|-----------|--------------| | Search | O(log n) | O(n) | O(log n) | | Insert | O(log n) | O(n) | O(log n) | | Delete | O(log n) | O(n) | O(log n) | | Find…

• Iterative Leaf Removal Order

  Given a binary tree, repeatedly remove all current leaf nodes and return the order in which nodes are removed. Once a leaf is removed, its parent may become the new leaf in the next round.

• Problem Statement

  Given a tree, select a leaf and remove it. Repeat until all nodes are removed. Return the removal sequence such that leaves are removed layer-by-layer from the outside in.

• Approach 1: BFS Level-Order then Reverse

  The key insight is that the removal order is the reverse of BFS level-order traversal from the root. Leaves at the deepest level are removed first. Time complexity: O(n) — BFS visits every node once, and reversing the list is O(n). Space…

• Approach 2: Track Parents (with parent priority)

  A more general variant: when a leaf is removed, if its parent becomes a new leaf, that parent must be removed before other existing leaves at the same depth. Time complexity: O(n) — BFS visits every node once, and the deduplication pass…

• Key Takeaways

  1. Trees model hierarchy. Any parent-child relationship maps to a tree. 2. BSTs give O(log n) search -- but only when balanced. 3. Balancing is the key insight. AVL and Red-Black trees pay O(log n) rotation cost to maintain O(log n) heig…