T

Trees & BSTs

Hierarchical data. DFS (pre/in/post-order) and BFS. BST enables O(log n) search.

Trees & Binary Search Trees

Tree Taxonomy

| Type | Definition | |------|-----------| | Binary tree | Each node has at most 2 children | | BST | Binary tree where left < node < right (strict) | | Balanced tree | Heights of subtrees differ by at most 1 — guarantees O(log n) ops. Examples: AVL tree, Red-Black tree | | Complete binary tree | Every level filled except possibly the last, which fills left-to-right | | Full binary tree | Every node has exactly 0 or 2 children | | Perfect binary tree | Full AND complete — all leaves at same level. Has exactly 2^k − 1 nodes where k = number of levels |

Tree Properties

  • Height: Longest path from root to leaf (edges)
  • Depth: Distance from root to a specific node (edges)
  • Level: Root is level 0, children are level 1, etc.
  • Diameter: Longest path between any two nodes (may not pass through root)

BST Complexity

| Operation | Average (balanced) | Worst (skewed) | |-----------|--------------------|----------------| | Search | O(log n) | O(n) | | Insert | O(log n) | O(n) | | Delete | O(log n) | O(n) |

Python Node Template

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

DFS Traversals

def preorder(node):   # current → left → right  (preserves tree structure)
    if not node: return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

def inorder(node):    # left → current → right  (SORTED for BST!)
    if not node: return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

def postorder(node):  # left → right → current  (children before parent)
    if not node: return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

All traversals can also be done iteratively using an explicit stack — avoids Python recursion depth limits on skewed trees.

BFS (Level-Order)

from collections import deque

def level_order(root):
    if not root: return []
    result, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):   # process exactly one level
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        result.append(level)
    return result

Tree Height & Balance Check

def height(node):
    if not node: return 0
    return 1 + max(height(node.left), height(node.right))

def is_balanced(node):
    """O(n) — return -1 if unbalanced, height otherwise."""
    def check(n):
        if not n: return 0
        l = check(n.left)
        r = check(n.right)
        if l == -1 or r == -1 or abs(l - r) > 1:
            return -1
        return 1 + max(l, r)
    return check(node) != -1

Validate BST (min/max bounds — the right approach)

Local parent-child checks are not enough — a node must satisfy ALL ancestor constraints:

def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
    if not root: return True
    if root.val <= lo or root.val >= hi:
        return False
    return (is_valid_bst(root.left,  lo,       root.val) and
            is_valid_bst(root.right, root.val, hi))

Tree Construction: Sorted Array → Minimal BST

Always pick the middle element as root — recursively for each half:

def sorted_array_to_bst(arr):
    if not arr: return None
    mid = len(arr) // 2
    node = TreeNode(arr[mid])
    node.left  = sorted_array_to_bst(arr[:mid])
    node.right = sorted_array_to_bst(arr[mid+1:])
    return node
# Time: O(n), Space: O(n) for tree + O(log n) for recursion stack

You can also reconstruct trees from:

  • Preorder + inorder: root from preorder, split inorder at root
  • Postorder + inorder: root from postorder, split inorder at root

In-Order Successor in BST

Given a node, find the next node in in-order traversal:

def inorder_successor(node):
    # Case 1: node has a right subtree
    # → successor is the LEFTMOST node in the right subtree
    if node.right:
        curr = node.right
        while curr.left:
            curr = curr.left
        return curr

    # Case 2: no right subtree
    # → go up parent chain until we come from a LEFT child
    # → that parent is the successor
    child = node
    parent = node.parent
    while parent and child is parent.right:
        child = parent
        parent = parent.parent
    return parent   # None if node is the maximum
# Time: O(h), Space: O(1)

Lowest Common Ancestor (LCA)

With parent pointers:

  1. Get depth of both nodes
  2. Move deeper node up until same depth
  3. Move both up together until they meet

Without parent pointers (DFS):

def lca(root, p, q):
    """Returns LCA node if both p and q are in tree."""
    if not root or root is p or root is q:
        return root
    left  = lca(root.left,  p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root   # p in one subtree, q in the other
    return left or right
# Time: O(n), Space: O(h)

Subtree Matching

Naive: find T2's root in T1 via BFS, then compare trees simultaneously — O(n × m).

Better approach (serialize + substring): Serialize both trees using preorder with null markers (e.g. "4 2 # # 6 # #"), then check if T2's serialized form is a substring of T1's. Use KMP for O(n + m).

Binary Heaps

A min-heap is a complete binary tree where every parent ≤ its children (root = minimum). Max-heap: every parent ≥ its children (root = maximum).

Array implementation (space-efficient):

Parent at index i → children at 2i+1 and 2i+2
Child at index i  → parent at (i-1)//2

import heapq

# Min-heap in Python
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappop(heap)   # → 1 (minimum)

# Max-heap: negate values
heapq.heappush(heap, -val)
max_val = -heapq.heappop(heap)

| Operation | Time | |-----------|------| | Insert (push) | O(log n) | | Extract min/max | O(log n) | | Peek | O(1) |

Use cases: Dijkstra's algorithm, merge k sorted lists, find k largest/smallest, event simulation.

Tries (Prefix Trees)

An N-ary tree where each node represents a character. End of word marked with a * flag.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self): self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True

    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children: return False
            node = node.children[c]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children: return False
            node = node.children[c]
        return True

Lookup is O(k) where k = length of string — similar to a hash map (which still hashes each character).

Word search / word break: Build a Trie, run DFS+backtracking from each cell. At each step, check if current path is a valid prefix — prune early if not, which drastically reduces search space.

Key Interview Tips

  • Inorder traversal of a BST produces a sorted sequence — use this for validation, k-th smallest, etc.
  • Pre/post order preserve tree structure — useful for serialisation
  • Recursive solutions are natural; switch to iterative on skewed trees to avoid stack overflow
  • BST deletion: leaf → remove directly; one child → replace; two children → swap with in-order successor then delete successor
  • For "find k-th smallest in BST": inorder traversal + counter