Linked lists and trees

Most linked list problems are about changing links without losing your way. To reverse a list, keep two parts: the part already reversed, and the part not yet touched. Save next before you overwrite it. Otherwise you lose the only link to the rest of the list. All the pointer moves exist to keep the rest of the list reachable.

Use a dummy head node when the first node might change. When merging sorted lists, the output so far holds the smallest items used, and each list's head is its smallest unused item. For cycles, finding that a cycle exists is a different problem from finding where it starts.

Tree recursion gets easier when each call has a small, clear job. For height, an empty tree has height 0, and a node returns one plus its taller child's height. To check balance, a call can return a height or a "not balanced" signal. That way no ancestor recomputes a height.

For the diameter, separate what a call returns to its parent from the best answer found anywhere. The parent can only extend one branch downward, so return max(left_height, right_height) + 1. But a path whose highest node is the current node can use both children, so its length in edges is left_height + right_height. Every path has one highest node, so checking this at every node covers every path.

To validate a binary search tree, a node must satisfy rules from every ancestor, not only its parent. Pass down a lower and upper limit. Or show that an inorder traversal is strictly increasing, given no duplicates. Use "no limit" for a missing limit, not a made-up number that could rule out a real value.

The traversal order follows what depends on what. Preorder handles a node before its children. Postorder combines the children's answers. Inorder visits a BST in sorted order. Level order uses a queue and handles nodes by distance from the root. Visiting n nodes costs O(n). Recursion goes as deep as the tree's height, which is n for a chain and can overflow the call stack.

Practice: LC 206 Reverse Linked List, LC 21 Merge Two Sorted Lists, LC 19 Remove Nth Node From End, LC 104 Maximum Depth of Binary Tree, LC 110 Balanced Binary Tree, LC 98 Validate Binary Search Tree, LC 543 Diameter of Binary Tree, LC 236 Lowest Common Ancestor.

Check your understanding: What exactly does one call return? What information goes down the tree, and what comes back up? Can the parent extend the branch you return, or is it a finished path?