Binary Trees & BSTs

A Tree is a hierarchical data structure consisting of nodes connected by edges. Unlike Arrays or Linked Lists which are linear, a Tree branches out. The top node is called the Root. Nodes with no children are called Leaves.

A Binary Tree is a tree where every node has at most two children, referred to as the left child and the right child.

Memory Layout

A Binary Tree node is very similar to a Doubly Linked List node, except instead of next and prev, the pointers are left and right.

Binary Search Tree (BST)

A Binary Search Tree is a special type of Binary Tree that strictly adheres to the following property for every single node:

1. All nodes in the Left Subtree are strictly less than the node's value.
2. All nodes in the Right Subtree are strictly greater than the node's value.

This property guarantees that searching for an element is mathematically identical to performing a Binary Search on a sorted array!

Time Complexity (BST)

Why is the worst case $O(N)$? If you insert elements into a BST in already-sorted order (e.g., 1, 2, 3, 4, 5), the tree will only grow down the right side. It degrades from a Tree into a Singly Linked List, destroying its $O(\log N)$ search capabilities. To fix this, we use Balanced Trees (AVL, Red-Black) which automatically self-balance.

Tree Traversals

Because trees are non-linear, there isn't just one way to iterate through them. We use Depth-First Search (DFS) traversals:

1. In-Order (Left, Root, Right): Visits nodes in strictly ascending order for a BST.
2. Pre-Order (Root, Left, Right): Used to create a copy of the tree.
3. Post-Order (Left, Right, Root): Used to delete the tree (you must delete children before the parent).

Implementation in Code

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val===undefined ? 0 : val);
    this.left = (left===undefined ? null : left);
    this.right = (right===undefined ? null : right);
  }
}

// 1. Recursive Search in a BST
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  if (root === null || root.val === val) {
    return root;
  }
  
  // Property: Left is smaller, Right is larger
  if (val < root.val) {
    return searchBST(root.left, val);
  } else {
    return searchBST(root.right, val);
  }
}

// 2. In-Order Traversal (Prints sorted values in a BST)
function inorderTraversal(root: TreeNode | null): void {
  if (root !== null) {
    inorderTraversal(root.left);    // 1. Traverse Left
    console.log(root.val);          // 2. Visit Root
    inorderTraversal(root.right);   // 3. Traverse Right
  }
}

Breadth-First Search (Level Order Traversal)

Instead of diving deep into the leaves (DFS), what if we want to explore the tree level by level? We use Breadth-First Search (BFS). BFS uses a Queue under the hood instead of the call stack.

function levelOrderTraversal(root: TreeNode | null): void {
  if (root === null) return;
  
  const queue: TreeNode[] = [root];
  
  while (queue.length > 0) {
    const current = queue.shift()!; // Dequeue front element
    console.log(current.val);
    
    // Enqueue children for the next level
    if (current.left) queue.push(current.left);
    if (current.right) queue.push(current.right);
  }
}