Advanced Data Structures

Trees & Binary Trees

Binary Trees

A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and right child.

🌳 Real-Life Analogy:

Think of a family tree where each person can have at most two children. The tree starts with one ancestor (root) and branches down through generations.

TypeScript

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

class BinaryTree {
    root: TreeNode | null;
    
    constructor() {
        this.root = null;
    }
    
    // Insert a value into the tree
    insert(val: number): void {
        if (!this.root) {
            this.root = new TreeNode(val);
            return;
        }
        
        this.insertNode(this.root, val);
    }
    
    private insertNode(node: TreeNode, val: number): void {
        if (val < node.val) {
            if (!node.left) {
                node.left = new TreeNode(val);
            } else {
                this.insertNode(node.left, val);
            }
        } else {
            if (!node.right) {
                node.right = new TreeNode(val);
            } else {
                this.insertNode(node.right, val);
            }
        }
    }
    
    // In-order traversal (left, root, right)
    inorderTraversal(node: TreeNode | null = this.root): number[] {
        const result: number[] = [];
        if (node) {
            result.push(...this.inorderTraversal(node.left));
            result.push(node.val);
            result.push(...this.inorderTraversal(node.right));
        }
        return result;
    }
}

Python

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

class BinaryTree:
    def __init__(self):
        self.root = None
    
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
            return
        
        self._insert_node(self.root, val)
    
    def _insert_node(self, node, val):
        if val < node.val:
            if not node.left:
                node.left = TreeNode(val)
            else:
                self._insert_node(node.left, val)
        else:
            if not node.right:
                node.right = TreeNode(val)
            else:
                self._insert_node(node.right, val)
    
    def inorder_traversal(self, node=None):
        if node is None:
            node = self.root
        
        result = []
        if node:
            result.extend(self.inorder_traversal(node.left))
            result.append(node.val)
            result.extend(self.inorder_traversal(node.right))
        
        return result

OCaml

type 'a tree = 
  | Empty 
  | Node of 'a * 'a tree * 'a tree

let rec insert x = function
  | Empty -> Node (x, Empty, Empty)
  | Node (y, left, right) ->
      if x < y then Node (y, insert x left, right)
      else Node (y, left, insert x right)

let rec inorder = function
  | Empty -> []
  | Node (x, left, right) ->
      (inorder left) @ [x] @ (inorder right)

(* Example usage *)
let tree = Empty
let tree = insert 5 tree
let tree = insert 3 tree
let tree = insert 7 tree
let result = inorder tree (* [3; 5; 7] *)

🎯 Key Properties:

Height: Maximum depth from root to leaf
Balanced: Height difference between subtrees ≤ 1
Complete: All levels filled except possibly the last
Perfect: All internal nodes have two children

Operation	Time Complexity	Space Complexity	Notes
Insert	O(log n)	O(1)	With position tracking
Extract Min	O(log n)	O(1)	Update position map
Delete by ID	O(log n)	O(1)	Key advantage over standard heap
Update Value	O(log n)	O(1)	Decrease/increase key operations
Contains Check	O(1)	O(1)	Hash map lookup

Average Case Worst Case Search O(log n) O(n) Insert O(log n) O(n) Delete O(log n) O(n)

Lowest Common Ancestor (LCA) Variations

The Lowest Common Ancestor of two nodes in a tree is the deepest node that has both nodes as descendants. Different tree types and constraints require different approaches.

👨‍👩‍👧‍👦 Real-Life Analogy:

In a family tree, the LCA of two cousins is their closest common ancestor - perhaps their grandparent. Different family relationships require different strategies to trace back to common relatives.

TypeScript

class LCAAlgorithms {
    // Method 1: Binary Search Tree - O(h) time
    lcaBST(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
        if (!root) return null;
        
        // Both nodes are in left subtree
        if (p.val < root.val && q.val < root.val) {
            return this.lcaBST(root.left, p, q);
        }
        
        // Both nodes are in right subtree  
        if (p.val > root.val && q.val > root.val) {
            return this.lcaBST(root.right, p, q);
        }
        
        // Split case: one node on each side (or one is root)
        return root;
    }
    
    // Method 2: Binary Tree without Parent Pointers - O(n) time
    lcaBinaryTree(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
        if (!root || root === p || root === q) {
            return root;
        }
        
        const left = this.lcaBinaryTree(root.left, p, q);
        const right = this.lcaBinaryTree(root.right, p, q);
        
        // If both children return non-null, this is the LCA
        if (left && right) {
            return root;
        }
        
        // Return whichever child found a target node
        return left || right;
    }
    
    // Method 3: Path-based approach - O(n) time, O(h) space
    lcaWithPaths(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
        const pathToP: TreeNode[] = [];
        const pathToQ: TreeNode[] = [];
        
        if (!this.findPath(root, p, pathToP) || !this.findPath(root, q, pathToQ)) {
            return null;
        }
        
        // Find last common node in both paths
        let lca: TreeNode | null = null;
        let i = 0;
        while (i < pathToP.length && i < pathToQ.length && pathToP[i] === pathToQ[i]) {
            lca = pathToP[i];
            i++;
        }
        
        return lca;
    }
    
    private findPath(root: TreeNode | null, target: TreeNode, path: TreeNode[]): boolean {
        if (!root) return false;
        
        path.push(root);
        
        if (root === target) {
            return true;
        }
        
        if (this.findPath(root.left, target, path) || this.findPath(root.right, target, path)) {
            return true;
        }
        
        path.pop(); // Backtrack
        return false;
    }
}

Python

class LCAAlgorithms:
    # Method 1: Binary Search Tree - O(h) time
    def lca_bst(self, root, p, q):
        if not root:
            return None
        
        # Both nodes are in left subtree
        if p.val < root.val and q.val < root.val:
            return self.lca_bst(root.left, p, q)
        
        # Both nodes are in right subtree
        if p.val > root.val and q.val > root.val:
            return self.lca_bst(root.right, p, q)
        
        # Split case: one node on each side (or one is root)
        return root
    
    # Method 2: Binary Tree without Parent Pointers - O(n) time
    def lca_binary_tree(self, root, p, q):
        if not root or root == p or root == q:
            return root
        
        left = self.lca_binary_tree(root.left, p, q)
        right = self.lca_binary_tree(root.right, p, q)
        
        # If both children return non-null, this is the LCA
        if left and right:
            return root
        
        # Return whichever child found a target node
        return left or right
    
    # Method 3: Path-based approach - O(n) time, O(h) space
    def lca_with_paths(self, root, p, q):
        path_to_p = []
        path_to_q = []
        
        if not self._find_path(root, p, path_to_p) or not self._find_path(root, q, path_to_q):
            return None
        
        # Find last common node in both paths
        lca = None
        i = 0
        while (i < len(path_to_p) and i < len(path_to_q) and 
               path_to_p[i] == path_to_q[i]):
            lca = path_to_p[i]
            i += 1
        
        return lca
    
    def _find_path(self, root, target, path):
        if not root:
            return False
        
        path.append(root)
        
        if root == target:
            return True
        
        if (self._find_path(root.left, target, path) or 
            self._find_path(root.right, target, path)):
            return True
        
        path.pop()  # Backtrack
        return False

OCaml

type tree = Empty | Node of int * tree * tree

module LCAAlgorithms = struct
  (* Method 1: Binary Search Tree - O(h) time *)
  let rec lca_bst root p q =
    match root with
    | Empty -> None
    | Node (val, left, right) ->
        if p < val && q < val then
          lca_bst left p q
        else if p > val && q > val then
          lca_bst right p q
        else
          Some val (* Split case *)
  
  (* Method 2: Binary Tree - O(n) time *)
  let rec lca_binary_tree root p q =
    match root with
    | Empty -> None
    | Node (val, left, right) ->
        if val = p || val = q then Some val
        else
          let left_result = lca_binary_tree left p q in
          let right_result = lca_binary_tree right p q in
          match left_result, right_result with
          | Some _, Some _ -> Some val (* Both children found targets *)
          | Some x, None -> Some x
          | None, Some x -> Some x
          | None, None -> None
  
  (* Method 3: Path-based approach *)
  let lca_with_paths root p q =
    let rec find_path target path = function
      | Empty -> (false, path)
      | Node (val, left, right) ->
          let new_path = val :: path in
          if val = target then (true, new_path)
          else
            let (found_left, path_left) = find_path target new_path left in
            if found_left then (true, path_left)
            else find_path target new_path right
    in
    
    let (found_p, path_p) = find_path p [] root in
    let (found_q, path_q) = find_path q [] root in
    
    if not found_p || not found_q then None
    else
      let rec find_common_ancestor p_path q_path last_common =
        match p_path, q_path with
        | [], _ | _, [] -> last_common
        | p_head :: p_tail, q_head :: q_tail ->
            if p_head = q_head then
              find_common_ancestor p_tail q_tail (Some p_head)
            else
              last_common
      in
      
      find_common_ancestor (List.rev path_p) (List.rev path_q) None
end

Method	Tree Type	Time Complexity	Space Complexity
BST Approach	Binary Search Tree	O(h)	O(h)
Standard Approach	Any Binary Tree	O(n)	O(h)
Path-based	Any Binary Tree	O(n)	O(h)

Binary Tree Maximum Path Sum

Find the maximum sum of any path in a binary tree. A path can start and end at any nodes and doesn't need to pass through the root. This is a classic tree recursion problem with global state tracking.

🛤️ Real-Life Analogy:

Think of hiking through a mountain range where each peak has a value (positive or negative). You want to find the most valuable route between any two points, which might go through valleys (negative values) to reach higher peaks.

TypeScript

class MaxPathSum {
    // Standard Maximum Path Sum
    maxPathSum(root: TreeNode | null): number {
        let maxSum = -Infinity;
        
        const maxGain = (node: TreeNode | null): number => {
            if (!node) return 0;
            
            // Recursively get max gain from left and right subtrees
            // Only take positive gains
            const leftGain = Math.max(maxGain(node.left), 0);
            const rightGain = Math.max(maxGain(node.right), 0);
            
            // Current path sum including this node as highest point
            const currentPathSum = node.val + leftGain + rightGain;
            
            // Update global maximum
            maxSum = Math.max(maxSum, currentPathSum);
            
            // Return max gain if we continue the path through this node
            return node.val + Math.max(leftGain, rightGain);
        };
        
        maxGain(root);
        return maxSum;
    }
    
    // Maximum Path Sum with constraint: path must include root
    maxPathSumThroughRoot(root: TreeNode | null): number {
        if (!root) return 0;
        
        const maxPathDown = (node: TreeNode | null): number => {
            if (!node) return 0;
            
            const leftMax = Math.max(maxPathDown(node.left), 0);
            const rightMax = Math.max(maxPathDown(node.right), 0);
            
            return node.val + Math.max(leftMax, rightMax);
        };
        
        const leftMax = Math.max(maxPathDown(root.left), 0);
        const rightMax = Math.max(maxPathDown(root.right), 0);
        
        return root.val + leftMax + rightMax;
    }
    
    // Maximum Path Sum with length constraint
    maxPathSumWithLength(root: TreeNode | null, maxLength: number): number {
        let maxSum = -Infinity;
        
        const dfs = (node: TreeNode | null, length: number): number => {
            if (!node || length <= 0) return 0;
            
            // If this is the last node we can include
            if (length === 1) {
                maxSum = Math.max(maxSum, node.val);
                return node.val;
            }
            
            const leftMax = dfs(node.left, length - 1);
            const rightMax = dfs(node.right, length - 1);
            
            // Three options for paths through this node:
            // 1. Just this node
            maxSum = Math.max(maxSum, node.val);
            
            // 2. This node + left path
            if (node.left) {
                maxSum = Math.max(maxSum, node.val + leftMax);
            }
            
            // 3. This node + right path
            if (node.right) {
                maxSum = Math.max(maxSum, node.val + rightMax);
            }
            
            // 4. This node + both paths (if length allows)
            if (node.left && node.right && length >= 3) {
                maxSum = Math.max(maxSum, node.val + leftMax + rightMax);
            }
            
            // Return best single path through this node
            return node.val + Math.max(leftMax, rightMax, 0);
        };
        
        dfs(root, maxLength);
        return maxSum;
    }
    
    // Maximum Path Sum between two specific nodes
    maxPathSumBetweenNodes(root: TreeNode | null, start: TreeNode, end: TreeNode): number {
        let pathSum = 0;
        let found = false;
        
        const findPath = (node: TreeNode | null, target: TreeNode, path: TreeNode[]): boolean => {
            if (!node) return false;
            
            path.push(node);
            
            if (node === target) return true;
            
            if (findPath(node.left, target, path) || findPath(node.right, target, path)) {
                return true;
            }
            
            path.pop();
            return false;
        };
        
        const pathToStart: TreeNode[] = [];
        const pathToEnd: TreeNode[] = [];
        
        if (!findPath(root, start, pathToStart) || !findPath(root, end, pathToEnd)) {
            return 0; // Nodes not found
        }
        
        // Find LCA
        let lca: TreeNode | null = null;
        let i = 0;
        while (i < pathToStart.length && i < pathToEnd.length && pathToStart[i] === pathToEnd[i]) {
            lca = pathToStart[i];
            i++;
        }
        
        if (!lca) return 0;
        
        // Calculate path sum
        let sum = 0;
        
        // Sum from start to LCA (excluding LCA)
        for (let j = pathToStart.length - 1; j >= i; j--) {
            sum += pathToStart[j].val;
        }
        
        // Add LCA
        sum += lca.val;
        
        // Sum from LCA to end (excluding LCA)
        for (let j = i; j < pathToEnd.length; j++) {
            sum += pathToEnd[j].val;
        }
        
        return sum;
    }
}

Python

class MaxPathSum:
    def __init__(self):
        self.max_sum = float('-inf')
    
    # Standard Maximum Path Sum
    def max_path_sum(self, root):
        self.max_sum = float('-inf')
        
        def max_gain(node):
            if not node:
                return 0
            
            # Recursively get max gain from left and right subtrees
            # Only take positive gains
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)
            
            # Current path sum including this node as highest point
            current_path_sum = node.val + left_gain + right_gain
            
            # Update global maximum
            self.max_sum = max(self.max_sum, current_path_sum)
            
            # Return max gain if we continue the path through this node
            return node.val + max(left_gain, right_gain)
        
        max_gain(root)
        return self.max_sum
    
    # Maximum Path Sum with constraint: path must include root
    def max_path_sum_through_root(self, root):
        if not root:
            return 0
        
        def max_path_down(node):
            if not node:
                return 0
            
            left_max = max(max_path_down(node.left), 0)
            right_max = max(max_path_down(node.right), 0)
            
            return node.val + max(left_max, right_max)
        
        left_max = max(max_path_down(root.left), 0)
        right_max = max(max_path_down(root.right), 0)
        
        return root.val + left_max + right_max
    
    # Maximum Path Sum with length constraint
    def max_path_sum_with_length(self, root, max_length):
        self.max_sum = float('-inf')
        
        def dfs(node, length):
            if not node or length <= 0:
                return 0
            
            # If this is the last node we can include
            if length == 1:
                self.max_sum = max(self.max_sum, node.val)
                return node.val
            
            left_max = dfs(node.left, length - 1)
            right_max = dfs(node.right, length - 1)
            
            # Three options for paths through this node:
            # 1. Just this node
            self.max_sum = max(self.max_sum, node.val)
            
            # 2. This node + left path
            if node.left:
                self.max_sum = max(self.max_sum, node.val + left_max)
            
            # 3. This node + right path
            if node.right:
                self.max_sum = max(self.max_sum, node.val + right_max)
            
            # 4. This node + both paths (if length allows)
            if node.left and node.right and length >= 3:
                self.max_sum = max(self.max_sum, node.val + left_max + right_max)
            
            # Return best single path through this node
            return node.val + max(left_max, right_max, 0)
        
        dfs(root, max_length)
        return self.max_sum
    
    # Maximum Sum Root to Leaf Path
    def max_root_to_leaf_sum(self, root):
        if not root:
            return 0
        
        if not root.left and not root.right:
            return root.val
        
        left_sum = float('-inf')
        right_sum = float('-inf')
        
        if root.left:
            left_sum = self.max_root_to_leaf_sum(root.left)
        
        if root.right:
            right_sum = self.max_root_to_leaf_sum(root.right)
        
        return root.val + max(left_sum, right_sum)

OCaml

type tree = Empty | Node of int * tree * tree

module MaxPathSum = struct
  let max_path_sum root =
    let max_sum = ref (min_int) in
    
    let rec max_gain = function
      | Empty -> 0
      | Node (value, left, right) ->
          (* Get max gain from subtrees, ignore negative gains *)
          let left_gain = max 0 (max_gain left) in
          let right_gain = max 0 (max_gain right) in
          
          (* Current path sum through this node *)
          let current_path_sum = value + left_gain + right_gain in
          
          (* Update global maximum *)
          max_sum := max !max_sum current_path_sum;
          
          (* Return max gain continuing through this node *)
          value + max left_gain right_gain
    in
    
    let _ = max_gain root in
    !max_sum
  
  let max_path_sum_through_root = function
    | Empty -> 0
    | Node (value, left, right) ->
        let rec max_path_down = function
          | Empty -> 0
          | Node (v, l, r) ->
              let left_max = max 0 (max_path_down l) in
              let right_max = max 0 (max_path_down r) in
              v + max left_max right_max
        in
        
        let left_max = max 0 (max_path_down left) in
        let right_max = max 0 (max_path_down right) in
        
        value + left_max + right_max
  
  let max_root_to_leaf_sum = function
    | Empty -> 0
    | Node (value, Empty, Empty) -> value
    | Node (value, left, right) ->
        let left_sum = 
          match left with
          | Empty -> min_int
          | tree -> max_root_to_leaf_sum tree
        in
        let right_sum = 
          match right with
          | Empty -> min_int
          | tree -> max_root_to_leaf_sum tree
        in
        value + max left_sum right_sum
end

🔑 Key Insights:

Global vs Local: Track global maximum while computing local maximums
Positive Gains: Only include positive path contributions
Path Definition: Path can start and end at any nodes
State Management: Use closure/global variable for max tracking

Variant	Time Complexity	Space Complexity	Constraint
Standard	O(n)	O(h)	Any path
Through Root	O(n)	O(h)	Must include root
Root to Leaf	O(n)	O(h)	Root to leaf only

Validate Binary Search Tree

Determine if a binary tree is a valid Binary Search Tree (BST). A valid BST has the property that for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.

📏 Real-Life Analogy:

Think of organizing a library where books must be arranged by call numbers. Each shelf section has a valid range, and every book must be within its section's range and properly ordered relative to neighboring books.

TypeScript

class BSTValidator {
    // Method 1: Bounds Checking (Most Efficient) - O(n) time, O(h) space
    isValidBST(root: TreeNode | null): boolean {
        const validate = (node: TreeNode | null, min: number, max: number): boolean => {
            if (!node) return true;
            
            // Current node must be within bounds
            if (node.val <= min || node.val >= max) {
                return false;
            }
            
            // Recursively validate subtrees with updated bounds
            return validate(node.left, min, node.val) && 
                   validate(node.right, node.val, max);
        };
        
        return validate(root, -Infinity, Infinity);
    }
    
    // Method 2: In-order Traversal with Early Termination
    isValidBSTInorder(root: TreeNode | null): boolean {
        let prev: number | null = null;
        
        const validate = (node: TreeNode | null): boolean => {
            if (!node) return true;
            
            // Check left subtree
            if (!validate(node.left)) return false;
            
            // Check current node
            if (prev !== null && node.val <= prev) {
                return false;
            }
            prev = node.val;
            
            // Check right subtree
            return validate(node.right);
        };
        
        return validate(root);
    }
}

Python

class BSTValidator:
    # Method 1: Bounds Checking (Most Efficient) - O(n) time, O(h) space
    def is_valid_bst(self, root):
        def validate(node, min_val, max_val):
            if not node:
                return True
            
            # Current node must be within bounds
            if node.val <= min_val or node.val >= max_val:
                return False
            
            # Recursively validate subtrees with updated bounds
            return (validate(node.left, min_val, node.val) and 
                    validate(node.right, node.val, max_val))
        
        return validate(root, float('-inf'), float('inf'))
    
    # Method 2: In-order Traversal with Early Termination
    def is_valid_bst_inorder(self, root):
        self.prev = None
        
        def validate(node):
            if not node:
                return True
            
            # Check left subtree
            if not validate(node.left):
                return False
            
            # Check current node
            if self.prev is not None and node.val <= self.prev:
                return False
            self.prev = node.val
            
            # Check right subtree
            return validate(node.right)
        
        return validate(root)

OCaml

type tree = Empty | Node of int * tree * tree

module BSTValidator = struct
  (* Method 1: Bounds Checking *)
  let is_valid_bst tree =
    let rec validate node min_val max_val =
      match node with
      | Empty -> true
      | Node (value, left, right) ->
          value > min_val && value < max_val &&
          validate left min_val value &&
          validate right value max_val
    in
    
    validate tree min_int max_int
  
  (* Method 2: In-order Traversal *)
  let is_valid_bst_inorder tree =
    let prev = ref None in
    
    let rec validate = function
      | Empty -> true
      | Node (value, left, right) ->
          (* Check left subtree *)
          if not (validate left) then false
          else
            (* Check current node *)
            match !prev with
            | Some p when value <= p -> false
            | _ -> 
                prev := Some value;
                validate right
    in
    
    validate tree
end

Method	Time Complexity	Space Complexity	Early Termination
Bounds Checking	O(n)	O(h)	Yes
In-order Optimized	O(n)	O(h)	Yes

Tree Reconstruction Problems

Reconstruct binary trees from various traversal sequences or partial information. These problems test understanding of tree properties and traversal relationships.

🧩 Real-Life Analogy:

Think of reconstructing a building's floor plan from different views (front, side, top). Each traversal gives you a different "view" of the tree structure, and you need to combine them to rebuild the original.

TypeScript

class TreeReconstruction {
    // Method 1: Build from Preorder and Inorder
    buildTreePreorderInorder(preorder: number[], inorder: number[]): TreeNode | null {
        if (preorder.length === 0 || inorder.length === 0) return null;
        
        // Create map for O(1) inorder lookups
        const inorderMap = new Map();
        for (let i = 0; i < inorder.length; i++) {
            inorderMap.set(inorder[i], i);
        }
        
        let preorderIndex = 0;
        
        const build = (inorderStart: number, inorderEnd: number): TreeNode | null => {
            if (inorderStart > inorderEnd) return null;
            
            const rootVal = preorder[preorderIndex++];
            const root = new TreeNode(rootVal);
            
            const inorderRootIndex = inorderMap.get(rootVal)!;
            
            // Build left subtree first (preorder: root, left, right)
            root.left = build(inorderStart, inorderRootIndex - 1);
            root.right = build(inorderRootIndex + 1, inorderEnd);
            
            return root;
        };
        
        return build(0, inorder.length - 1);
    }
    
    // Method 2: Build BST from Preorder Only
    buildBSTFromPreorder(preorder: number[]): TreeNode | null {
        if (preorder.length === 0) return null;
        
        let index = 0;
        
        const build = (min: number, max: number): TreeNode | null => {
            if (index >= preorder.length) return null;
            
            const val = preorder[index];
            if (val < min || val > max) return null;
            
            index++;
            const root = new TreeNode(val);
            
            // Build left subtree with updated max bound
            root.left = build(min, val);
            // Build right subtree with updated min bound
            root.right = build(val, max);
            
            return root;
        };
        
        return build(-Infinity, Infinity);
    }
    
    // Method 3: Build from Level Order Traversal
    buildTreeFromLevelOrder(levelorder: (number | null)[]): TreeNode | null {
        if (levelorder.length === 0 || levelorder[0] === null) return null;
        
        const root = new TreeNode(levelorder[0]!);
        const queue: TreeNode[] = [root];
        let i = 1;
        
        while (queue.length > 0 && i < levelorder.length) {
            const node = queue.shift()!;
            
            // Left child
            if (i < levelorder.length && levelorder[i] !== null) {
                node.left = new TreeNode(levelorder[i]!);
                queue.push(node.left);
            }
            i++;
            
            // Right child
            if (i < levelorder.length && levelorder[i] !== null) {
                node.right = new TreeNode(levelorder[i]!);
                queue.push(node.right);
            }
            i++;
        }
        
        return root;
    }
}

Python

class TreeReconstruction:
    # Method 1: Build from Preorder and Inorder
    def build_tree_preorder_inorder(self, preorder, inorder):
        if not preorder or not inorder:
            return None
        
        # Create map for O(1) inorder lookups
        inorder_map = {val: i for i, val in enumerate(inorder)}
        self.preorder_index = 0
        
        def build(inorder_start, inorder_end):
            if inorder_start > inorder_end:
                return None
            
            root_val = preorder[self.preorder_index]
            self.preorder_index += 1
            root = TreeNode(root_val)
            
            inorder_root_index = inorder_map[root_val]
            
            # Build left subtree first (preorder: root, left, right)
            root.left = build(inorder_start, inorder_root_index - 1)
            root.right = build(inorder_root_index + 1, inorder_end)
            
            return root
        
        return build(0, len(inorder) - 1)
    
    # Method 2: Build BST from Preorder Only
    def build_bst_from_preorder(self, preorder):
        if not preorder:
            return None
        
        self.index = 0
        
        def build(min_val, max_val):
            if self.index >= len(preorder):
                return None
            
            val = preorder[self.index]
            if val < min_val or val > max_val:
                return None
            
            self.index += 1
            root = TreeNode(val)
            
            # Build left subtree with updated max bound
            root.left = build(min_val, val)
            # Build right subtree with updated min bound
            root.right = build(val, max_val)
            
            return root
        
        return build(float('-inf'), float('inf'))
    
    # Method 3: Build from Level Order Traversal
    def build_tree_from_level_order(self, levelorder):
        if not levelorder or levelorder[0] is None:
            return None
        
        from collections import deque
        root = TreeNode(levelorder[0])
        queue = deque([root])
        i = 1
        
        while queue and i < len(levelorder):
            node = queue.popleft()
            
            # Left child
            if i < len(levelorder) and levelorder[i] is not None:
                node.left = TreeNode(levelorder[i])
                queue.append(node.left)
            i += 1
            
            # Right child
            if i < len(levelorder) and levelorder[i] is not None:
                node.right = TreeNode(levelorder[i])
                queue.append(node.right)
            i += 1
        
        return root

OCaml

type tree = Empty | Node of int * tree * tree

module TreeReconstruction = struct
  (* Method 1: Build from Preorder and Inorder *)
  let build_tree_preorder_inorder preorder inorder =
    let inorder_map = Hashtbl.create (List.length inorder) in
    List.iteri (fun i val -> Hashtbl.add inorder_map val i) inorder;
    
    let preorder_index = ref 0 in
    
    let rec build inorder_start inorder_end =
      if inorder_start > inorder_end then Empty
      else (
        let root_val = List.nth preorder !preorder_index in
        incr preorder_index;
        
        let inorder_root_index = Hashtbl.find inorder_map root_val in
        
        let left = build inorder_start (inorder_root_index - 1) in
        let right = build (inorder_root_index + 1) inorder_end in
        
        Node (root_val, left, right)
      )
    in
    
    build 0 (List.length inorder - 1)
  
  (* Method 2: Build BST from Preorder Only *)
  let build_bst_from_preorder preorder =
    let index = ref 0 in
    
    let rec build min_val max_val =
      if !index >= List.length preorder then Empty
      else (
        let val_at_index = List.nth preorder !index in
        if val_at_index < min_val || val_at_index > max_val then Empty
        else (
          incr index;
          let left = build min_val val_at_index in
          let right = build val_at_index max_val in
          Node (val_at_index, left, right)
        )
      )
    in
    
    build min_int max_int
end

🔄 Reconstruction Strategies:

Preorder + Inorder: Use preorder for root, inorder for left/right split
BST from Preorder: Use BST property with bounds checking
Level Order: Build level by level using queue
Key Insight: Need either constraints (BST) or two traversals

Method	Time Complexity	Space Complexity	Requirements
Preorder + Inorder	O(n)	O(n)	Two traversals
BST from Preorder	O(n)	O(h)	BST property
Level Order	O(n)	O(n)	Complete representation

Heaps & Priority Queues

Binary Heap

A binary heap is a complete binary tree that satisfies the heap property: in a max heap, parent nodes are greater than their children; in a min heap, parent nodes are smaller than their children.

🏆 Real-Life Analogy:

Think of a tournament bracket where the strongest player always moves up. In a max heap, the strongest (largest value) is always at the top, just like the tournament winner.

TypeScript

class MaxHeap {
    private heap: number[] = [];
    
    private getParentIndex(index: number): number {
        return Math.floor((index - 1) / 2);
    }
    
    private getLeftChildIndex(index: number): number {
        return 2 * index + 1;
    }
    
    private getRightChildIndex(index: number): number {
        return 2 * index + 2;
    }
    
    private swap(i: number, j: number): void {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
    
    insert(value: number): void {
        this.heap.push(value);
        this.heapifyUp(this.heap.length - 1);
    }
    
    private heapifyUp(index: number): void {
        const parentIndex = this.getParentIndex(index);
        
        if (parentIndex >= 0 && this.heap[parentIndex] < this.heap[index]) {
            this.swap(parentIndex, index);
            this.heapifyUp(parentIndex);
        }
    }
    
    extractMax(): number | null {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop()!;
        
        const max = this.heap[0];
        this.heap[0] = this.heap.pop()!;
        this.heapifyDown(0);
        
        return max;
    }
    
    private heapifyDown(index: number): void {
        const leftIndex = this.getLeftChildIndex(index);
        const rightIndex = this.getRightChildIndex(index);
        let largest = index;
        
        if (leftIndex < this.heap.length && this.heap[leftIndex] > this.heap[largest]) {
            largest = leftIndex;
        }
        
        if (rightIndex < this.heap.length && this.heap[rightIndex] > this.heap[largest]) {
            largest = rightIndex;
        }
        
        if (largest !== index) {
            this.swap(index, largest);
            this.heapifyDown(largest);
        }
    }
    
    peek(): number | null {
        return this.heap.length > 0 ? this.heap[0] : null;
    }
}

Python

import heapq

class MaxHeap:
    def __init__(self):
        self.heap = []
    
    def insert(self, value):
        # Python's heapq is a min heap, so we negate values for max heap
        heapq.heappush(self.heap, -value)
    
    def extract_max(self):
        if not self.heap:
            return None
        return -heapq.heappop(self.heap)
    
    def peek(self):
        if not self.heap:
            return None
        return -self.heap[0]

# Alternative: Manual implementation
class ManualMaxHeap:
    def __init__(self):
        self.heap = []
    
    def _parent_index(self, index):
        return (index - 1) // 2
    
    def _left_child_index(self, index):
        return 2 * index + 1
    
    def _right_child_index(self, index):
        return 2 * index + 2
    
    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    
    def insert(self, value):
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)
    
    def _heapify_up(self, index):
        parent_index = self._parent_index(index)
        
        if parent_index >= 0 and self.heap[parent_index] < self.heap[index]:
            self._swap(parent_index, index)
            self._heapify_up(parent_index)
    
    def extract_max(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        
        max_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        
        return max_val
    
    def _heapify_down(self, index):
        left_index = self._left_child_index(index)
        right_index = self._right_child_index(index)
        largest = index
        
        if (left_index < len(self.heap) and 
            self.heap[left_index] > self.heap[largest]):
            largest = left_index
        
        if (right_index < len(self.heap) and 
            self.heap[right_index] > self.heap[largest]):
            largest = right_index
        
        if largest != index:
            self._swap(index, largest)
            self._heapify_down(largest)

OCaml

(* Simple heap implementation using arrays *)
module MaxHeap = struct
  type t = {
    mutable data: int array;
    mutable size: int;
    capacity: int;
  }
  
  let create capacity = {
    data = Array.make capacity 0;
    size = 0;
    capacity;
  }
  
  let parent i = (i - 1) / 2
  let left_child i = 2 * i + 1
  let right_child i = 2 * i + 2
  
  let swap heap i j =
    let temp = heap.data.(i) in
    heap.data.(i) <- heap.data.(j);
    heap.data.(j) <- temp
  
  let rec heapify_up heap index =
    if index > 0 then
      let parent_idx = parent index in
      if heap.data.(parent_idx) < heap.data.(index) then (
        swap heap parent_idx index;
        heapify_up heap parent_idx
      )
  
  let rec heapify_down heap index =
    let left_idx = left_child index in
    let right_idx = right_child index in
    let largest = ref index in
    
    if left_idx < heap.size && 
       heap.data.(left_idx) > heap.data.(!largest) then
      largest := left_idx;
    
    if right_idx < heap.size && 
       heap.data.(right_idx) > heap.data.(!largest) then
      largest := right_idx;
    
    if !largest <> index then (
      swap heap index !largest;
      heapify_down heap !largest
    )
  
  let insert heap value =
    if heap.size < heap.capacity then (
      heap.data.(heap.size) <- value;
      heapify_up heap heap.size;
      heap.size <- heap.size + 1
    )
  
  let extract_max heap =
    if heap.size = 0 then None
    else if heap.size = 1 then (
      heap.size <- 0;
      Some heap.data.(0)
    ) else (
      let max_val = heap.data.(0) in
      heap.data.(0) <- heap.data.(heap.size - 1);
      heap.size <- heap.size - 1;
      heapify_down heap 0;
      Some max_val
    )
end

Operation	Time Complexity	Space Complexity
Insert	O(log n)	O(1)
Extract Max/Min	O(log n)	O(1)
Peek	O(1)	O(1)

Hash Tables

Hash Table with Collision Handling

A hash table uses a hash function to map keys to indices in an array, providing average O(1) time complexity for insertions, deletions, and lookups. When multiple keys hash to the same index (collision), we need strategies to handle them.

📚 Real-Life Analogy:

Think of a library's card catalog system. Each book has a unique call number (hash) that tells you exactly which shelf (bucket) to find it on. When multiple books need the same shelf (collision), you either chain them together or find the next available shelf.

TypeScript

// Hash Table with Chaining (Separate Chaining)
class HashTableChaining {
    private buckets: Array>;
    private size: number;
    private capacity: number;
    private readonly loadFactorThreshold = 0.75;
    
    constructor(initialCapacity: number = 16) {
        this.capacity = initialCapacity;
        this.size = 0;
        this.buckets = new Array(this.capacity);
        for (let i = 0; i < this.capacity; i++) {
            this.buckets[i] = [];
        }
    }
    
    private hash(key: string): number {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash * 31 + key.charCodeAt(i)) % this.capacity;
        }
        return Math.abs(hash);
    }
    
    private resize(): void {
        const oldBuckets = this.buckets;
        this.capacity *= 2;
        this.size = 0;
        this.buckets = new Array(this.capacity);
        
        for (let i = 0; i < this.capacity; i++) {
            this.buckets[i] = [];
        }
        
        // Rehash all existing elements
        for (const bucket of oldBuckets) {
            for (const {key, value} of bucket) {
                this.put(key, value);
            }
        }
    }
    
    put(key: string, value: T): void {
        const index = this.hash(key);
        const bucket = this.buckets[index];
        
        // Check if key already exists
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i].key === key) {
                bucket[i].value = value; // Update existing
                return;
            }
        }
        
        // Add new key-value pair
        bucket.push({key, value});
        this.size++;
        
        // Check if resize is needed
        if (this.size / this.capacity > this.loadFactorThreshold) {
            this.resize();
        }
    }
    
    get(key: string): T | null {
        const index = this.hash(key);
        const bucket = this.buckets[index];
        
        for (const {key: k, value} of bucket) {
            if (k === key) {
                return value;
            }
        }
        
        return null;
    }
    
    delete(key: string): boolean {
        const index = this.hash(key);
        const bucket = this.buckets[index];
        
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i].key === key) {
                bucket.splice(i, 1);
                this.size--;
                return true;
            }
        }
        
        return false;
    }
    
    getLoadFactor(): number {
        return this.size / this.capacity;
    }
}

// Hash Table with Open Addressing (Linear Probing)
class HashTableOpenAddressing {
    private keys: (string | null)[];
    private values: (T | null)[];
    private size: number;
    private capacity: number;
    private readonly loadFactorThreshold = 0.5;
    
    constructor(initialCapacity: number = 16) {
        this.capacity = initialCapacity;
        this.size = 0;
        this.keys = new Array(this.capacity).fill(null);
        this.values = new Array(this.capacity).fill(null);
    }
    
    private hash(key: string): number {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash * 31 + key.charCodeAt(i)) % this.capacity;
        }
        return Math.abs(hash);
    }
    
    private resize(): void {
        const oldKeys = this.keys;
        const oldValues = this.values;
        
        this.capacity *= 2;
        this.size = 0;
        this.keys = new Array(this.capacity).fill(null);
        this.values = new Array(this.capacity).fill(null);
        
        // Rehash all existing elements
        for (let i = 0; i < oldKeys.length; i++) {
            if (oldKeys[i] !== null) {
                this.put(oldKeys[i]!, oldValues[i]!);
            }
        }
    }
    
    put(key: string, value: T): void {
        if (this.size >= this.capacity * this.loadFactorThreshold) {
            this.resize();
        }
        
        let index = this.hash(key);
        
        // Linear probing to find empty slot or existing key
        while (this.keys[index] !== null) {
            if (this.keys[index] === key) {
                this.values[index] = value; // Update existing
                return;
            }
            index = (index + 1) % this.capacity; // Linear probing
        }
        
        // Insert new key-value pair
        this.keys[index] = key;
        this.values[index] = value;
        this.size++;
    }
    
    get(key: string): T | null {
        let index = this.hash(key);
        
        while (this.keys[index] !== null) {
            if (this.keys[index] === key) {
                return this.values[index];
            }
            index = (index + 1) % this.capacity;
        }
        
        return null;
    }
    
    delete(key: string): boolean {
        let index = this.hash(key);
        
        while (this.keys[index] !== null) {
            if (this.keys[index] === key) {
                this.keys[index] = null;
                this.values[index] = null;
                this.size--;
                
                // Rehash subsequent elements to maintain clustering
                index = (index + 1) % this.capacity;
                while (this.keys[index] !== null) {
                    const keyToRehash = this.keys[index]!;
                    const valueToRehash = this.values[index]!;
                    this.keys[index] = null;
                    this.values[index] = null;
                    this.size--;
                    this.put(keyToRehash, valueToRehash);
                    index = (index + 1) % this.capacity;
                }
                
                return true;
            }
            index = (index + 1) % this.capacity;
        }
        
        return false;
    }
}

Python

# Hash Table with Chaining (Separate Chaining)
class HashTableChaining:
    def __init__(self, initial_capacity=16):
        self.capacity = initial_capacity
        self.size = 0
        self.buckets = [[] for _ in range(self.capacity)]
        self.load_factor_threshold = 0.75
    
    def _hash(self, key):
        hash_value = 0
        for char in key:
            hash_value = (hash_value * 31 + ord(char)) % self.capacity
        return hash_value
    
    def _resize(self):
        old_buckets = self.buckets
        self.capacity *= 2
        self.size = 0
        self.buckets = [[] for _ in range(self.capacity)]
        
        # Rehash all existing elements
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)
    
    def put(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
        
        # Check if key already exists
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Update existing
                return
        
        # Add new key-value pair
        bucket.append((key, value))
        self.size += 1
        
        # Check if resize is needed
        if self.size / self.capacity > self.load_factor_threshold:
            self._resize()
    
    def get(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        
        for k, v in bucket:
            if k == key:
                return v
        
        return None
    
    def delete(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return True
        
        return False
    
    def get_load_factor(self):
        return self.size / self.capacity

# Hash Table with Open Addressing (Linear Probing)
class HashTableOpenAddressing:
    def __init__(self, initial_capacity=16):
        self.capacity = initial_capacity
        self.size = 0
        self.keys = [None] * self.capacity
        self.values = [None] * self.capacity
        self.load_factor_threshold = 0.5
    
    def _hash(self, key):
        hash_value = 0
        for char in key:
            hash_value = (hash_value * 31 + ord(char)) % self.capacity
        return hash_value
    
    def _resize(self):
        old_keys = self.keys
        old_values = self.values
        
        self.capacity *= 2
        self.size = 0
        self.keys = [None] * self.capacity
        self.values = [None] * self.capacity
        
        # Rehash all existing elements
        for i in range(len(old_keys)):
            if old_keys[i] is not None:
                self.put(old_keys[i], old_values[i])
    
    def put(self, key, value):
        if self.size >= self.capacity * self.load_factor_threshold:
            self._resize()
        
        index = self._hash(key)
        
        # Linear probing to find empty slot or existing key
        while self.keys[index] is not None:
            if self.keys[index] == key:
                self.values[index] = value  # Update existing
                return
            index = (index + 1) % self.capacity
        
        # Insert new key-value pair
        self.keys[index] = key
        self.values[index] = value
        self.size += 1
    
    def get(self, key):
        index = self._hash(key)
        
        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]
            index = (index + 1) % self.capacity
        
        return None
    
    def delete(self, key):
        index = self._hash(key)
        
        while self.keys[index] is not None:
            if self.keys[index] == key:
                self.keys[index] = None
                self.values[index] = None
                self.size -= 1
                
                # Rehash subsequent elements to maintain clustering
                index = (index + 1) % self.capacity
                while self.keys[index] is not None:
                    key_to_rehash = self.keys[index]
                    value_to_rehash = self.values[index]
                    self.keys[index] = None
                    self.values[index] = None
                    self.size -= 1
                    self.put(key_to_rehash, value_to_rehash)
                    index = (index + 1) % self.capacity
                
                return True
            index = (index + 1) % self.capacity
        
        return False

OCaml

(* Hash Table with Chaining *)
module HashTableChaining = struct
  type ('a, 'b) t = {
    mutable buckets: ('a * 'b) list array;
    mutable size: int;
    mutable capacity: int;
    load_factor_threshold: float;
  }
  
  let create initial_capacity = {
    buckets = Array.make initial_capacity [];
    size = 0;
    capacity = initial_capacity;
    load_factor_threshold = 0.75;
  }
  
  let hash_string s capacity =
    let hash = ref 0 in
    String.iter (fun c ->
      hash := (!hash * 31 + Char.code c) mod capacity
    ) s;
    abs !hash
  
  let resize table =
    let old_buckets = table.buckets in
    table.capacity <- table.capacity * 2;
    table.size <- 0;
    table.buckets <- Array.make table.capacity [];
    
    Array.iter (fun bucket ->
      List.iter (fun (key, value) ->
        let index = hash_string key table.capacity in
        table.buckets.(index) <- (key, value) :: table.buckets.(index);
        table.size <- table.size + 1
      ) bucket
    ) old_buckets
  
  let put table key value =
    let index = hash_string key table.capacity in
    let bucket = table.buckets.(index) in
    
    (* Check if key already exists *)
    let rec update_or_add = function
      | [] -> 
          table.buckets.(index) <- (key, value) :: bucket;
          table.size <- table.size + 1;
          if float_of_int table.size /. float_of_int table.capacity > table.load_factor_threshold then
            resize table
      | (k, v) :: rest when k = key ->
          table.buckets.(index) <- (key, value) :: rest
      | item :: rest ->
          item :: update_or_add rest
    in
    table.buckets.(index) <- update_or_add bucket
  
  let get table key =
    let index = hash_string key table.capacity in
    let bucket = table.buckets.(index) in
    
    let rec find = function
      | [] -> None
      | (k, v) :: _ when k = key -> Some v
      | _ :: rest -> find rest
    in
    find bucket
  
  let delete table key =
    let index = hash_string key table.capacity in
    let bucket = table.buckets.(index) in
    
    let rec remove = function
      | [] -> ([], false)
      | (k, v) :: rest when k = key -> (rest, true)
      | item :: rest ->
          let (new_rest, found) = remove rest in
          (item :: new_rest, found)
    in
    
    let (new_bucket, found) = remove bucket in
    if found then (
      table.buckets.(index) <- new_bucket;
      table.size <- table.size - 1
    );
    found
end

(* Hash Table with Open Addressing *)
module HashTableOpenAddressing = struct
  type ('a, 'b) t = {
    mutable keys: 'a option array;
    mutable values: 'b option array;
    mutable size: int;
    mutable capacity: int;
    load_factor_threshold: float;
  }
  
  let create initial_capacity = {
    keys = Array.make initial_capacity None;
    values = Array.make initial_capacity None;
    size = 0;
    capacity = initial_capacity;
    load_factor_threshold = 0.5;
  }
  
  let hash_string s capacity =
    let hash = ref 0 in
    String.iter (fun c ->
      hash := (!hash * 31 + Char.code c) mod capacity
    ) s;
    abs !hash
  
  let resize table =
    let old_keys = table.keys in
    let old_values = table.values in
    
    table.capacity <- table.capacity * 2;
    table.size <- 0;
    table.keys <- Array.make table.capacity None;
    table.values <- Array.make table.capacity None;
    
    for i = 0 to Array.length old_keys - 1 do
      match old_keys.(i), old_values.(i) with
      | Some key, Some value ->
          let rec find_slot index =
            if table.keys.(index) = None then (
              table.keys.(index) <- Some key;
              table.values.(index) <- Some value;
              table.size <- table.size + 1
            ) else
              find_slot ((index + 1) mod table.capacity)
          in
          find_slot (hash_string key table.capacity)
      | _ -> ()
    done
  
  let put table key value =
    if float_of_int table.size >= float_of_int table.capacity *. table.load_factor_threshold then
      resize table;
    
    let rec find_slot index =
      match table.keys.(index) with
      | None ->
          table.keys.(index) <- Some key;
          table.values.(index) <- Some value;
          table.size <- table.size + 1
      | Some k when k = key ->
          table.values.(index) <- Some value
      | Some _ ->
          find_slot ((index + 1) mod table.capacity)
    in
    find_slot (hash_string key table.capacity)
  
  let get table key =
    let rec find_key index =
      match table.keys.(index) with
      | None -> None
      | Some k when k = key -> table.values.(index)
      | Some _ -> find_key ((index + 1) mod table.capacity)
    in
    find_key (hash_string key table.capacity)
end

🔑 Collision Handling Strategies:

Separate Chaining: Each bucket contains a list of key-value pairs
Open Addressing: Find next available slot using probing
Linear Probing: Check next slot sequentially
Quadratic Probing: Check slots at quadratic intervals
Double Hashing: Use second hash function for probing

Method	Average Case	Worst Case	Space Overhead
Separate Chaining	O(1)	O(n)	Extra pointers
Linear Probing	O(1)	O(n)	None
Quadratic Probing	O(1)	O(n)	None

Graph Representations

Complete Graph Implementations

Graphs are collections of vertices (nodes) connected by edges. Different representations offer different trade-offs in terms of space and time complexity for various operations.

🗺️ Real-Life Analogy:

Think of a social network where people (vertices) are connected by friendships (edges). You could store this as: a contact list for each person (adjacency list), a giant friendship matrix (adjacency matrix), or a simple list of all friendships (edge list).

TypeScript

// 1. Adjacency List Implementation
class GraphAdjacencyList {
    private vertices: Map;
    private isDirected: boolean;
    
    constructor(isDirected: boolean = false) {
        this.vertices = new Map();
        this.isDirected = isDirected;
    }
    
    addVertex(vertex: number): void {
        if (!this.vertices.has(vertex)) {
            this.vertices.set(vertex, []);
        }
    }
    
    addEdge(from: number, to: number): void {
        this.addVertex(from);
        this.addVertex(to);
        
        this.vertices.get(from)!.push(to);
        
        if (!this.isDirected) {
            this.vertices.get(to)!.push(from);
        }
    }
    
    getNeighbors(vertex: number): number[] {
        return this.vertices.get(vertex) || [];
    }
    
    hasEdge(from: number, to: number): boolean {
        return this.vertices.get(from)?.includes(to) || false;
    }
}

// 2. Adjacency Matrix Implementation
class GraphAdjacencyMatrix {
    private matrix: number[][];
    private vertexCount: number;
    private isDirected: boolean;
    
    constructor(vertexCount: number, isDirected: boolean = false) {
        this.vertexCount = vertexCount;
        this.isDirected = isDirected;
        this.matrix = Array(vertexCount).fill(null).map(() => Array(vertexCount).fill(0));
    }
    
    addEdge(from: number, to: number, weight: number = 1): void {
        if (this.isValidVertex(from) && this.isValidVertex(to)) {
            this.matrix[from][to] = weight;
            
            if (!this.isDirected) {
                this.matrix[to][from] = weight;
            }
        }
    }
    
    hasEdge(from: number, to: number): boolean {
        if (this.isValidVertex(from) && this.isValidVertex(to)) {
            return this.matrix[from][to] !== 0;
        }
        return false;
    }
    
    getNeighbors(vertex: number): number[] {
        const neighbors: number[] = [];
        if (this.isValidVertex(vertex)) {
            for (let i = 0; i < this.vertexCount; i++) {
                if (this.matrix[vertex][i] !== 0) {
                    neighbors.push(i);
                }
            }
        }
        return neighbors;
    }
    
    private isValidVertex(vertex: number): boolean {
        return vertex >= 0 && vertex < this.vertexCount;
    }
}

// 3. Edge List Implementation
interface Edge {
    from: number;
    to: number;
    weight?: number;
}

class GraphEdgeList {
    private edges: Edge[];
    private vertices: Set;
    private isDirected: boolean;
    
    constructor(isDirected: boolean = false) {
        this.edges = [];
        this.vertices = new Set();
        this.isDirected = isDirected;
    }
    
    addVertex(vertex: number): void {
        this.vertices.add(vertex);
    }
    
    addEdge(from: number, to: number, weight: number = 1): void {
        this.vertices.add(from);
        this.vertices.add(to);
        
        this.edges.push({ from, to, weight });
        
        if (!this.isDirected) {
            this.edges.push({ from: to, to: from, weight });
        }
    }
    
    hasEdge(from: number, to: number): boolean {
        return this.edges.some(edge => edge.from === from && edge.to === to);
    }
    
    getNeighbors(vertex: number): number[] {
        return this.edges
            .filter(edge => edge.from === vertex)
            .map(edge => edge.to);
    }
    
    getAllEdges(): Edge[] {
        return [...this.edges];
    }
}

// Conversion utilities
class GraphConverter {
    static listToMatrix(adjList: GraphAdjacencyList, vertexCount: number): GraphAdjacencyMatrix {
        const matrix = new GraphAdjacencyMatrix(vertexCount, true);
        
        for (let i = 0; i < vertexCount; i++) {
            for (const neighbor of adjList.getNeighbors(i)) {
                matrix.addEdge(i, neighbor);
            }
        }
        
        return matrix;
    }
    
    static listToEdgeList(adjList: GraphAdjacencyList): GraphEdgeList {
        const edgeList = new GraphEdgeList(true);
        
        // Assuming vertices are numbered 0 to n-1
        for (let vertex = 0; vertex < 100; vertex++) { // arbitrary limit
            const neighbors = adjList.getNeighbors(vertex);
            if (neighbors.length > 0) {
                edgeList.addVertex(vertex);
                for (const neighbor of neighbors) {
                    edgeList.addEdge(vertex, neighbor);
                }
            }
        }
        
        return edgeList;
    }
}

Python

# 1. Adjacency List Implementation
class GraphAdjacencyList:
    def __init__(self, is_directed=False):
        self.vertices = {}
        self.is_directed = is_directed
    
    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = []
    
    def add_edge(self, from_vertex, to_vertex):
        self.add_vertex(from_vertex)
        self.add_vertex(to_vertex)
        
        self.vertices[from_vertex].append(to_vertex)
        
        if not self.is_directed:
            self.vertices[to_vertex].append(from_vertex)
    
    def get_neighbors(self, vertex):
        return self.vertices.get(vertex, [])
    
    def has_edge(self, from_vertex, to_vertex):
        return to_vertex in self.vertices.get(from_vertex, [])
    
    def get_all_vertices(self):
        return list(self.vertices.keys())
    
    def remove_edge(self, from_vertex, to_vertex):
        if from_vertex in self.vertices and to_vertex in self.vertices[from_vertex]:
            self.vertices[from_vertex].remove(to_vertex)
        
        if not self.is_directed and to_vertex in self.vertices and from_vertex in self.vertices[to_vertex]:
            self.vertices[to_vertex].remove(from_vertex)

# 2. Adjacency Matrix Implementation
class GraphAdjacencyMatrix:
    def __init__(self, vertex_count, is_directed=False):
        self.vertex_count = vertex_count
        self.is_directed = is_directed
        self.matrix = [[0] * vertex_count for _ in range(vertex_count)]
    
    def add_edge(self, from_vertex, to_vertex, weight=1):
        if self._is_valid_vertex(from_vertex) and self._is_valid_vertex(to_vertex):
            self.matrix[from_vertex][to_vertex] = weight
            
            if not self.is_directed:
                self.matrix[to_vertex][from_vertex] = weight
    
    def has_edge(self, from_vertex, to_vertex):
        if self._is_valid_vertex(from_vertex) and self._is_valid_vertex(to_vertex):
            return self.matrix[from_vertex][to_vertex] != 0
        return False
    
    def get_neighbors(self, vertex):
        neighbors = []
        if self._is_valid_vertex(vertex):
            for i in range(self.vertex_count):
                if self.matrix[vertex][i] != 0:
                    neighbors.append(i)
        return neighbors
    
    def get_weight(self, from_vertex, to_vertex):
        if self._is_valid_vertex(from_vertex) and self._is_valid_vertex(to_vertex):
            return self.matrix[from_vertex][to_vertex]
        return 0
    
    def _is_valid_vertex(self, vertex):
        return 0 <= vertex < self.vertex_count
    
    def print_matrix(self):
        for row in self.matrix:
            print(' '.join(map(str, row)))

# 3. Edge List Implementation
class GraphEdgeList:
    def __init__(self, is_directed=False):
        self.edges = []
        self.vertices = set()
        self.is_directed = is_directed
    
    def add_vertex(self, vertex):
        self.vertices.add(vertex)
    
    def add_edge(self, from_vertex, to_vertex, weight=1):
        self.vertices.add(from_vertex)
        self.vertices.add(to_vertex)
        
        self.edges.append((from_vertex, to_vertex, weight))
        
        if not self.is_directed:
            self.edges.append((to_vertex, from_vertex, weight))
    
    def has_edge(self, from_vertex, to_vertex):
        return any(f == from_vertex and t == to_vertex for f, t, _ in self.edges)
    
    def get_neighbors(self, vertex):
        return [t for f, t, _ in self.edges if f == vertex]
    
    def get_all_edges(self):
        return self.edges.copy()
    
    def get_all_vertices(self):
        return list(self.vertices)
    
    def remove_edge(self, from_vertex, to_vertex):
        self.edges = [(f, t, w) for f, t, w in self.edges 
                     if not (f == from_vertex and t == to_vertex)]
        
        if not self.is_directed:
            self.edges = [(f, t, w) for f, t, w in self.edges 
                         if not (f == to_vertex and t == from_vertex)]

# Conversion utilities
class GraphConverter:
    @staticmethod
    def list_to_matrix(adj_list, vertex_count):
        matrix = GraphAdjacencyMatrix(vertex_count, adj_list.is_directed)
        
        for vertex in adj_list.get_all_vertices():
            if isinstance(vertex, int) and 0 <= vertex < vertex_count:
                for neighbor in adj_list.get_neighbors(vertex):
                    if isinstance(neighbor, int) and 0 <= neighbor < vertex_count:
                        matrix.add_edge(vertex, neighbor)
        
        return matrix
    
    @staticmethod
    def list_to_edge_list(adj_list):
        edge_list = GraphEdgeList(adj_list.is_directed)
        
        for vertex in adj_list.get_all_vertices():
            edge_list.add_vertex(vertex)
            for neighbor in adj_list.get_neighbors(vertex):
                edge_list.add_edge(vertex, neighbor)
        
        return edge_list
    
    @staticmethod
    def edge_list_to_list(edge_list):
        adj_list = GraphAdjacencyList(edge_list.is_directed)
        
        for vertex in edge_list.get_all_vertices():
            adj_list.add_vertex(vertex)
        
        for from_vertex, to_vertex, _ in edge_list.get_all_edges():
            adj_list.add_edge(from_vertex, to_vertex)
        
        return adj_list

# Example usage
def demonstrate_graph_representations():
    print("=== Graph Representations Demo ===")
    
    # Create same graph with different representations
    # Graph: 0-1, 0-2, 1-2, 2-3
    
    # Adjacency List
    adj_list = GraphAdjacencyList()
    adj_list.add_edge(0, 1)
    adj_list.add_edge(0, 2)
    adj_list.add_edge(1, 2)
    adj_list.add_edge(2, 3)
    
    # Adjacency Matrix
    adj_matrix = GraphAdjacencyMatrix(4)
    adj_matrix.add_edge(0, 1)
    adj_matrix.add_edge(0, 2)
    adj_matrix.add_edge(1, 2)
    adj_matrix.add_edge(2, 3)
    
    # Edge List
    edge_list = GraphEdgeList()
    edge_list.add_edge(0, 1)
    edge_list.add_edge(0, 2)
    edge_list.add_edge(1, 2)
    edge_list.add_edge(2, 3)
    
    print("Neighbors of vertex 0:")
    print(f"Adjacency List: {adj_list.get_neighbors(0)}")
    print(f"Adjacency Matrix: {adj_matrix.get_neighbors(0)}")
    print(f"Edge List: {edge_list.get_neighbors(0)}")

OCaml

(* 1. Adjacency List Implementation *)
module GraphAdjacencyList = struct
  type t = {
    mutable vertices: (int, int list) Hashtbl.t;
    is_directed: bool;
  }
  
  let create is_directed = {
    vertices = Hashtbl.create 16;
    is_directed;
  }
  
  let add_vertex graph vertex =
    if not (Hashtbl.mem graph.vertices vertex) then
      Hashtbl.add graph.vertices vertex []
  
  let add_edge graph from_vertex to_vertex =
    add_vertex graph from_vertex;
    add_vertex graph to_vertex;
    
    let current_neighbors = 
      try Hashtbl.find graph.vertices from_vertex 
      with Not_found -> [] in
    Hashtbl.replace graph.vertices from_vertex (to_vertex :: current_neighbors);
    
    if not graph.is_directed then (
      let current_neighbors = 
        try Hashtbl.find graph.vertices to_vertex 
        with Not_found -> [] in
      Hashtbl.replace graph.vertices to_vertex (from_vertex :: current_neighbors)
    )
  
  let get_neighbors graph vertex =
    try Hashtbl.find graph.vertices vertex
    with Not_found -> []
  
  let has_edge graph from_vertex to_vertex =
    let neighbors = get_neighbors graph from_vertex in
    List.mem to_vertex neighbors
  
  let get_all_vertices graph =
    Hashtbl.fold (fun vertex _ acc -> vertex :: acc) graph.vertices []
end

(* 2. Adjacency Matrix Implementation *)
module GraphAdjacencyMatrix = struct
  type t = {
    matrix: int array array;
    vertex_count: int;
    is_directed: bool;
  }
  
  let create vertex_count is_directed = {
    matrix = Array.make_matrix vertex_count vertex_count 0;
    vertex_count;
    is_directed;
  }
  
  let is_valid_vertex graph vertex =
    vertex >= 0 && vertex < graph.vertex_count
  
  let add_edge graph from_vertex to_vertex ?(weight=1) () =
    if is_valid_vertex graph from_vertex && is_valid_vertex graph to_vertex then (
      graph.matrix.(from_vertex).(to_vertex) <- weight;
      
      if not graph.is_directed then
        graph.matrix.(to_vertex).(from_vertex) <- weight
    )
  
  let has_edge graph from_vertex to_vertex =
    if is_valid_vertex graph from_vertex && is_valid_vertex graph to_vertex then
      graph.matrix.(from_vertex).(to_vertex) <> 0
    else false
  
  let get_neighbors graph vertex =
    if is_valid_vertex graph vertex then
      let neighbors = ref [] in
      for i = 0 to graph.vertex_count - 1 do
        if graph.matrix.(vertex).(i) <> 0 then
          neighbors := i :: !neighbors
      done;
      List.rev !neighbors
    else []
  
  let get_weight graph from_vertex to_vertex =
    if is_valid_vertex graph from_vertex && is_valid_vertex graph to_vertex then
      graph.matrix.(from_vertex).(to_vertex)
    else 0
  
  let print_matrix graph =
    Printf.printf "Adjacency Matrix:\n";
    for i = 0 to graph.vertex_count - 1 do
      for j = 0 to graph.vertex_count - 1 do
        Printf.printf "%d " graph.matrix.(i).(j)
      done;
      Printf.printf "\n"
    done
end

(* 3. Edge List Implementation *)
module GraphEdgeList = struct
  type edge = {
    from_vertex: int;
    to_vertex: int;
    weight: int;
  }
  
  type t = {
    mutable edges: edge list;
    mutable vertices: int list;
    is_directed: bool;
  }
  
  let create is_directed = {
    edges = [];
    vertices = [];
    is_directed;
  }
  
  let add_vertex graph vertex =
    if not (List.mem vertex graph.vertices) then
      graph.vertices <- vertex :: graph.vertices
  
  let add_edge graph from_vertex to_vertex ?(weight=1) () =
    add_vertex graph from_vertex;
    add_vertex graph to_vertex;
    
    let edge = { from_vertex; to_vertex; weight } in
    graph.edges <- edge :: graph.edges;
    
    if not graph.is_directed then
      let reverse_edge = { from_vertex = to_vertex; to_vertex = from_vertex; weight } in
      graph.edges <- reverse_edge :: graph.edges
  
  let has_edge graph from_vertex to_vertex =
    List.exists (fun edge ->
      edge.from_vertex = from_vertex && edge.to_vertex = to_vertex
    ) graph.edges
  
  let get_neighbors graph vertex =
    List.fold_left (fun acc edge ->
      if edge.from_vertex = vertex then edge.to_vertex :: acc else acc
    ) [] graph.edges |> List.rev
  
  let get_all_edges graph = graph.edges
  
  let get_all_vertices graph = graph.vertices
end

(* Example usage and demonstration *)
let demonstrate_representations () =
  Printf.printf "=== Graph Representations Demo ===\n";
  
  (* Create same graph with different representations *)
  (* Graph: 0-1, 0-2, 1-2, 2-3 *)
  
  (* Adjacency List *)
  let adj_list = GraphAdjacencyList.create false in
  GraphAdjacencyList.add_edge adj_list 0 1;
  GraphAdjacencyList.add_edge adj_list 0 2;
  GraphAdjacencyList.add_edge adj_list 1 2;
  GraphAdjacencyList.add_edge adj_list 2 3;
  
  (* Adjacency Matrix *)
  let adj_matrix = GraphAdjacencyMatrix.create 4 false in
  GraphAdjacencyMatrix.add_edge adj_matrix 0 1 ();
  GraphAdjacencyMatrix.add_edge adj_matrix 0 2 ();
  GraphAdjacencyMatrix.add_edge adj_matrix 1 2 ();
  GraphAdjacencyMatrix.add_edge adj_matrix 2 3 ();
  
  (* Edge List *)
  let edge_list = GraphEdgeList.create false in
  GraphEdgeList.add_edge edge_list 0 1 ();
  GraphEdgeList.add_edge edge_list 0 2 ();
  GraphEdgeList.add_edge edge_list 1 2 ();
  GraphEdgeList.add_edge edge_list 2 3 ();
  
  Printf.printf "Neighbors of vertex 0:\n";
  Printf.printf "Adjacency List: [%s]\n" 
    (String.concat "; " (List.map string_of_int (GraphAdjacencyList.get_neighbors adj_list 0)));
  Printf.printf "Adjacency Matrix: [%s]\n" 
    (String.concat "; " (List.map string_of_int (GraphAdjacencyMatrix.get_neighbors adj_matrix 0)));
  Printf.printf "Edge List: [%s]\n" 
    (String.concat "; " (List.map string_of_int (GraphEdgeList.get_neighbors edge_list 0)))

📊 Representation Comparison:

Adjacency List: Space-efficient for sparse graphs, fast neighbor iteration
Adjacency Matrix: Fast edge lookup O(1), good for dense graphs, supports weights easily
Edge List: Simple structure, good for algorithms that process all edges sequentially
Conversions: Each representation can be converted to others as needed

Operation	Adjacency List	Adjacency Matrix	Edge List
Add Edge	O(1)	O(1)	O(1)
Remove Edge	O(V)	O(1)	O(E)
Check Edge	O(V)	O(1)	O(E)
Space	O(V + E)	O(V²)	O(E)
Get Neighbors	O(1)	O(V)	O(E)

DSA Interview Guide

Advanced Data Structures

🎯 Key Properties:

🔑 Key Insights:

🔄 Reconstruction Strategies:

🔑 Collision Handling Strategies:

📊 Representation Comparison: