Trees & Binary Search Trees

1. What is a Tree?

A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike arrays or linked lists which are linear, trees branch out -- making them perfect for representing hierarchical relationships like file systems, HTML DOM, or organizational charts.

Key Terminology

• Root -- The topmost node (no parent)
• Child -- A node directly connected below another node
• Parent -- A node directly connected above another node
• Leaf -- A node with no children
• Depth -- Distance from the root to a node (root has depth 0)
• Height -- Distance from a node to its deepest leaf (leaves have height 0)
• Subtree -- A node and all its descendants
• Edge -- Connection between a parent and child

Visual Representation

            1            <-- Root (depth 0, height 2)
           / \
          2   3         <-- depth 1
         / \   \
        4   5   6      <-- Leaves (depth 2, height 0)

    Nodes: 6
    Edges: 5  (always n-1 for n nodes)
    Height of tree: 2

Binary Tree

A binary tree is a tree where each node has at most 2 children -- referred to as the left child and right child. This is the most common tree type in interviews.

2. Binary Search Tree (BST)

A Binary Search Tree is a binary tree with an ordering property: for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater.

BST Example

            8
           / \
          3   10
         / \    \
        1   6   14
           / \   /
          4   7 13

    Inorder traversal gives sorted order:
    1, 3, 4, 6, 7, 8, 10, 13, 14

BST Operations & Time Complexity

All operations are O(h) where h is the height. For a balanced tree, h = O(log n). For a skewed tree (essentially a linked list), h = O(n).

    1
     \
      2
       \
        3       <-- Skewed tree: height = n - 1
         \
          4
           \
            5

3. BST Implementation

TreeNode Class

Python
class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

JavaScript
class TreeNode {
    constructor(val = 0) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

Full BST Class -- Python

Python
class BST:
    def __init__(self):
        self.root = None

    # ---- INSERT ----
    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        # if val == node.val, ignore duplicate
        return node

    # ---- SEARCH ----
    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if not node:
            return False
        if val == node.val:
            return True
        elif val < node.val:
            return self._search(node.left, val)
        else:
            return self._search(node.right, val)

    # ---- FIND MIN / MAX ----
    def find_min(self, node=None):
        node = node or self.root
        while node.left:
            node = node.left
        return node.val

    def find_max(self, node=None):
        node = node or self.root
        while node.right:
            node = node.right
        return node.val

    # ---- DELETE ----
    def delete(self, val):
        self.root = self._delete(self.root, val)

    def _delete(self, node, val):
        if not node:
            return None

        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            # Case 1: Leaf node (no children)
            if not node.left and not node.right:
                return None

            # Case 2: One child
            if not node.left:
                return node.right
            if not node.right:
                return node.left

            # Case 3: Two children
            # Find inorder successor (smallest in right subtree)
            successor_val = self.find_min(node.right)
            node.val = successor_val
            node.right = self._delete(node.right, successor_val)

        return node

Full BST Class -- JavaScript

JavaScript
class BST {
    constructor() {
        this.root = null;
    }

    // ---- INSERT ----
    insert(val) {
        this.root = this._insert(this.root, val);
    }

    _insert(node, val) {
        if (!node) return new TreeNode(val);
        if (val < node.val) node.left = this._insert(node.left, val);
        else if (val > node.val) node.right = this._insert(node.right, val);
        return node;
    }

    // ---- SEARCH ----
    search(val) {
        return this._search(this.root, val);
    }

    _search(node, val) {
        if (!node) return false;
        if (val === node.val) return true;
        if (val < node.val) return this._search(node.left, val);
        return this._search(node.right, val);
    }

    // ---- FIND MIN / MAX ----
    findMin(node = this.root) {
        while (node.left) node = node.left;
        return node.val;
    }

    findMax(node = this.root) {
        while (node.right) node = node.right;
        return node.val;
    }

    // ---- DELETE ----
    delete(val) {
        this.root = this._delete(this.root, val);
    }

    _delete(node, val) {
        if (!node) return null;

        if (val < node.val) {
            node.left = this._delete(node.left, val);
        } else if (val > node.val) {
            node.right = this._delete(node.right, val);
        } else {
            // Case 1: Leaf node
            if (!node.left && !node.right) return null;

            // Case 2: One child
            if (!node.left) return node.right;
            if (!node.right) return node.left;

            // Case 3: Two children
            const successorVal = this.findMin(node.right);
            node.val = successorVal;
            node.right = this._delete(node.right, successorVal);
        }
        return node;
    }
}

Understanding Delete -- The Three Cases

  Delete 4:

      5               5
     / \     -->    / \
    3   7          3   7
   /
  4  (removed)

  Delete 3 (has left child only):

      5               5
     / \     -->    / \
    3   7          2   7
   /
  2

  Delete 5 (root, has two children):

      5          Step 1: Find inorder       6
     / \        successor = 6              / \
    3   8      Step 2: Copy 6 to root     3   8
       / \     Step 3: Delete 6               \
      6   9     from right subtree           9
       \
        7

4. Tree Traversals

Tree traversal means visiting every node exactly once. There are two main approaches: Depth-First Search (DFS) and Breadth-First Search (BFS).

Inorder Traversal (Left, Root, Right)

Visit left subtree, then current node, then right subtree. For a BST, this gives values in sorted ascending order.

    Inorder walk-through:

        4
       / \
      2   6
     / \ / \
    1  3 5  7

    Visit order: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7  (sorted!)

Python
# Recursive Inorder
def inorder_recursive(root):
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)       # Left
        result.append(node.val)  # Root
        dfs(node.right)      # Right
    dfs(root)
    return result

# Iterative Inorder (using stack)
def inorder_iterative(root):
    result = []
    stack = []
    current = root
    while current or stack:
        # Go as far left as possible
        while current:
            stack.append(current)
            current = current.left
        # Process node
        current = stack.pop()
        result.append(current.val)
        # Move to right subtree
        current = current.right
    return result

JavaScript
// Recursive Inorder
function inorderRecursive(root) {
    const result = [];
    function dfs(node) {
        if (!node) return;
        dfs(node.left);           // Left
        result.push(node.val);    // Root
        dfs(node.right);          // Right
    }
    dfs(root);
    return result;
}

// Iterative Inorder (using stack)
function inorderIterative(root) {
    const result = [];
    const stack = [];
    let current = root;
    while (current || stack.length) {
        while (current) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.push(current.val);
        current = current.right;
    }
    return result;
}

Preorder Traversal (Root, Left, Right)

Visit current node first, then left subtree, then right subtree. Useful for copying/serializing a tree.

    Preorder walk-through:

        4
       / \
      2   6
     / \ / \
    1  3 5  7

    Visit order: 4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7

Python
# Recursive Preorder
def preorder_recursive(root):
    result = []
    def dfs(node):
        if not node:
            return
        result.append(node.val)  # Root
        dfs(node.left)           # Left
        dfs(node.right)          # Right
    dfs(root)
    return result

# Iterative Preorder (using stack)
def preorder_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

JavaScript
// Recursive Preorder
function preorderRecursive(root) {
    const result = [];
    function dfs(node) {
        if (!node) return;
        result.push(node.val);    // Root
        dfs(node.left);           // Left
        dfs(node.right);          // Right
    }
    dfs(root);
    return result;
}

// Iterative Preorder (using stack)
function preorderIterative(root) {
    if (!root) return [];
    const result = [];
    const stack = [root];
    while (stack.length) {
        const node = stack.pop();
        result.push(node.val);
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
    return result;
}

Postorder Traversal (Left, Right, Root)

Visit left subtree, then right subtree, then current node. Useful for deletion (delete children before parent) and evaluating expression trees.

    Postorder walk-through:

        4
       / \
      2   6
     / \ / \
    1  3 5  7

    Visit order: 1 -> 3 -> 2 -> 5 -> 7 -> 6 -> 4

Python
# Recursive Postorder
def postorder_recursive(root):
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)           # Left
        dfs(node.right)          # Right
        result.append(node.val)  # Root
    dfs(root)
    return result

# Iterative Postorder (using two stacks)
def postorder_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]  # Reverse the result

JavaScript
// Recursive Postorder
function postorderRecursive(root) {
    const result = [];
    function dfs(node) {
        if (!node) return;
        dfs(node.left);           // Left
        dfs(node.right);          // Right
        result.push(node.val);    // Root
    }
    dfs(root);
    return result;
}

// Iterative Postorder
function postorderIterative(root) {
    if (!root) return [];
    const result = [];
    const stack = [root];
    while (stack.length) {
        const node = stack.pop();
        result.push(node.val);
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }
    return result.reverse();
}

Level Order Traversal (BFS)

Visit nodes level by level, from left to right. Uses a queue instead of a stack.

    Level order walk-through:

        4           Level 0: [4]
       / \
      2   6        Level 1: [2, 6]
     / \ / \
    1  3 5  7     Level 2: [1, 3, 5, 7]

    Result: [[4], [2, 6], [1, 3, 5, 7]]

Python
from collections import deque

def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result

JavaScript
function levelOrder(root) {
    if (!root) return [];

    const result = [];
    const queue = [root];

    while (queue.length) {
        const levelSize = queue.length;
        const currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        result.push(currentLevel);
    }

    return result;
}

5. Common Tree Problems & Patterns

Maximum Depth of Binary Tree

Find the maximum depth (number of nodes along the longest path from root to the farthest leaf). This is the classic recursive tree problem.

Python
def max_depth(root):
    if not root:
        return 0
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    return 1 + max(left_depth, right_depth)

JavaScript
function maxDepth(root) {
    if (!root) return 0;
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    return 1 + Math.max(leftDepth, rightDepth);
}

    Walk-through:

        3        maxDepth(3) = 1 + max(2, 1) = 3
       / \
      9   20     maxDepth(9) = 1 + max(0, 0) = 1  |  maxDepth(20) = 1 + max(1, 1) = 2
          / \
         15  7    maxDepth(15) = 1  |  maxDepth(7) = 1

    Answer: 3

Validate Binary Search Tree

Check if a binary tree is a valid BST. The trick: each node must be within a valid range (min, max), not just compared to its immediate parent.

       5
      / \
     1   7
        / \
       3   8    <-- 3 is less than 5, violates BST!
                    (3 < 7 passes local check but 3 < 5 fails)

Python
# Approach 1: Min/Max Range
def is_valid_bst(root):
    def validate(node, low=float('-inf'), high=float('inf')):
        if not node:
            return True
        if node.val <= low or node.val >= high:
            return False
        return (validate(node.left, low, node.val) and
                validate(node.right, node.val, high))
    return validate(root)

# Approach 2: Inorder traversal should be sorted
def is_valid_bst_inorder(root):
    prev = [float('-inf')]
    def inorder(node):
        if not node:
            return True
        if not inorder(node.left):
            return False
        if node.val <= prev[0]:
            return False
        prev[0] = node.val
        return inorder(node.right)
    return inorder(root)

JavaScript
// Approach 1: Min/Max Range
function isValidBST(root) {
    function validate(node, low = -Infinity, high = Infinity) {
        if (!node) return true;
        if (node.val <= low || node.val >= high) return false;
        return validate(node.left, low, node.val) &&
               validate(node.right, node.val, high);
    }
    return validate(root);
}

// Approach 2: Inorder traversal should be sorted
function isValidBSTInorder(root) {
    let prev = -Infinity;
    function inorder(node) {
        if (!node) return true;
        if (!inorder(node.left)) return false;
        if (node.val <= prev) return false;
        prev = node.val;
        return inorder(node.right);
    }
    return inorder(root);
}

Invert Binary Tree

Swap left and right children at every node. The famous question that Max Howell (Homebrew creator) couldn't solve in a Google interview.

    Before:            After:

        4                 4
       / \               / \
      2   7             7   2
     / \ / \           / \ / \
    1  3 6  9         9  6 3  1

Python
def invert_tree(root):
    if not root:
        return None
    # Swap left and right
    root.left, root.right = root.right, root.left
    # Recursively invert subtrees
    invert_tree(root.left)
    invert_tree(root.right)
    return root

JavaScript
function invertTree(root) {
    if (!root) return null;
    // Swap left and right
    [root.left, root.right] = [root.right, root.left];
    // Recursively invert subtrees
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

Lowest Common Ancestor of a BST

Find the lowest node that is an ancestor of both p and q. In a BST, we can leverage the ordering property.

Python
def lowest_common_ancestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left       # Both in left subtree
        elif p.val > root.val and q.val > root.val:
            root = root.right      # Both in right subtree
        else:
            return root            # Split point = LCA

JavaScript
function lowestCommonAncestor(root, p, q) {
    while (root) {
        if (p.val < root.val && q.val < root.val) {
            root = root.left;       // Both in left subtree
        } else if (p.val > root.val && q.val > root.val) {
            root = root.right;      // Both in right subtree
        } else {
            return root;            // Split point = LCA
        }
    }
}

    Example: Find LCA of 2 and 8

        6       <-- 2 < 6 and 8 > 6 -> split! LCA = 6
       / \
      2   8
     / \ / \
    0  4 7  9

    Example: Find LCA of 2 and 4

        6       <-- 2 < 6 and 4 < 6 -> go left
       / \
      2   8     <-- 2 == 2 -> split! LCA = 2
     / \ / \
    0  4 7  9

6. LeetCode Problems

Full Solutions

104. Maximum Depth of Binary Tree

Python
# LeetCode 104 - Maximum Depth of Binary Tree
# Time: O(n)  Space: O(h) where h = height (recursion stack)

class Solution:
    def maxDepth(self, root) -> int:
        if not root:
            return 0
        return 1 + max(
            self.maxDepth(root.left),
            self.maxDepth(root.right)
        )

JavaScript
// LeetCode 104 - Maximum Depth of Binary Tree
// Time: O(n)  Space: O(h)

var maxDepth = function(root) {
    if (!root) return 0;
    return 1 + Math.max(
        maxDepth(root.left),
        maxDepth(root.right)
    );
};

226. Invert Binary Tree

Python
# LeetCode 226 - Invert Binary Tree
# Time: O(n)  Space: O(h)

class Solution:
    def invertTree(self, root):
        if not root:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

JavaScript
// LeetCode 226 - Invert Binary Tree
// Time: O(n)  Space: O(h)

var invertTree = function(root) {
    if (!root) return null;
    [root.left, root.right] = [root.right, root.left];
    invertTree(root.left);
    invertTree(root.right);
    return root;
};

102. Binary Tree Level Order Traversal

Python
# LeetCode 102 - Binary Tree Level Order Traversal
# Time: O(n)  Space: O(n)

from collections import deque

class Solution:
    def levelOrder(self, root):
        if not root:
            return []

        result = []
        queue = deque([root])

        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)

        return result

JavaScript
// LeetCode 102 - Binary Tree Level Order Traversal
// Time: O(n)  Space: O(n)

var levelOrder = function(root) {
    if (!root) return [];

    const result = [];
    const queue = [root];

    while (queue.length) {
        const level = [];
        const size = queue.length;

        for (let i = 0; i < size; 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;
};

7. Balanced Trees

A balanced BST maintains a height of O(log n), guaranteeing efficient operations. Without balancing, a BST can degrade to O(n) for all operations.

Why Balance Matters

AVL Trees

AVL trees maintain balance by ensuring the height difference between left and right subtrees of any node is at most 1. After every insert/delete, rotations are performed if the balance factor (|height(left) - height(right)|) exceeds 1.

• Balance factor = height(left) - height(right)
• Valid range: -1, 0, or 1
• Four rotation types: Left, Right, Left-Right, Right-Left
• Strictly balanced -- slightly faster lookups than Red-Black trees

Red-Black Trees

Red-Black trees use node coloring (red or black) and a set of rules to maintain approximate balance. They are less strictly balanced than AVL trees but have faster insertions and deletions.

• Every node is red or black
• Root is always black
• No two consecutive red nodes
• Every path from root to null has the same number of black nodes
• Used in: Java TreeMap, C++ std::map, Linux kernel

8. Practice Quiz

        10
       /  \
      5    15
     / \     \
    3   7    20