Binary Trees & BSTs

Intro

A binary tree is a hierarchical structure where each node has up to two children (left, right). A binary search tree (BST) adds a single invariant: for every node, all values in its left subtree are less, and all values in its right subtree are greater. That invariant is what enables $O(log n)$ search, insert, and delete in a balanced tree. Most interview tree problems reduce to recursion, define a function on a node and combine subtree results.

In-depth description

Traversals are the starting point:

Preorder (root → left → right): useful for serializing the structure itself.
Inorder (left → root → right): on a BST, yields values in sorted order. Critical insight.
Postorder (left → right → root): useful for subtree computations (delete, aggregate up).
Level-order (BFS): traverse by depth using a queue; used for level-dependent problems.

Vanilla BSTs degrade to $O(n)$ on sorted input (they become a linked list). Self-balancing variants, AVL, red-black trees, B-trees, maintain $O(log n)$ depth via rotations. Java’s TreeMap/TreeSet and C++‘s std::map/std::set are red-black trees. Python has no built-in balanced BST; use sortedcontainers.SortedList or build workarounds.

Interview patterns:

Recursion on subtrees: define f(node) in terms of f(node.left) and f(node.right). Max Depth, Diameter, Symmetric, Invert are all one-liners in this form.
Returning tuples from recursion: when you need multiple pieces of info about a subtree (e.g., “max depth and whether balanced”), return a tuple.
Tree DP: when a decision at a node depends on decisions at its children; e.g., House Robber III, Binary Tree Cameras.
Iterative traversal: replace recursion with an explicit stack (prevents stack overflow on deep trees).
LCA (Lowest Common Ancestor): recursive case analysis; a staple.

Time complexity

Operation	Balanced BST	Unbalanced	Vanilla binary tree
Search	$O(log n)$	$O(n)$	$O(n)$
Insert	$O(log n)$	$O(n)$	-
Delete	$O(log n)$	$O(n)$	-
Traversal	$O(n)$	$O(n)$	$O(n)$
Space	$O(n)$	$O(n)$	$O(n)$

Common uses in DSA

Hierarchical data modeling: file systems, DOM, ASTs, expression trees.
Ordered map / sorted set operations: TreeMap, std::map, SortedList for “give me the next-largest key” and range queries.
Recursive subtree problems: Maximum Depth, Invert Binary Tree, Diameter, Symmetric Tree, Path Sum.
Lowest Common Ancestor: LCA of a Binary Tree, LCA of a BST.
Tree DP and serialization: House Robber III, Binary Tree Cameras, Serialize and Deserialize Binary Tree.

Canonical LeetCode problems: #98 Validate BST, #104 Maximum Depth, #226 Invert Binary Tree, #235 LCA of a BST, #297 Serialize and Deserialize Binary Tree, #543 Diameter of Binary Tree, #572 Subtree of Another Tree.

Python example

from collections import deque

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

# Inorder traversal (recursive)
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Level-order (BFS)
def level_order(root):
    if not root:
        return []
    result, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            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

# Max depth
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

# Validate BST (using inorder property: sorted strictly ascending)
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
    if not root:
        return True
    if not (low < root.val < high):
        return False
    return (is_valid_bst(root.left, low, root.val)
            and is_valid_bst(root.right, root.val, high))

# Lowest Common Ancestor
def lca(root, p, q):
    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)
    return root if left and right else (left or right)

LeetCode problems

Binary trees (and BSTs) drive all 15 NeetCode 150 problems in the Trees category.

Trees:

226. Invert Binary Tree
104. Maximum Depth of Binary Tree
543. Diameter of Binary Tree, height + accumulator DFS
110. Balanced Binary Tree, bottom-up DFS with sentinel
100. Same Tree
572. Subtree of Another Tree
235. Lowest Common Ancestor of a BST, iterative BST walk
102. Binary Tree Level Order Traversal
199. Binary Tree Right Side View
1448. Count Good Nodes in Binary Tree, path-state DFS
98. Validate Binary Search Tree, recursive bounds
230. Kth Smallest Element in a BST, iterative inorder
105. Construct Binary Tree from Preorder and Inorder
124. Binary Tree Maximum Path Sum, tree DP with accumulator
297. Serialize and Deserialize Binary Tree