Trees

A binary tree is a collection of nodes where each node holds a value and up to two children, conventionally called left and right. In Python, the minimal representation is a class with three fields:

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

What makes trees special as a data structure — and what makes them a favorite interview topic — is that they are recursively defined. A tree is either empty (None), or it is a node plus two subtrees that are themselves trees. This self-similar definition is exactly why recursion is the natural default tool for tree problems: any function you write to solve a problem on "a tree" can usually be expressed as "combine the answer for the left subtree with the answer for the right subtree, plus something about the current node." You don't need to reason about the whole tree at once; you only need to define the base case (usually an empty node) and the recursive case, and trust that the recursion handles the rest.

That said, recursion isn't always the right call. Recursive solutions cost O(h) stack space, where h is the tree's height — fine for balanced trees (h = O(log n)) but risky for a degenerate, linked-list-shaped tree of depth n, where you can hit a stack overflow on large inputs. Level-order problems (like finding the widest level or the right side view) are also usually cleaner with an explicit queue and iterative BFS, since "process nodes level by level" doesn't map naturally onto a single recursive call. As a rule of thumb: reach for recursion (DFS) when the problem is naturally about paths from root to leaf, subtree properties, or combining answers from children; reach for an explicit stack or queue (BFS) when the problem is naturally about levels, breadth, or you need to avoid deep call stacks.

Traversal orders. The three classic depth-first orders differ only in when you visit the current node relative to its children: preorder visits node-left-right (useful for copying/serializing a tree, since it visits parents before children), inorder visits left-node-right (useful for BSTs, since it visits values in sorted order), and postorder visits left-right-node (useful when children must be fully processed before the parent, such as computing subtree heights or deleting a tree bottom-up). Level-order traversal (BFS) visits nodes level by level using a queue, and underlies right-side-view and width problems in this subject.

The BST invariant. A Binary Search Tree adds an ordering rule: for every node, every value in its left subtree is smaller and every value in its right subtree is larger. This invariant is what makes search, insert, and delete run in O(log n) on a balanced BST — at each step you eliminate half the remaining tree, the same way binary search eliminates half an array. But nothing forces a BST to stay balanced; if you insert values in sorted order with no rebalancing, the tree degenerates into a linked list and every operation becomes O(n). A subtle but common bug is validating a BST by only checking "is this node's value greater than its left child and less than its right child" locally — that misses violations from a node several levels up. The correct approach passes down a valid (low, high) bound as you recurse, so a node deep in the left subtree is checked against the nearest ancestor that constrains it, not just its immediate parent.

A reusable pattern: return more than one thing. Several problems here (balance checking, diameter, max path sum) are solved elegantly by having each recursive call return a small tuple or combined value instead of a single number — e.g., "return (height, is_balanced) for this subtree" lets a parent call combine both pieces of information in O(1) work per node, instead of recomputing height separately (which would degrade a naive balance check from O(n) to O(n^2)).

Complexity. Nearly every tree problem here is O(n) time, since you must at least look at every node once. Space is typically O(h) for the recursion stack (or O(w) for BFS, where w is the maximum width of a level), plus O(n) for any output structure you build (like a serialized string or a list of columns).

Common pitfalls: validating BSTs with only local comparisons instead of ancestor bounds; forgetting that a "path" for max-path-sum problems can bend at a node (go up into one child and back down into the other) without ever reaching the root or a leaf, and that a path also isn't required to include more than one node; off-by-one and index-overflow errors when tracking position indices for level-width problems, especially with very skewed trees where position values can grow exponentially; and forgetting to handle None children explicitly when comparing trees for symmetry.

This subject covers twelve problems in increasing difficulty: inverting a binary tree, validating that a tree is height-balanced, computing the right side view via BFS, finding the widest level, validating the BST invariant with bounds, finding the lowest common ancestor of two nodes, reconstructing a tree from its preorder and inorder traversals, finding the maximum path sum along any path, checking whether a tree is symmetric, grouping nodes by vertical column, finding the kth smallest value in a BST, and designing a serialize/deserialize scheme for arbitrary binary trees.