Binary Trees & Binary Search Trees (BST)

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. Hierarchical Tree Structures

A Binary Tree is a non-linear data structure where each node has at most two children (left and right).

2. The BST Ordering Invariant

A Binary Search Tree (BST) enforces a strict ordering rule on every node:

• All values in the left subtree are strictly less than the node's value ($< ext$).
• All values in the right subtree are strictly greater than the node's value ($> ext$).

                 8 (Root)
               /   \
              3     10
             / \      \
            1   6      14
               / \     /
              4   7   13

3. BST Search & Insertion Implementation

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

function searchBST(root, val) {
  if (!root || root.val === val) return root;

  // Search left if target is smaller, right if larger
  return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}

function insertBST(root, val) {
  if (!root) return new TreeNode(val);

  if (val < root.val) {
    root.left = insertBST(root.left, val);
  } else {
    root.right = insertBST(root.right, val);
  }

  return root;
}

4. Performance & Tree Degeneration

• Balanced BST (AVL / Red-Black): Search, insert, and delete take $O(log N)$ time.
• Degenerate Skewed BST (Inserting sorted data $[1, 2, 3, 4, 5]$): Degenerates into a linked list with $O(N)$ linear time!

5. Common Mistakes

• Checking Only Immediate Children: A valid BST requires ALL nodes in the left subtree to be smaller, not just the direct left child! Validate BST with range bounds: isValidBST(node, min, max).

6. Next Steps

Use BSTs for ordered dictionary lookups. Next, let's explore Tree Traversals: Pre-order, In-order, and Post-order!