Trees & Binary Search Tree

Think of it like this

A tree is like a company org chart: the CEO is at the top (root), each manager has direct reports (children), and everyone has exactly one boss (parent). There are no loops, you can't be your own manager's manager.

A binary tree means each node has at most two children: left and right.

A binary search tree (BST) adds an ordering rule: everything to the left is smaller, everything to the right is larger. This one rule is what gives you fast search, insert, and sorted traversal.

Vocabulary

              50          ← Root (no parent)
             /  \
           30    70       ← Internal nodes (have children)
          / \   / \
        20  40 60  80     ← Leaf nodes (no children)
 
Terms:
  Height of tree = 2   (longest root-to-leaf path, counting edges)
  Depth of node 60 = 2 (root-to-60 edges)
  Subtree rooted at 30 = {20, 30, 40}

The BST Property

For every node N in a BST:

Every value in N's left subtree is strictly less than N.val
Every value in N's right subtree is strictly greater than N.val

Valid BST:          Invalid (8 is in right subtree of 10
                             but 8 < 10, violating the rule):
    10                  10
   /  \                /  \
  5   15              5   15
 / \  / \            / \  /
3   7 12 20         3   7 8  ← 8 should be left of 10, not right of 15

The payoff: inorder traversal (left → node → right) visits all values in sorted order.

Node Implementation

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}
 
// Insert into BST
function insert(root, val) {
  if (!root) return new TreeNode(val);
  if (val < root.val)      root.left  = insert(root.left,  val);
  else if (val > root.val) root.right = insert(root.right, val);
  // equal: BST typically ignores duplicates (or you choose a side)
  return root;
}
 
// Search BST
function search(root, val) {
  if (!root || root.val === val) return root;
  return val < root.val
    ? search(root.left,  val)
    : search(root.right, val);
}
 
// Delete from BST (the trickiest operation)
function deleteNode(root, val) {
  if (!root) return null;
  if (val < root.val)      { root.left  = deleteNode(root.left,  val); }
  else if (val > root.val) { root.right = deleteNode(root.right, val); }
  else {
    // Found the node to delete
    if (!root.left)  return root.right; // no left child → replace with right
    if (!root.right) return root.left;  // no right child → replace with left
    // Two children: replace val with inorder successor (min of right subtree)
    let successor = root.right;
    while (successor.left) successor = successor.left;
    root.val = successor.val;
    root.right = deleteNode(root.right, successor.val);
  }
  return root;
}

Time Complexity

Operation	Average (balanced)	Worst (skewed)	Why worst is bad
Search	O(log n)	O(n)	Skewed tree = linked list
Insert	O(log n)	O(n)	Must find correct position
Delete	O(log n)	O(n)	Must find node + rebalance
Inorder traversal	O(n)	O(n)	Must visit every node
Find min/max	O(log n)	O(n)	Leftmost/rightmost node

Critical insight: A BST inserted in sorted order degrades to a linked list (height = n). This is why balanced BSTs (AVL, Red-Black) exist.

Four Traversal Orders

Tree:        4
            / \
           2   6
          / \ / \
         1  3 5  7
 
Inorder   (L → Root → R): 1, 2, 3, 4, 5, 6, 7  ← SORTED! 🎉
Preorder  (Root → L → R): 4, 2, 1, 3, 6, 5, 7  ← used to serialize/copy trees
Postorder (L → R → Root): 1, 3, 2, 5, 7, 6, 4  ← delete subtrees bottom-up
Level-order (BFS by row):  4, 2, 6, 1, 3, 5, 7  ← used for "right side view"

// Recursive traversals (clean but uses O(h) call stack space)
function inorder(node, result = []) {
  if (!node) return result;
  inorder(node.left, result);
  result.push(node.val);   // ← visit in the middle
  inorder(node.right, result);
  return result;
}
 
function preorder(node, result = []) {
  if (!node) return result;
  result.push(node.val);   // ← visit first
  preorder(node.left, result);
  preorder(node.right, result);
  return result;
}
 
// Iterative inorder, often required in interviews to avoid stack overflow
function inorderIterative(root) {
  const result = [], stack = [];
  let curr = root;
  while (curr || stack.length) {
    // Go as far left as possible
    while (curr) { stack.push(curr); curr = curr.left; }
    curr = stack.pop();
    result.push(curr.val);  // ← visit
    curr = curr.right;      // ← then go right
  }
  return result;
}
 
// Level-order (BFS)
function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

Binary Search Tree: Search for 7

1 / 4

Start at the root (8). We are looking for 7. Since 7 < 8, we go left.

Key Recursive Patterns

Most tree problems use one of two DFS patterns:

// Pattern A: Compute something bottom-up (return a value from subtrees)
function height(node) {
  if (!node) return 0;
  const leftH  = height(node.left);
  const rightH = height(node.right);
  return 1 + Math.max(leftH, rightH); // combine left + right results
}
 
// Pattern B: Carry information top-down (pass parameters down)
function isValidBST(node, min = -Infinity, max = Infinity) {
  if (!node) return true;
  if (node.val <= min || node.val >= max) return false;
  return isValidBST(node.left,  min, node.val) &&   // left: tighten max
         isValidBST(node.right, node.val, max);       // right: tighten min
}
 
// Pattern C: Path problems with a global variable
let maxPathSum = -Infinity;
function maxGain(node) {
  if (!node) return 0;
  const left  = Math.max(0, maxGain(node.left));   // ignore negative gains
  const right = Math.max(0, maxGain(node.right));
  maxPathSum = Math.max(maxPathSum, node.val + left + right); // update global
  return node.val + Math.max(left, right); // only one branch goes upward
}

Balanced BSTs to Know (Reference)

Structure	Balance Guarantee	Used In
AVL Tree	Height ≤ 1.44 log₂ n	Databases needing fast lookup
Red-Black Tree	Height ≤ 2 log₂(n+1)	C++ `std::map`, Java `TreeMap`
B-Tree / B+ Tree	Disk-page-sized nodes, multi-key	File systems, database indices

You won't implement these in interviews, but knowing why they exist (to prevent O(n) worst case) is expected.

Real-World Frontend Application

The DOM is a tree: Every HTML element is a node; children are nested elements. DOM traversal APIs (parentNode, firstChild, nextSibling) walk this tree
React Virtual DOM: A massive tree of React elements. The reconciler DFS-traverses the old tree and new tree to find differences
File system explorer: Every folder is an internal node; files are leaves. Expanding a folder in VS Code is tree traversal
Abstract Syntax Tree (AST): Babel, ESLint, TypeScript all parse your code into a tree of nodes before transforming or checking it

Common Mistakes

Mistake	Example	Fix
Only checking node val, not bounds	Validating BST: `if (left.val < node.val)`	Pass min/max bounds recursively
Off-by-one on height vs depth	Mixing edges vs nodes for height	Pick one convention and be consistent
Modifying tree while traversing	In-place delete during traversal	Collect deletions, apply after
Not handling null root	`root.val` when tree is empty	Always check `if (!root) return ...` first

Key Problems to Solve

#	Problem	Pattern	Difficulty
1	Maximum Depth of Binary Tree	Bottom-up DFS	Easy
2	Symmetric Tree	Mirror comparison	Easy
3	Invert Binary Tree	DFS swap	Easy
4	Validate Binary Search Tree	Top-down bounds	Medium
5	Lowest Common Ancestor of BST	Divergence point	Easy
6	Lowest Common Ancestor (general BT)	DFS + combine	Medium
7	Binary Tree Right Side View	Level-order, take last	Medium
8	Kth Smallest Element in BST	Inorder k-th	Medium
9	Path Sum II	DFS backtracking	Medium
10	Construct BST from Preorder	Bounds splitting	Medium
11	Serialize and Deserialize Binary Tree	BFS/DFS encode + decode	Hard
12	Binary Tree Maximum Path Sum	DFS with global max	Hard

50 ← Root (no parent) / \ 30 70 ← Internal nodes (have children) / \ / \ 20 40 60 80 ← Leaf nodes (no children) Terms: Height of tree = 2 (longest root-to-leaf path, counting edges) Depth of node 60 = 2 (root-to-60 edges) Subtree rooted at 30 = {20, 30, 40}

Valid BST: Invalid (8 is in right subtree of 10 but 8 < 10, violating the rule): 10 10 / \ / \ 5 15 5 15 / \ / \ / \ / 3 7 12 20 3 7 8 ← 8 should be left of 10, not right of 15

class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; } } // Insert into BST function insert(root, val) { if (!root) return new TreeNode(val); if (val < root.val) root.left = insert(root.left, val); else if (val > root.val) root.right = insert(root.right, val); // equal: BST typically ignores duplicates (or you choose a side) return root; } // Search BST function search(root, val) { if (!root || root.val === val) return root; return val < root.val ? search(root.left, val) : search(root.right, val); } // Delete from BST (the trickiest operation) function deleteNode(root, val) { if (!root) return null; if (val < root.val) { root.left = deleteNode(root.left, val); } else if (val > root.val) { root.right = deleteNode(root.right, val); } else { // Found the node to delete if (!root.left) return root.right; // no left child → replace with right if (!root.right) return root.left; // no right child → replace with left // Two children: replace val with inorder successor (min of right subtree) let successor = root.right; while (successor.left) successor = successor.left; root.val = successor.val; root.right = deleteNode(root.right, successor.val); } return root; }

Operation

Average (balanced)

Worst (skewed)

Why worst is bad

O(log n)

O(n)

Skewed tree = linked list

Insert

O(log n)

O(n)

Must find correct position

Delete

O(log n)

O(n)

Must find node + rebalance

Inorder traversal

O(n)

Must visit every node

Find min/max

O(log n)

O(n)

Leftmost/rightmost node

Tree: 4 / \ 2 6 / \ / \ 1 3 5 7 Inorder (L → Root → R): 1, 2, 3, 4, 5, 6, 7 ← SORTED! 🎉 Preorder (Root → L → R): 4, 2, 1, 3, 6, 5, 7 ← used to serialize/copy trees Postorder (L → R → Root): 1, 3, 2, 5, 7, 6, 4 ← delete subtrees bottom-up Level-order (BFS by row): 4, 2, 6, 1, 3, 5, 7 ← used for "right side view"

// Recursive traversals (clean but uses O(h) call stack space) function inorder(node, result = []) { if (!node) return result; inorder(node.left, result); result.push(node.val); // ← visit in the middle inorder(node.right, result); return result; } function preorder(node, result = []) { if (!node) return result; result.push(node.val); // ← visit first preorder(node.left, result); preorder(node.right, result); return result; } // Iterative inorder, often required in interviews to avoid stack overflow function inorderIterative(root) { const result = [], stack = []; let curr = root; while (curr || stack.length) { // Go as far left as possible while (curr) { stack.push(curr); curr = curr.left; } curr = stack.pop(); result.push(curr.val); // ← visit curr = curr.right; // ← then go right } return result; } // Level-order (BFS) function levelOrder(root) { if (!root) return []; const result = [], queue = [root]; while (queue.length) { const levelSize = queue.length; const level = []; for (let i = 0; i < levelSize; i++) { const node = queue.shift(); level.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } result.push(level); } return result; }

// Pattern A: Compute something bottom-up (return a value from subtrees) function height(node) { if (!node) return 0; const leftH = height(node.left); const rightH = height(node.right); return 1 + Math.max(leftH, rightH); // combine left + right results } // Pattern B: Carry information top-down (pass parameters down) function isValidBST(node, min = -Infinity, max = Infinity) { if (!node) return true; if (node.val <= min || node.val >= max) return false; return isValidBST(node.left, min, node.val) && // left: tighten max isValidBST(node.right, node.val, max); // right: tighten min } // Pattern C: Path problems with a global variable let maxPathSum = -Infinity; function maxGain(node) { if (!node) return 0; const left = Math.max(0, maxGain(node.left)); // ignore negative gains const right = Math.max(0, maxGain(node.right)); maxPathSum = Math.max(maxPathSum, node.val + left + right); // update global return node.val + Math.max(left, right); // only one branch goes upward }

Structure

Balance Guarantee

Used In

AVL Tree

Height ≤ 1.44 log₂ n

Databases needing fast lookup

Red-Black Tree

Height ≤ 2 log₂(n+1)

C++ std::map, Java TreeMap

B-Tree / B+ Tree

Disk-page-sized nodes, multi-key

File systems, database indices

Mistake

Example

Fix

Only checking node val, not bounds

Validating BST: if (left.val < node.val)

Pass min/max bounds recursively

Off-by-one on height vs depth

Mixing edges vs nodes for height

Pick one convention and be consistent

Modifying tree while traversing

In-place delete during traversal

Collect deletions, apply after

Not handling null root

root.val when tree is empty

Always check if (!root) return ... first

Problem

Pattern

Difficulty

Maximum Depth of Binary Tree

Bottom-up DFS

Easy

Symmetric Tree

Mirror comparison

Easy

Invert Binary Tree

DFS swap

Easy

Validate Binary Search Tree

Top-down bounds

Medium

Lowest Common Ancestor of BST

Divergence point

Easy

Lowest Common Ancestor (general BT)

DFS + combine

Medium

Binary Tree Right Side View

Level-order, take last

Medium

Kth Smallest Element in BST

Inorder k-th

Medium

Path Sum II

DFS backtracking

Medium

Construct BST from Preorder

Bounds splitting

Medium

Serialize and Deserialize Binary Tree

BFS/DFS encode + decode

Hard

Binary Tree Maximum Path Sum

DFS with global max

Hard

Trees & Binary Search Tree