Day 7: Trees & Binary Search Trees

What You'll Learn Today

• Fundamental tree concepts and terminology
• Binary trees and traversals
• Binary Search Tree (BST) implementation
• BST operations and complexity

---

What Is a Tree?

A tree is a hierarchical data structure where nodes are connected by parent-child relationships.

flowchart TB
    R["Root"] --> A["Node A"]
    R --> B["Node B"]
    A --> C["Leaf C"]
    A --> D["Leaf D"]
    B --> E["Leaf E"]
    B --> F["Node F"]
    F --> G["Leaf G"]
    style R fill:#3b82f6,color:#fff
    style A fill:#8b5cf6,color:#fff
    style B fill:#8b5cf6,color:#fff
    style C fill:#22c55e,color:#fff
    style D fill:#22c55e,color:#fff
    style E fill:#22c55e,color:#fff
    style F fill:#8b5cf6,color:#fff
    style G fill:#22c55e,color:#fff

Terminology

Term	Description
Root	The topmost node
Leaf	A node with no children
Edge	A connection between nodes
Depth	Number of edges from root to a node
Height	Number of edges from a node to its farthest leaf
Subtree	A node and all its descendants

---

Binary Trees

A binary tree is a tree where each node has at most two children (left and right).

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

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

---

Tree Traversals

flowchart TB
    N1["1"] --> N2["2"]
    N1 --> N3["3"]
    N2 --> N4["4"]
    N2 --> N5["5"]
    N3 --> N6["6"]
    N3 --> N7["7"]
    style N1 fill:#3b82f6,color:#fff
    style N2 fill:#8b5cf6,color:#fff
    style N3 fill:#8b5cf6,color:#fff
    style N4 fill:#22c55e,color:#fff
    style N5 fill:#22c55e,color:#fff
    style N6 fill:#22c55e,color:#fff
    style N7 fill:#22c55e,color:#fff

Depth-First Search (DFS)

// Pre-order: Root → Left → Right
function preOrder(node) {
  if (!node) return [];
  return [node.value, ...preOrder(node.left), ...preOrder(node.right)];
}
// [1, 2, 4, 5, 3, 6, 7]

// In-order: Left → Root → Right
function inOrder(node) {
  if (!node) return [];
  return [...inOrder(node.left), node.value, ...inOrder(node.right)];
}
// [4, 2, 5, 1, 6, 3, 7]

// Post-order: Left → Right → Root
function postOrder(node) {
  if (!node) return [];
  return [...postOrder(node.left), ...postOrder(node.right), node.value];
}
// [4, 5, 2, 6, 7, 3, 1]

Breadth-First Search (BFS) / Level-Order

function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}
// [1, 2, 3, 4, 5, 6, 7]

Traversal	Order	Use Case
Pre-order	Root→Left→Right	Copy a tree
In-order	Left→Root→Right	Sorted output from BST
Post-order	Left→Right→Root	Delete a tree
Level-order	Top to bottom, left to right	Shortest path

---

Binary Search Trees (BST)

A Binary Search Tree is a binary tree with these properties:

• All left descendants < parent value
• All right descendants > parent value

flowchart TB
    N8["8"] --> N3["3"]
    N8 --> N10["10"]
    N3 --> N1["1"]
    N3 --> N6["6"]
    N10 --> N9["9"]
    N10 --> N14["14"]
    N6 --> N4["4"]
    N6 --> N7["7"]
    style N8 fill:#3b82f6,color:#fff
    style N3 fill:#8b5cf6,color:#fff
    style N10 fill:#8b5cf6,color:#fff
    style N1 fill:#22c55e,color:#fff
    style N6 fill:#f59e0b,color:#fff
    style N9 fill:#22c55e,color:#fff
    style N14 fill:#22c55e,color:#fff
    style N4 fill:#22c55e,color:#fff
    style N7 fill:#22c55e,color:#fff

BST Implementation

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

  insert(value) {
    const node = new TreeNode(value);
    if (!this.root) {
      this.root = node;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = node;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = node;
          return;
        }
        current = current.right;
      }
    }
  }

  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return current;
      if (value < current.value) current = current.left;
      else current = current.right;
    }
    return null;
  }

  findMin(node = this.root) {
    while (node && node.left) {
      node = node.left;
    }
    return node;
  }

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

  delete(value, node = this.root, parent = null) {
    while (node) {
      if (value < node.value) {
        parent = node;
        node = node.left;
      } else if (value > node.value) {
        parent = node;
        node = node.right;
      } else {
        if (node.left && node.right) {
          const successor = this.findMin(node.right);
          node.value = successor.value;
          this.delete(successor.value, node.right, node);
        } else {
          const child = node.left || node.right;
          if (!parent) this.root = child;
          else if (parent.left === node) parent.left = child;
          else parent.right = child;
        }
        return;
      }
    }
  }

  inOrder(node = this.root) {
    if (!node) return [];
    return [...this.inOrder(node.left), node.value, ...this.inOrder(node.right)];
  }
}

const bst = new BST();
[8, 3, 10, 1, 6, 14, 4, 7, 9].forEach(v => bst.insert(v));
console.log(bst.inOrder()); // [1, 3, 4, 6, 7, 8, 9, 10, 14]
console.log(bst.search(6)); // TreeNode { value: 6, ... }
console.log(bst.findMin()); // TreeNode { value: 1 }

---

BST Time Complexities

Operation	Average	Worst (Skewed)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Traversal	O(n)	O(n)

The worst case occurs when sorted data is inserted sequentially (the tree becomes a linked list).

flowchart TB
    subgraph Balanced["Balanced Tree"]
        B4["4"] --> B2["2"]
        B4 --> B6["6"]
        B2 --> B1["1"]
        B2 --> B3["3"]
        B6 --> B5["5"]
        B6 --> B7["7"]
    end
    subgraph Skewed["Skewed Tree (Worst Case)"]
        S1["1"] --> S2["2"]
        S2 --> S3["3"]
        S3 --> S4["4"]
    end
    style Balanced fill:#22c55e,color:#fff
    style Skewed fill:#ef4444,color:#fff

---

Tree Height and Validation

function height(node) {
  if (!node) return -1;
  return 1 + Math.max(height(node.left), height(node.right));
}

function isValidBST(node, min = -Infinity, max = Infinity) {
  if (!node) return true;
  if (node.value <= min || node.value >= max) return false;
  return (
    isValidBST(node.left, min, node.value) &&
    isValidBST(node.right, node.value, max)
  );
}

---

Practical Example: File System

class FileNode {
  constructor(name, isDirectory = false) {
    this.name = name;
    this.isDirectory = isDirectory;
    this.children = [];
  }

  addChild(node) {
    this.children.push(node);
  }

  print(indent = "") {
    const prefix = this.isDirectory ? "📁 " : "📄 ";
    console.log(indent + prefix + this.name);
    for (const child of this.children) {
      child.print(indent + "  ");
    }
  }
}

const root = new FileNode("src", true);
const components = new FileNode("components", true);
components.addChild(new FileNode("Header.tsx"));
components.addChild(new FileNode("Footer.tsx"));
root.addChild(components);
root.addChild(new FileNode("index.ts"));
root.print();

---

Summary

Concept	Description
Tree	Hierarchical structure with parent-child connections
Binary Tree	Each node has at most two children
BST	Binary tree where left < parent < right
Traversal	Pre-order, in-order, post-order, level-order
Balance	Tree height kept at O(log n)

Key Takeaways

1. In-order traversal of a BST produces sorted output
2. A balanced BST supports O(log n) search, insert, and delete
3. A skewed tree degrades to O(n) — solved by balanced trees
4. Tree traversals are naturally expressed with recursion

---

Practice Problems

Problem 1: Basic

Implement a function to find the maximum depth (height) of a binary tree.

Problem 2: Intermediate

Implement a function to check if a binary tree is symmetric (a mirror of itself).

Challenge

Find the Lowest Common Ancestor (LCA) of two nodes in a BST.

---

References

• Wikipedia - Binary search tree
• Visualgo - BST
• LeetCode - Tree Problems

---

Next up: In Day 8, we'll explore "Heaps & Priority Queues" — data structures that provide fast access to the minimum or maximum value.