Trees & Binary Search Trees: Hierarchical Data Structures

Introduction

Trees are the most important non-linear data structure in computer science. Unlike arrays, linked lists, stacks, and queues — which are all sequential — trees organize data in a hierarchical structure that enables fundamentally different operations.

Every time you browse a file system, parse HTML, evaluate an expression, or use autocomplete — you're interacting with trees. In coding interviews, tree problems are among the most common, appearing in nearly 40% of technical interviews at top tech companies.

This post begins Phase 3: Non-Linear Data Structures of our DSA series. The linear structures you learned previously (arrays, linked lists, stacks, queues) will serve as building blocks — stacks power DFS traversal, queues power BFS traversal, and arrays/linked lists are used to implement trees themselves.

What You'll Learn

✅ Understand tree terminology and properties
✅ Implement Binary Trees and Binary Search Trees from scratch
✅ Master all four tree traversals (Inorder, Preorder, Postorder, Level-Order)
✅ Perform BST operations: insert, search, delete
✅ Understand balanced vs skewed trees and why it matters
✅ Solve 8 classic tree interview problems step-by-step

Prerequisites

Understanding of Big O Notation & Complexity Analysis
Familiarity with Problem-Solving Patterns
Completed Stacks & Queues (used for traversals)
Basic programming knowledge in TypeScript or Python

1. Tree Fundamentals

1.1 What Is a Tree?

A tree is a hierarchical data structure consisting of nodes connected by edges. It has a single root node at the top, and every other node has exactly one parent.

1.2 Tree Terminology

Term	Definition
Root	Top node with no parent
Parent	Node directly above a given node
Child	Node directly below a given node
Leaf	Node with no children
Edge	Connection between parent and child
Height	Longest path from root to a leaf (root height = 0 or 1, convention varies)
Depth	Distance from root to a given node
Level	All nodes at the same depth
Subtree	A node and all its descendants
Degree	Number of children a node has

Key properties:

A tree with N nodes has exactly N - 1 edges
There is exactly one path between any two nodes
A tree with height h has at most 2^(h+1) - 1 nodes (for binary trees)

1.3 Types of Trees

We'll focus primarily on Binary Trees and Binary Search Trees in this post.

2. Binary Trees

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

2.1 Binary Tree Types

Full Binary Tree — Every node has 0 or 2 children (no single-child nodes):

Complete Binary Tree — All levels filled except possibly the last, which fills left to right:

Perfect Binary Tree — All internal nodes have 2 children, all leaves at same level:

Level 0: 1 node, Level 1: 2 nodes, Level 2: 4 nodes...
Total nodes at height h: 2^(h+1) - 1

Balanced Binary Tree — Height difference between left and right subtrees of every node is at most 1.

Degenerate (Skewed) Tree — Every node has only one child — effectively a linked list with O(n) operations:

2.2 Binary Tree Node Implementation

// TypeScript - Binary Tree Node
class TreeNode<T> {
  val: T;
  left: TreeNode<T> | null;
  right: TreeNode<T> | null;
 
  constructor(val: T, left: TreeNode<T> | null = null, right: TreeNode<T> | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
 
// Build a tree manually
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);
root.right.left = new TreeNode(12);
root.right.right = new TreeNode(20);

# Python - Binary Tree Node
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
# Build a tree manually
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(12)
root.right.right = TreeNode(20)

3. Tree Traversals — DFS and BFS

Tree traversal is the process of visiting every node exactly once. There are two fundamental approaches:

Depth-First Search (DFS) — Go as deep as possible before backtracking (uses stack)
Breadth-First Search (BFS) — Visit all nodes at current level before going deeper (uses queue)

3.1 DFS: Inorder Traversal (Left → Root → Right)

For a BST, inorder traversal visits nodes in sorted ascending order. This is the most important traversal for BSTs.

Visit order: 3 → 5 → 7 → 10 → 12 → 15 → 20 (sorted!)

// TypeScript - Inorder Traversal
 
// Recursive (clean and intuitive)
function inorderRecursive(root: TreeNode<number> | null): number[] {
  const result: number[] = [];
 
  function dfs(node: TreeNode<number> | null): void {
    if (!node) return;
    dfs(node.left);        // Left
    result.push(node.val); // Root
    dfs(node.right);       // Right
  }
 
  dfs(root);
  return result;
}
 
// Iterative (using explicit stack — important for interviews)
function inorderIterative(root: TreeNode<number> | null): number[] {
  const result: number[] = [];
  const stack: TreeNode<number>[] = [];
  let current = root;
 
  while (current || stack.length > 0) {
    // Go as far left as possible
    while (current) {
      stack.push(current);
      current = current.left;
    }
    // Process current node
    current = stack.pop()!;
    result.push(current.val);
    // Move to right subtree
    current = current.right;
  }
 
  return result;
}

# Python - Inorder Traversal
 
# Recursive
def inorder_recursive(root: TreeNode | None) -> list[int]:
    result = []
 
    def dfs(node: TreeNode | None):
        if not node:
            return
        dfs(node.left)           # Left
        result.append(node.val)  # Root
        dfs(node.right)          # Right
 
    dfs(root)
    return result
 
# Iterative
def inorder_iterative(root: TreeNode | None) -> list[int]:
    result = []
    stack = []
    current = root
 
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
 
    return result

3.2 DFS: Preorder Traversal (Root → Left → Right)

Preorder visits the root first, then left subtree, then right subtree. Useful for copying/serializing trees.

Visit order: 10 → 5 → 3 → 7 → 15 → 12 → 20

// TypeScript - Preorder Traversal
 
// Recursive
function preorderRecursive(root: TreeNode<number> | null): number[] {
  const result: number[] = [];
 
  function dfs(node: TreeNode<number> | null): void {
    if (!node) return;
    result.push(node.val); // Root
    dfs(node.left);        // Left
    dfs(node.right);       // Right
  }
 
  dfs(root);
  return result;
}
 
// Iterative
function preorderIterative(root: TreeNode<number> | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const stack: TreeNode<number>[] = [root];
 
  while (stack.length > 0) {
    const node = stack.pop()!;
    result.push(node.val);
    // Push right first so left is processed first (stack is LIFO)
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
 
  return result;
}

# Python - Preorder Traversal
 
# Recursive
def preorder_recursive(root: TreeNode | None) -> list[int]:
    result = []
 
    def dfs(node: TreeNode | None):
        if not node:
            return
        result.append(node.val)  # Root
        dfs(node.left)           # Left
        dfs(node.right)          # Right
 
    dfs(root)
    return result
 
# Iterative
def preorder_iterative(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    result = []
    stack = [root]
 
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
 
    return result

3.3 DFS: Postorder Traversal (Left → Right → Root)

Postorder visits the root last — process children before their parent. Useful for deleting trees and evaluating expression trees.

Visit order: 3 → 7 → 5 → 12 → 20 → 15 → 10

// TypeScript - Postorder Traversal
 
// Recursive
function postorderRecursive(root: TreeNode<number> | null): number[] {
  const result: number[] = [];
 
  function dfs(node: TreeNode<number> | null): void {
    if (!node) return;
    dfs(node.left);        // Left
    dfs(node.right);       // Right
    result.push(node.val); // Root
  }
 
  dfs(root);
  return result;
}
 
// Iterative (modified preorder + reverse)
function postorderIterative(root: TreeNode<number> | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const stack: TreeNode<number>[] = [root];
 
  while (stack.length > 0) {
    const node = stack.pop()!;
    result.push(node.val);
    // Push left first, then right (opposite of preorder)
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
 
  return result.reverse(); // Reverse gives postorder
}

# Python - Postorder Traversal
 
# Recursive
def postorder_recursive(root: TreeNode | None) -> list[int]:
    result = []
 
    def dfs(node: TreeNode | None):
        if not node:
            return
        dfs(node.left)           # Left
        dfs(node.right)          # Right
        result.append(node.val)  # Root
 
    dfs(root)
    return result
 
# Iterative (modified preorder + reverse)
def postorder_iterative(root: TreeNode | None) -> list[int]:
    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]

3.4 BFS: Level-Order Traversal

Visit nodes level by level, left to right. Uses a queue (exactly what we learned in the previous post!).

Visit order: [10] → [5, 15] → [3, 7, 12, 20]

// TypeScript - Level-Order Traversal (BFS)
function levelOrder(root: TreeNode<number> | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode<number>[] = [root];
 
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel: number[] = [];
 
    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;
  // Returns: [[10], [5, 15], [3, 7, 12, 20]]
}

# Python - Level-Order Traversal (BFS)
from collections import deque
 
def level_order(root: TreeNode | None) -> list[list[int]]:
    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
    # Returns: [[10], [5, 15], [3, 7, 12, 20]]

3.5 Traversal Summary

Traversal	Order	Use Case	Data Structure
Inorder	Left → Root → Right	Get sorted order from BST	Stack (DFS)
Preorder	Root → Left → Right	Copy/serialize tree	Stack (DFS)
Postorder	Left → Right → Root	Delete tree, evaluate expression	Stack (DFS)
Level-Order	Level by level	Print levels, find min depth	Queue (BFS)

Mnemonic: The name tells you when you visit the root — preorder (root first), inorder (root in middle), postorder (root last).

4. Binary Search Trees (BST)

A Binary Search Tree is a binary tree with one critical property:

For every node: all values in left subtree < node value < all values in right subtree

This property enables O(log n) search, insert, and delete operations (when the tree is balanced).

4.1 BST Search

Start at root. If target < current node, go left. If target > current node, go right. Repeat until found or null.

// TypeScript - BST Search
 
// Recursive
function searchBST(root: TreeNode<number> | null, target: number): TreeNode<number> | null {
  if (!root) return null;
  if (target === root.val) return root;
  if (target < root.val) return searchBST(root.left, target);
  return searchBST(root.right, target);
}
 
// Iterative (preferred — no stack overflow risk)
function searchBSTIterative(root: TreeNode<number> | null, target: number): TreeNode<number> | null {
  let current = root;
  while (current) {
    if (target === current.val) return current;
    if (target < current.val) current = current.left;
    else current = current.right;
  }
  return null;
}

# Python - BST Search
 
# Recursive
def search_bst(root: TreeNode | None, target: int) -> TreeNode | None:
    if not root:
        return None
    if target == root.val:
        return root
    if target < root.val:
        return search_bst(root.left, target)
    return search_bst(root.right, target)
 
# Iterative
def search_bst_iterative(root: TreeNode | None, target: int) -> TreeNode | None:
    current = root
    while current:
        if target == current.val:
            return current
        elif target < current.val:
            current = current.left
        else:
            current = current.right
    return None

Time complexity: O(h) where h is tree height. O(log n) for balanced BST, O(n) for skewed BST.

4.2 BST Insert

Find the correct position (same logic as search), then attach the new node as a leaf.

// TypeScript - BST Insert
function insertBST(root: TreeNode<number> | null, val: number): TreeNode<number> {
  if (!root) return new TreeNode(val);
 
  if (val < root.val) {
    root.left = insertBST(root.left, val);
  } else if (val > root.val) {
    root.right = insertBST(root.right, val);
  }
  // If val === root.val, ignore duplicate
 
  return root;
}

# Python - BST Insert
def insert_bst(root: TreeNode | None, val: int) -> TreeNode:
    if not root:
        return TreeNode(val)
 
    if val < root.val:
        root.left = insert_bst(root.left, val)
    elif val > root.val:
        root.right = insert_bst(root.right, val)
 
    return root

4.3 BST Delete

The most complex BST operation. Three cases to handle:

Case 1: Node is a leaf — Simply remove it.

Case 2: Node has one child — Replace node with its child.

Case 3: Node has two children — Find the inorder successor (smallest node in right subtree), copy its value to the current node, then delete the successor.

After deletion: Replace 5 with 6 (inorder successor), then delete original 6.

// TypeScript - BST Delete
function deleteBST(root: TreeNode<number> | null, val: number): TreeNode<number> | null {
  if (!root) return null;
 
  if (val < root.val) {
    root.left = deleteBST(root.left, val);
  } else if (val > root.val) {
    root.right = deleteBST(root.right, val);
  } else {
    // Found the node to delete
 
    // Case 1 & 2: No child or one child
    if (!root.left) return root.right;
    if (!root.right) return root.left;
 
    // Case 3: Two children — find inorder successor
    let successor = root.right;
    while (successor.left) {
      successor = successor.left;
    }
    root.val = successor.val;
    root.right = deleteBST(root.right, successor.val);
  }
 
  return root;
}

# Python - BST Delete
def delete_bst(root: TreeNode | None, val: int) -> TreeNode | None:
    if not root:
        return None
 
    if val < root.val:
        root.left = delete_bst(root.left, val)
    elif val > root.val:
        root.right = delete_bst(root.right, val)
    else:
        # Found the node to delete
 
        # Case 1 & 2: No child or one child
        if not root.left:
            return root.right
        if not root.right:
            return root.left
 
        # Case 3: Two children — find inorder successor
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val = successor.val
        root.right = delete_bst(root.right, successor.val)
 
    return root

4.4 BST Complexity Summary

Operation	Average (Balanced)	Worst (Skewed)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Inorder traversal	O(n)	O(n)
Space (recursive)	O(log n) stack	O(n) stack

The balance problem: If you insert sorted data [1, 2, 3, 4, 5] into a BST, you get a skewed tree (linked list). All operations degrade to O(n). This is why balanced BSTs (AVL, Red-Black) were invented.

5. Balanced BSTs — Brief Overview

Balanced BSTs automatically maintain O(log n) height through rotations after insert/delete operations.

5.1 AVL Trees

Strict balance: Height difference between left and right subtrees ≤ 1 for every node
Uses rotations (left, right, left-right, right-left) to rebalance
Faster lookups than Red-Black trees (stricter balance)
Slower inserts/deletes (more rotations)

5.2 Red-Black Trees

Relaxed balance: No path from root to leaf is more than twice as long as any other
Each node is colored red or black, with rules that ensure balance
Used in most language standard libraries:
- Java: TreeMap, TreeSet
- C++: std::map, std::set
- Linux kernel: Process scheduling, memory management

5.3 When to Use What

Structure	Lookup	Insert/Delete	Use Case
BST (unbalanced)	O(log n) avg, O(n) worst	O(log n) avg, O(n) worst	Learning, simple cases
AVL Tree	O(log n) guaranteed	O(log n) with more rotations	Read-heavy workloads
Red-Black Tree	O(log n) guaranteed	O(log n) with fewer rotations	General purpose (standard libs)
Hash Map	O(1) average	O(1) average	When order doesn't matter

Interview tip: You rarely need to implement AVL or Red-Black trees from scratch. But you should understand why they exist and their trade-offs.

6. Trie (Prefix Tree) — Introduction

A Trie is a tree-like structure used for efficient string searching and prefix matching. Each node represents a character, and paths from root to marked nodes form complete words.

Words stored: car, cat, dog

// TypeScript - Basic Trie Implementation
class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd: boolean = false;
}
 
class Trie {
  root: TrieNode = new TrieNode();
 
  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEnd = true;
  }
 
  search(word: string): boolean {
    const node = this.findNode(word);
    return node !== null && node.isEnd;
  }
 
  startsWith(prefix: string): boolean {
    return this.findNode(prefix) !== null;
  }
 
  private findNode(prefix: string): TrieNode | null {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) return null;
      node = node.children.get(char)!;
    }
    return node;
  }
}
 
// Usage
const trie = new Trie();
trie.insert("car");
trie.insert("cat");
trie.insert("dog");
console.log(trie.search("car"));      // true
console.log(trie.search("ca"));       // false
console.log(trie.startsWith("ca"));   // true

# Python - Basic Trie Implementation
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
 
    def search(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_end
 
    def starts_with(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None
 
    def _find_node(self, prefix: str) -> TrieNode | None:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

Operation	Time Complexity	Space
Insert	O(m) where m = word length	O(m) per word
Search	O(m)	O(1)
Prefix search	O(m)	O(1)

Use cases: Autocomplete, spell checkers, IP routing tables, dictionary lookups.

7. Classic Interview Problems

Problem 1: Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth (number of nodes along the longest path from root to the farthest leaf).

Approach: Recursive DFS — the depth of a tree is 1 + max(depth of left, depth of right).

// TypeScript - Maximum Depth
function maxDepth(root: TreeNode<number> | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
// Tree: [10, 5, 15, 3, 7] → maxDepth = 3

# Python - Maximum Depth
def max_depth(root: TreeNode | None) -> int:
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Time: O(n) — visit every node. Space: O(h) — recursion stack.

Problem 2: Invert Binary Tree

Mirror a binary tree (swap left and right children at every node).

The famous problem that Homebrew author Max Howell couldn't solve at Google.

// TypeScript - Invert Binary Tree
function invertTree(root: TreeNode<number> | null): TreeNode<number> | null {
  if (!root) return null;
 
  // Swap children
  const temp = root.left;
  root.left = root.right;
  root.right = temp;
 
  // Recurse
  invertTree(root.left);
  invertTree(root.right);
 
  return root;
}

# Python - Invert Binary Tree
def invert_tree(root: TreeNode | None) -> TreeNode | None:
    if not root:
        return None
 
    root.left, root.right = root.right, root.left
 
    invert_tree(root.left)
    invert_tree(root.right)
 
    return root

Time: O(n). Space: O(h).

Problem 3: Validate Binary Search Tree

Determine if a binary tree is a valid BST.

Key insight: Don't just check left.val < root.val < right.val — you must ensure ALL nodes in the left subtree are less than root, and ALL in right are greater. Pass valid ranges down.

// TypeScript - Validate BST
function isValidBST(root: TreeNode<number> | null): boolean {
  function validate(
    node: TreeNode<number> | null,
    min: number,
    max: number
  ): boolean {
    if (!node) return true;
    if (node.val <= min || node.val >= max) return false;
    return (
      validate(node.left, min, node.val) &&
      validate(node.right, node.val, max)
    );
  }
 
  return validate(root, -Infinity, Infinity);
}

# Python - Validate BST
def is_valid_bst(root: TreeNode | None) -> bool:
    def validate(node: TreeNode | None, min_val: float, max_val: float) -> bool:
        if not node:
            return True
        if node.val <= min_val or node.val >= max_val:
            return False
        return (
            validate(node.left, min_val, node.val) and
            validate(node.right, node.val, max_val)
        )
 
    return validate(root, float('-inf'), float('inf'))

Alternative: Inorder traversal should produce a strictly increasing sequence.

Time: O(n). Space: O(h).

Problem 4: Lowest Common Ancestor (LCA)

Given two nodes p and q in a binary tree, find their lowest common ancestor.

LCA definition: The deepest node that is an ancestor of both p and q.

// TypeScript - LCA of Binary Tree
function lowestCommonAncestor(
  root: TreeNode<number> | null,
  p: TreeNode<number>,
  q: TreeNode<number>
): TreeNode<number> | null {
  if (!root || root === p || root === q) return root;
 
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
 
  // If both sides return non-null, root is the LCA
  if (left && right) return root;
  // Otherwise, LCA is on the side that returned non-null
  return left ?? right;
}
 
// For BST — exploit the ordering property
function lcaBST(
  root: TreeNode<number> | null,
  p: TreeNode<number>,
  q: TreeNode<number>
): TreeNode<number> | null {
  if (!root) return null;
 
  if (p.val < root.val && q.val < root.val) {
    return lcaBST(root.left, p, q);    // Both on left
  }
  if (p.val > root.val && q.val > root.val) {
    return lcaBST(root.right, p, q);   // Both on right
  }
  return root; // Split point — this is the LCA
}

# Python - LCA of Binary Tree
def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root
 
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
 
    if left and right:
        return root
    return left or right
 
# For BST
def lca_bst(root, p, q):
    if not root:
        return None
    if p.val < root.val and q.val < root.val:
        return lca_bst(root.left, p, q)
    if p.val > root.val and q.val > root.val:
        return lca_bst(root.right, p, q)
    return root

Time: O(n) for binary tree, O(h) for BST. Space: O(h).

Problem 5: Check If Tree Is Balanced

A tree is balanced if the height difference between left and right subtrees of every node is at most 1.

// TypeScript - Check Balanced
function isBalanced(root: TreeNode<number> | null): boolean {
  function height(node: TreeNode<number> | null): number {
    if (!node) return 0;
 
    const leftHeight = height(node.left);
    if (leftHeight === -1) return -1; // Left subtree unbalanced
 
    const rightHeight = height(node.right);
    if (rightHeight === -1) return -1; // Right subtree unbalanced
 
    if (Math.abs(leftHeight - rightHeight) > 1) return -1; // Current node unbalanced
 
    return 1 + Math.max(leftHeight, rightHeight);
  }
 
  return height(root) !== -1;
}

# Python - Check Balanced
def is_balanced(root: TreeNode | None) -> bool:
    def height(node: TreeNode | None) -> int:
        if not node:
            return 0
 
        left_h = height(node.left)
        if left_h == -1:
            return -1
 
        right_h = height(node.right)
        if right_h == -1:
            return -1
 
        if abs(left_h - right_h) > 1:
            return -1
 
        return 1 + max(left_h, right_h)
 
    return height(root) != -1

Trick: Return -1 as a sentinel for "unbalanced" to short-circuit early.

Time: O(n). Space: O(h).

Problem 6: Path Sum

Given a binary tree and a target sum, determine if the tree has a root-to-leaf path such that all values along the path equal the target sum.

// TypeScript - Path Sum
function hasPathSum(root: TreeNode<number> | null, targetSum: number): boolean {
  if (!root) return false;
 
  // Leaf node — check if remaining sum equals this node's value
  if (!root.left && !root.right) {
    return targetSum === root.val;
  }
 
  const remaining = targetSum - root.val;
  return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}

# Python - Path Sum
def has_path_sum(root: TreeNode | None, target_sum: int) -> bool:
    if not root:
        return False
 
    if not root.left and not root.right:
        return target_sum == root.val
 
    remaining = target_sum - root.val
    return has_path_sum(root.left, remaining) or has_path_sum(root.right, remaining)

Time: O(n). Space: O(h).

Problem 7: Serialize and Deserialize Binary Tree

Design an algorithm to serialize a binary tree to a string and deserialize it back.

// TypeScript - Serialize/Deserialize (Preorder)
function serialize(root: TreeNode<number> | null): string {
  const result: string[] = [];
 
  function dfs(node: TreeNode<number> | null): void {
    if (!node) {
      result.push("null");
      return;
    }
    result.push(String(node.val));
    dfs(node.left);
    dfs(node.right);
  }
 
  dfs(root);
  return result.join(",");
}
 
function deserialize(data: string): TreeNode<number> | null {
  const values = data.split(",");
  let index = 0;
 
  function dfs(): TreeNode<number> | null {
    if (values[index] === "null") {
      index++;
      return null;
    }
 
    const node = new TreeNode(Number(values[index]));
    index++;
    node.left = dfs();
    node.right = dfs();
    return node;
  }
 
  return dfs();
}

# Python - Serialize/Deserialize (Preorder)
def serialize(root: TreeNode | None) -> str:
    result = []
 
    def dfs(node):
        if not node:
            result.append("null")
            return
        result.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
 
    dfs(root)
    return ",".join(result)
 
def deserialize(data: str) -> TreeNode | None:
    values = iter(data.split(","))
 
    def dfs():
        val = next(values)
        if val == "null":
            return None
        node = TreeNode(int(val))
        node.left = dfs()
        node.right = dfs()
        return node
 
    return dfs()

Time: O(n) for both operations. Space: O(n).

Problem 8: Build Tree from Inorder and Preorder

Given inorder and preorder traversal arrays, reconstruct the binary tree.

Key insight: First element of preorder is always the root. Find that root in inorder — everything to its left is the left subtree, everything to its right is the right subtree.

// TypeScript - Build Tree from Preorder + Inorder
function buildTree(preorder: number[], inorder: number[]): TreeNode<number> | null {
  const inorderMap = new Map<number, number>();
  inorder.forEach((val, idx) => inorderMap.set(val, idx));
 
  let preIdx = 0;
 
  function build(left: number, right: number): TreeNode<number> | null {
    if (left > right) return null;
 
    const rootVal = preorder[preIdx++];
    const root = new TreeNode(rootVal);
    const mid = inorderMap.get(rootVal)!;
 
    root.left = build(left, mid - 1);
    root.right = build(mid + 1, right);
 
    return root;
  }
 
  return build(0, inorder.length - 1);
}

# Python - Build Tree from Preorder + Inorder
def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    pre_idx = [0]  # Use list to allow mutation in nested function
 
    def build(left: int, right: int) -> TreeNode | None:
        if left > right:
            return None
 
        root_val = preorder[pre_idx[0]]
        pre_idx[0] += 1
        root = TreeNode(root_val)
        mid = inorder_map[root_val]
 
        root.left = build(left, mid - 1)
        root.right = build(mid + 1, right)
 
        return root
 
    return build(0, len(inorder) - 1)

Time: O(n). Space: O(n) for the hash map.

8. Pattern Recognition Guide

When you see a tree problem, recognize these patterns:

Pattern	When to Use	Example Problems
Recursive DFS	Most tree problems	Max depth, invert, validate BST
BFS (level-order)	Level-by-level processing	Level order traversal, min depth, right side view
Top-down DFS	Pass info from parent to child	Path sum, validate BST with range
Bottom-up DFS	Compute info from children to parent	Max depth, balanced check, diameter
BST property	Ordered data, search by value	Search, insert, delete, LCA in BST
Serialize/Deserialize	Store/transmit tree structure	Preorder encoding, level-order encoding
Two traversals	Reconstruct tree	Preorder + inorder, postorder + inorder

Interview heuristics:

"Find depth/height" → Bottom-up DFS (return height from leaves upward)
"Find path" → Top-down DFS (accumulate path from root down)
"Level by level" → BFS with queue
"Sorted order" → BST inorder traversal
"Validate structure" → Recursive with constraints (pass min/max range)

9. Complexity Reference

Time Complexity by Operation

Operation	BST (avg)	BST (worst)	Balanced BST	Trie
Search	O(log n)	O(n)	O(log n)	O(m)
Insert	O(log n)	O(n)	O(log n)	O(m)
Delete	O(log n)	O(n)	O(log n)	O(m)
Traversal	O(n)	O(n)	O(n)	—
Min/Max	O(log n)	O(n)	O(log n)	—

n = number of nodes, m = length of key/word

Space Complexity

Structure	Space	Recursive Stack
Binary Tree	O(n)	O(h) per call
BST	O(n)	O(h) per call
Trie	O(ALPHABET × m × n)	O(m) per call

h = height: O(log n) balanced, O(n) skewed

10. Practice Problems

Easy (Start Here)

#	Problem	Key Concept
1	Maximum Depth of Binary Tree	Bottom-up DFS
2	Invert Binary Tree	Recursive swap
3	Same Tree	Parallel DFS
4	Symmetric Tree	Mirror comparison
5	Path Sum	Top-down DFS

Medium (Build Confidence)

#	Problem	Key Concept
6	Validate BST	Range-based DFS
7	Level Order Traversal	BFS with queue
8	Lowest Common Ancestor	Recursive split
9	BST Iterator	Controlled inorder
10	Build Tree (Preorder + Inorder)	Divide and conquer

Hard (Interview Ready)

#	Problem	Key Concept
11	Serialize/Deserialize	Preorder encoding
12	Binary Tree Maximum Path Sum	Bottom-up with global max
13	Implement Trie	Prefix tree design
14	Word Search II	Trie + backtracking
15	Count Nodes in Complete Tree	Binary search on levels

Recommended approach: Solve all Easy problems first, then Medium. Attempt Hard only after you're comfortable with the patterns.

Summary and Key Takeaways

Trees:
✅ Hierarchical data structure with root, parent-child relationships, and leaves
✅ Binary tree = max 2 children per node; BST adds the ordering property
✅ Height determines performance: balanced O(log n) vs skewed O(n)

Traversals:
✅ Inorder (L-Root-R) gives sorted order in BST — most common traversal
✅ Preorder (Root-L-R) for serialization, Postorder (L-R-Root) for deletion
✅ Level-order (BFS) uses queue for level-by-level processing

BST Operations:
✅ Search, insert are straightforward — follow left/right based on comparison
✅ Delete has 3 cases — leaf, one child, two children (use inorder successor)
✅ All O(h) — balanced trees guarantee O(log n)

Interview Patterns:
✅ Most tree problems use recursive DFS — start with base case if (!node) return
✅ Top-down = pass info down (path sum), Bottom-up = return info up (max depth)
✅ BST problems exploit the ordering property for O(log n) operations
✅ Trie for string prefix problems, implement with hash map children

What's Next?

With trees under your belt, you're ready to tackle graphs — the most general form of non-linear data structures. Trees are actually a special case of graphs (connected, acyclic, with a root).

Continue the DSA series:

Next: Graphs & Graph Algorithms — BFS, DFS, shortest paths, topological sort
Previous: Stacks & Queues — LIFO and FIFO data structures
Series Overview: Data Structures & Algorithms Roadmap

Introduction

What You'll Learn

Prerequisites

1. Tree Fundamentals

1.1 What Is a Tree?

1.2 Tree Terminology

1.3 Types of Trees

2. Binary Trees

2.1 Binary Tree Types

2.2 Binary Tree Node Implementation

3. Tree Traversals — DFS and BFS

3.1 DFS: Inorder Traversal (Left → Root → Right)

3.2 DFS: Preorder Traversal (Root → Left → Right)

3.3 DFS: Postorder Traversal (Left → Right → Root)

3.4 BFS: Level-Order Traversal

3.5 Traversal Summary

4. Binary Search Trees (BST)

4.1 BST Search

4.2 BST Insert

4.3 BST Delete

4.4 BST Complexity Summary

5. Balanced BSTs — Brief Overview

5.1 AVL Trees

5.2 Red-Black Trees

5.3 When to Use What

6. Trie (Prefix Tree) — Introduction

7. Classic Interview Problems

Problem 1: Maximum Depth of Binary Tree

Problem 2: Invert Binary Tree

Problem 3: Validate Binary Search Tree

Problem 4: Lowest Common Ancestor (LCA)

Problem 5: Check If Tree Is Balanced

Problem 6: Path Sum

Problem 7: Serialize and Deserialize Binary Tree

Problem 8: Build Tree from Inorder and Preorder

8. Pattern Recognition Guide

9. Complexity Reference

Time Complexity by Operation

Space Complexity

10. Practice Problems

Easy (Start Here)

Medium (Build Confidence)

Hard (Interview Ready)

Summary and Key Takeaways

What's Next?

📬 Subscribe to Newsletter

💬 Comments