Trees

Every problem in this topic is really the same question in disguise: "what does this node need from its children, and what does it hand back to its parent?" Once you can answer that for a specific problem, the recursion almost writes itself — the hard part is figuring out exactly what that handoff should contain, not the recursive mechanics themselves.

The core mental model: trust the recursion

Invert Binary Tree and Maximum Depth are the simplest possible cases: a node's answer is a small combination of its children's answers (swap them; take the max and add one), and the base case (an empty tree) is trivial. Don't try to trace through the whole tree by hand — define what a node needs from its children, write that as the recursive step, get the base case right, and let recursion handle the rest.

BFS vs. DFS: pick the traversal the problem is actually asking for

Binary Tree Level Order Traversal and Right Side View both want information organized by depth — that's breadth-first search with a queue, not recursion. The trick that makes level-by-level BFS clean: record the queue's size at the start of each iteration before processing anything — that number is exactly how many nodes belong to the current level, even though their children get pushed onto the same queue during that same pass.

Kth Smallest Element in a BST wants values in sorted order — that's an inorder traversal (left, node, right), which is the one traversal order that visits a BST's values from smallest to largest, for free, with no sorting step at all.

The BST property is a global constraint, not a local one

Validate Binary Search Tree's classic trap: checking a node only against its immediate parent passes plenty of genuinely invalid trees. A node in the left subtree of some ancestor must stay below that ancestor's value too, not just its direct parent's — the fix is threading a valid (low, high) range through the recursion, tightening one side at each step down.

// WRONG: only compares each node to its immediate parent.
// Passes a tree where a deep-left node is greater than an ANCESTOR
// several levels up, even though it's only compared against its parent.
bool check(TreeNode* node) {
    if (node->left && node->left->val >= node->val) return false;
    if (node->right && node->right->val <= node->val) return false;
    return check(node->left) && check(node->right);
}

// RIGHT: every node carries a valid (low, high) range from its ancestors,
// not just a comparison against its immediate parent.
bool validate(TreeNode* node, long long lo, long long hi) {
    if (!node) return true;
    if (node->val <= lo || node->val >= hi) return false;
    return validate(node->left, lo, node->val) && validate(node->right, node->val, hi);
}

What a BST's ordering buys you: O(h) instead of O(n)

Lowest Common Ancestor of a BST and Lowest Common Ancestor of a Binary Tree solve the exact same problem, but the BST version only needs O(h) time (h = tree height) because comparing values against the current node tells you which single subtree to descend into — no need to search both sides the way the general-tree version genuinely must. Recognizing when a data structure's extra guarantee (sortedness, here) unlocks a cheaper algorithm — rather than defaulting to the general-case approach out of habit — is the same skill this course has built since Binary Search.

Common mistakes

• Confusing "return value" with "answer" in problems like Maximum Path Sum — what a node hands its parent (a single extendable branch) is not always the same thing as the best answer seen so far (which is allowed to use both branches at once, since it won't be extended further).
• Checking a BST node only against its immediate parent instead of the full valid range inherited from every ancestor.
• Treating a negative subtree contribution as mandatory instead of optional — Maximum Path Sum clamps a negative branch to 0 (skip it) rather than being forced to include it just because it exists.
• Re-searching linearly for a value's position in Construct Binary Tree from Preorder and Inorder Traversal instead of building an index map once up front — turns an O(n) algorithm into O(n²) for no reason.