Binary Tree Traversal

Problem: Given the root of a binary search tree and an integer k, return the k-th smallest value (1-indexed).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is n. · 1 ≤ k ≤ n ≤ 10⁴ · 0 ≤ Node.val ≤ 10⁴

From brute force to the pattern: Collecting every value and sorting is O(n log n). The BST's in-order is already sorted, so walking it and stopping after k nodes is O(h + k).

Spot it: "BST" + "kth smallest" = sorted order is needed. Inorder traversal of a BST visits values in ascending order.

Key insight: Use the iterative inorder so you can stop early the moment you've visited k nodes. Cost is O(h + k), not O(n).

Approach:

1. Start with current = root, an empty stack, and visited_count = 0.
2. Slide left: push current and move to current.left until current is None.
3. Pop the top node. It's the next-smallest value. Add 1 to visited_count.
4. If visited_count == k, return this value (stop early).
5. Otherwise set current = current.right and repeat from step 2.

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []                # ancestors waiting to be visited
        current = root            # where we are in the tree
        visited_count = 0         # how many values we have visited so far (in sorted order)
        while current is not None or len(stack) > 0:
            # Go as far left as possible, remembering the path on the stack.
            while current is not None:
                stack.append(current)
                current = current.left
            # The top of the stack is the next smallest value.
            current = stack.pop()
            visited_count = visited_count + 1
            # Is this the k-th smallest? Then stop early; no need to see the rest.
            if visited_count == k:
                return current.val
            # Otherwise continue with this node's right subtree.
            current = current.right
        return -1                 # only reached if k is bigger than the number of nodes

What the code is doing, line by line:

1. stack, current and visited_count are set up. The count tells us how many values we have seen in sorted order.
2. The inner while slides left from current, pushing every node. The smallest unvisited value ends up on top of the stack.
3. stack.pop() gives the next smallest value, so visited_count goes up by 1.
4. If the count has reached k, that value is the answer and we return immediately, without visiting the rest of the tree.
5. Otherwise current = current.right: the next bigger values live in the right subtree (or in an ancestor on the stack).

Dry run on root = [5,3,6,2,4,null,null,1], k = 3:

Edge cases to test:

• k = 1 → the leftmost node.
• k = n → the rightmost node.
• A completely skewed tree.

Complexity: O(h + k) time, O(h) space.

Problem: Return True if the tree is a valid BST: every node's left subtree holds only smaller values, its right subtree only larger values, recursively.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [1, 10⁴]. · -2³¹ ≤ Node.val ≤ 2³¹ - 1

From brute force to the pattern: Checking, for every node, that its whole left subtree is smaller and its whole right subtree larger is O(n²). Passing bounds down (or one in-order pass) checks it in O(n).

Spot it: "valid BST" means "is the inorder sequence strictly increasing?"

Key insight: Checking only node.left.val < node.val is the classic trap. In [5,4,6,null,null,3,7] the 3 is a right-subtree descendant of 5, which breaks the rule, but every parent-child pair looks fine. Comparing each inorder value with the previous inorder value catches it.

Approach:

1. Run the iterative inorder traversal (slide left, pop, go right).
2. Keep previous_value = the last value you popped.
3. Each time you pop a node, if previous_value exists and current.val <= previous_value, the order isn't strictly increasing: return False.
4. Update previous_value and continue. If the traversal finishes, return True.

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        stack = []                # ancestors waiting to be visited
        current = root
        previous_value = None     # the value we visited just before (None = nothing yet)
        while current is not None or len(stack) > 0:
            # Slide left, pushing every node.
            while current is not None:
                stack.append(current)
                current = current.left
            # Visit the next node in inorder.
            current = stack.pop()
            # Inorder of a BST must be STRICTLY increasing.
            if previous_value is not None:
                if current.val <= previous_value:
                    return False  # out of order (or a duplicate): not a valid BST
            previous_value = current.val
            # Move on to the right subtree.
            current = current.right
        return True               # every value was bigger than the one before it

What the code is doing, line by line:

1. Same iterative inorder as before, plus previous_value, the last value we visited (None at the start).
2. The inner while slides left, pushing nodes. stack.pop() then gives the next value in inorder.
3. If there is a previous value and the current one is not bigger, the inorder sequence is not strictly increasing, so the tree is not a BST: return False.
4. Otherwise remember this value in previous_value and go to the right subtree.
5. If the loop finishes without a problem, every value was bigger than the one before it: return True.

Dry run on root = [5,1,4,null,null,3,6] (expected False):

Alternative (preorder, passing info down): check(node, lo, hi) requires lo < node.val < hi, then recurses with (lo, node.val) on the left and (node.val, hi) on the right.

Edge cases to test:

• A deep violation, e.g. [5, 4, 6, null, null, 3, 7] (3 is inside the right subtree of 5).
• Duplicate values → invalid (strictly increasing is required).
• Values at the integer limits (use infinities as the initial bounds).

Complexity: O(n) time, O(h) space.

Problem: You get the preorder and inorder lists of a tree with unique values. Rebuild the tree.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ preorder.length ≤ 3000 · inorder.length == preorder.length · -3000 ≤ preorder[i], inorder[i] ≤ 3000 · preorder and inorder consist of unique values. · Each value of inorder also appears in preorder. · preorder is guaranteed to be the preorder traversal of the tree. · inorder is guaranteed to be the inorder traversal of the tree.

From brute force to the pattern: Searching the inorder list for each root is O(n) per node, O(n²) overall. A hash map from value to inorder index makes every split O(1): O(n).

Spot it: "construct from traversals" means you have to know exactly what each order guarantees.

Key insight: Preorder's first value is always the root. Find that root in inorder: everything to its left is the left subtree, everything to its right is the right subtree. Keep a pointer into preorder and build left before right, because preorder is root → left → right. A hash map gives O(1) lookups of positions in inorder.

Approach:

1. Build a map value → index in inorder for O(1) lookups.
2. Keep a pointer self.next_root into preorder. The value there is the root of the subtree you're about to build.
3. The helper method build(low, high) builds the subtree whose values are inorder[low..high]. If low > high, return None.
4. Take preorder[self.next_root] as the root, advance self.next_root, and find its inorder position middle.
5. Build the left subtree from (low, middle-1) FIRST, then the right subtree from (middle+1, high). That's the same order preorder uses.

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # Remember where each value sits in "inorder", so we can find it in O(1).
        self.index_in_inorder = {}
        for i in range(len(inorder)):
            value = inorder[i]
            self.index_in_inorder[value] = i
        # Keep preorder on self so the helper method can read it.
        self.preorder = preorder
        # Position in preorder of the next root we will create.
        self.next_root = 0
        # Build the whole tree: it uses every position of inorder, 0 .. n-1.
        return self.build(0, len(inorder) - 1)

    def build(self, low: int, high: int) -> Optional[TreeNode]:
        # Builds the subtree made of the values inorder[low..high] (helper method).
        if low > high:
            return None           # empty range: no subtree here
        # The next value in preorder is the root of this subtree.
        root_value = self.preorder[self.next_root]
        self.next_root = self.next_root + 1
        node = TreeNode(root_value)
        # Everything left of the root in inorder is its left subtree, the rest is its right.
        middle = self.index_in_inorder[root_value]
        node.left = self.build(low, middle - 1)      # LEFT first: same order as preorder
        node.right = self.build(middle + 1, high)
        return node

What the code is doing, line by line:

1. The for loop builds self.index_in_inorder: value → its position in inorder. Looking up a root's position is then O(1).
2. self.preorder and self.next_root are stored on self so the helper method build can read and advance them across recursive calls.
3. build(low, high) builds the subtree whose values are inorder[low..high]. If the range is empty (low > high), there is no subtree: return None.
4. The value at preorder[self.next_root] is the root of this subtree (preorder always lists the root first). We create the node and move the pointer forward.
5. middle is where that root sits in inorder. Positions low..middle-1 are its left subtree, middle+1..high its right subtree.
6. The left subtree is built before the right one, because preorder lists root, then all of the left subtree, then the right.

Dry run on preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] (each row is one call that creates a node; calls with an empty range just return None):

Edge cases to test:

• A single node.
• A left-skewed or right-skewed tree.
• Values are unique, which is what makes the map work.

Complexity: O(n) time, O(n) space for the map (plus O(h) recursion).

Problem: A path is any chain of connected nodes (it doesn't have to pass through the root, and it can't branch). Return the largest possible sum of node values on a path. Values may be negative.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [1, 3 * 10⁴]. · -1000 ≤ Node.val ≤ 1000

From brute force to the pattern: Trying every pair of endpoints and summing the path between them is O(n²) or worse. A single post-order pass computes the best path bending at each node: O(n).

Spot it: "max path" in a tree, and the best answer at a node depends on the best answers below it. That's postorder.

Key insight: Each node does two different jobs. (1) It updates the global best with a path that bends at it: val + left + right. (2) It returns to its parent a path that goes down only one side: val + max(left, right). A parent can only extend one branch. Clamp negative branch gains to 0 (just don't take that branch).

Approach:

1. Write a helper method gain(node) = the best sum of a path that starts at node and goes down one side.
2. Postorder: compute left_gain and right_gain from the children, and replace a negative gain with 0. Negative branches are dropped.
3. Update self.best with node.val + left_gain + right_gain, the path that bends at this node.
4. Return node.val plus the bigger of left_gain and right_gain. A parent can extend only one branch.
5. The answer is self.best after calling self.gain(root).

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        # Best path sum seen anywhere so far. Start at "minus infinity"
        # so that even a single negative node can beat it.
        self.best = float("-inf")
        self.gain(root)           # walks the whole tree and updates self.best
        return self.best

    def gain(self, node: Optional[TreeNode]) -> int:
        # Helper method: best sum of a path that STARTS at node and goes DOWN one side.
        if node is None:
            return 0
        # Postorder: get the children's answers first.
        left_gain = self.gain(node.left)
        if left_gain < 0:
            left_gain = 0         # a negative branch only hurts: don't take it
        right_gain = self.gain(node.right)
        if right_gain < 0:
            right_gain = 0
        # Job 1: a path that BENDS here uses both sides. Is it the best so far?
        path_through_node = node.val + left_gain + right_gain
        if path_through_node > self.best:
            self.best = path_through_node
        # Job 2: the parent can extend only ONE side, so return the better one.
        if left_gain > right_gain:
            return node.val + left_gain
        else:
            return node.val + right_gain

What the code is doing, line by line:

1. maxPathSum sets self.best to minus infinity, calls the helper gain on the root, and returns whatever best was found.
2. gain(node) returns the best sum of a path that starts at node and goes down one side. An empty subtree gives 0.
3. It first computes the children's gains (postorder). A negative gain is replaced by 0, meaning "don't go down that branch".
4. path_through_node is a path that bends at this node and uses both sides. If it beats self.best, it becomes the new best.
5. Finally it returns the node's value plus the better of the two sides, because a parent can only continue the path down one side.

Dry run on root = [-10,9,20,null,null,15,7] (rows are in postorder, the order gain finishes):

The answer is 42: the path 15 → 20 → 7.

Edge cases to test:

• All negative values → the single largest value.
• A single node.
• The best path doesn't pass through the root.

Complexity: O(n) time, O(h) space.

Problem: Design serialize(root) -> str and deserialize(str) -> root so that a tree survives the round trip.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [0, 10⁴]. · -1000 ≤ Node.val ≤ 1000

From brute force to the pattern: This is a design task rather than an optimisation. The main pitfall is leaving out the None markers, which makes the tree ambiguous. A pre-order or level-order encoding with explicit nulls is O(n) both ways.

Spot it: "encode/decode a tree": preorder with explicit null markers is self-describing.

Key insight: If you write # for every missing child, a preorder string alone determines the tree. That's different from 105, which needed two traversals. Deserialize by reading tokens in the same preorder: make the node, then build its left, then its right.

Approach:

1. Serialize: preorder walk (helper method serialize_walk). Write the value for a node and # for every missing child, then join with commas.
2. Deserialize: split on commas and keep self.position, the index of the next token to read.
3. deserialize_build() reads one token. # means None. Otherwise create the node, then call deserialize_build() for its left, then its right.
4. Because both directions use the same preorder, the tokens are consumed in exactly the order they were written.

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        tokens = []                       # one string per node, "#" for a missing child
        self.serialize_walk(root, tokens)
        # [1,2,3,null,null,4,5] -> "1,2,#,#,3,4,#,#,5,#,#"
        return ",".join(tokens)

    def serialize_walk(self, node: Optional[TreeNode], tokens: List[str]) -> None:
        # Helper method: PREORDER walk (me, then left, then right).
        if node is None:
            tokens.append("#")            # null marker keeps the shape of the tree
            return
        tokens.append(str(node.val))
        self.serialize_walk(node.left, tokens)
        self.serialize_walk(node.right, tokens)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        self.tokens = data.split(",")     # "1,2,#" -> ["1", "2", "#"]
        self.position = 0                 # index of the next token to read
        return self.deserialize_build()

    def deserialize_build(self) -> Optional[TreeNode]:
        # Helper method: read tokens in the SAME preorder that serialize wrote them.
        token = self.tokens[self.position]
        self.position = self.position + 1
        if token == "#":
            return None                   # a missing child
        node = TreeNode(int(token))
        node.left = self.deserialize_build()     # next tokens describe the left subtree
        node.right = self.deserialize_build()    # then the right subtree
        return node

What the code is doing, line by line:

1. serialize creates an empty list tokens, lets the helper method serialize_walk fill it, and joins the tokens with commas.
2. serialize_walk is a preorder walk: a missing child adds "#"; a real node adds its value, then walks left, then right.
3. deserialize splits the string back into a list and sets self.position = 0, the index of the next token to read.
4. deserialize_build reads one token and moves the position on. "#" means None. Otherwise it creates the node and builds its left child, then its right child, from the following tokens.
5. Because both directions use the same preorder (me, left, right), tokens are read back in exactly the order they were written.

Dry run of serialize on [1,2,3,null,null,4,5]:

deserialize reads those 11 tokens in the same order: 1 becomes the root, 2 its left child, the two # close 2's children, 3 becomes the root's right child, and so on.

Edge cases to test:

• An empty tree.
• Negative and multi-digit values (use a separator between tokens).
• A skewed tree (deep recursion; level order avoids it).

Complexity: O(n) time and space for both directions.

Problem: Return the values of a binary tree in inorder (left, node, right). Do it without recursion.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [0, 100]. · -100 ≤ Node.val ≤ 100

From brute force to the pattern: The recursive version is three lines but uses the call stack. The explicit-stack version gives the same O(n) traversal and is the basis for BST iterators and early stopping.

Spot it: "inorder" is literally in the name. The iterative version is the building block for 98, 173 and 230.

Approach:

1. Keep a stack of ancestors you still need to come back to, and a pointer current.
2. Slide down-left from current, pushing every node.
3. Pop: that's the leftmost node not yet visited. Record its value.
4. Move to its right child and repeat until both current is None and the stack is empty.

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        out = []                  # the answer, in inorder
        stack = []                # ancestors we still have to come back to
        current = root
        # Still a node to visit, or an ancestor to return to?
        while current is not None or len(stack) > 0:
            # Slide left, remembering every ancestor.
            while current is not None:
                stack.append(current)
                current = current.left
            # Leftmost node not visited yet.
            current = stack.pop()
            out.append(current.val)   # INORDER: record between left and right
            # Now handle its right subtree.
            current = current.right
        return out

What the code is doing, line by line:

1. out is the answer, stack holds ancestors still to be visited, current is our position.
2. The inner while slides left from current, pushing each node.
3. stack.pop() returns the leftmost node not yet visited. Its value is recorded (left side is already done, right side comes next: that's inorder).
4. current = current.right moves into the right subtree. The outer loop stops when there is no current node and the stack is empty.

Dry run on root = [1,null,2,3] (1 at the root, 2 its right child, 3 the left child of 2):

Edge cases to test:

• An empty tree → [].
• Only left children.
• Only right children.

Complexity: O(n) time, O(h) space.

Problem: Return the node values level by level, from top to bottom and left to right within each level, as a list of lists.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [0, 2000]. · -1000 ≤ Node.val ≤ 1000

From brute force to the pattern: Computing each node's depth with DFS and grouping by depth also works in O(n). BFS produces the levels directly, in order, with one queue.

Spot it: "level by level" means BFS on the tree with a queue.

Approach:

1. If the tree is empty, return []. Otherwise put the root in a deque.
2. While the queue isn't empty, freeze level_size = len(queue).
3. Pop exactly level_size nodes, collect their values into level, and push their children.
4. Append level to the result.

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        result = []
        # deque: queue.append(x) adds at the BACK, queue.popleft() takes from the FRONT.
        queue = deque()
        queue.append(root)
        while len(queue) > 0:
            level_size = len(queue)       # freeze: exactly the nodes of THIS level
            level = []
            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                # Children go to the back of the queue: they are the next level.
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
            result.append(level)
        return result

What the code is doing, line by line:

1. An empty tree returns []. Otherwise the root goes into the queue.
2. Each round of the outer loop handles one level. level_size is read first, so later children don't sneak into this level.
3. The inner loop pops exactly level_size nodes from the front, records their values, and appends their children to the back.
4. The finished level list is appended to result.

Dry run on root = [3,9,20,null,null,15,7]:

Result: [[3], [9, 20], [15, 7]].

Edge cases to test:

• An empty tree → [].
• A skewed tree (one node per level).
• A complete tree.

Complexity: O(n) time, O(w) space (w = widest level).

Problem: Like level order, but alternate direction: level 0 left→right, level 1 right→left, and so on.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [0, 2000]. · -100 ≤ Node.val ≤ 100

From brute force to the pattern: Level-order BFS plus reversing alternate levels is O(n). Building each level with a deque avoids the extra reverse step.

Spot it: Still "per level", so it's level order. Only the way each level is written changes.

Approach:

1. Run the normal level-order BFS. The queue order stays left→right.
2. For each level, collect values into a list level, always left to right.
3. When going left→right add level as it is. When going right→left copy it backwards (with a while loop) and add the copy.
4. Flip the direction flag after every level.

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        result = []
        # deque: queue.append(x) adds at the BACK, queue.popleft() takes from the FRONT.
        queue = deque()
        queue.append(root)
        left_to_right = True              # direction for the current level
        while len(queue) > 0:
            level_size = len(queue)       # freeze the size of this level
            level = []                    # values of this level, always left to right
            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                # Children ALWAYS go in left-to-right; only the output is flipped.
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
            if left_to_right:
                result.append(level)
            else:
                # Copy the level backwards into a new list.
                reversed_level = []
                i = len(level) - 1
                while i >= 0:
                    reversed_level.append(level[i])
                    i = i - 1
                result.append(reversed_level)
            left_to_right = not left_to_right     # flip the direction for the next level
        return result

What the code is doing, line by line:

1. This is the level-order code from 102, plus a flag left_to_right that starts as True.
2. Inside each level the queue is handled exactly as in 102, so level is always collected left to right.
3. If the flag is True, level is added as it is. If it is False, a while loop copies it from the last item to the first into reversed_level, and that is added instead.
4. left_to_right = not left_to_right flips the direction after every level.

Dry run on root = [3,9,20,null,null,15,7]:

Result: [[3], [20, 9], [15, 7]].

Edge cases to test:

• An empty tree.
• A single node.
• Levels with missing children.

Complexity: O(n) time, O(w) space.

Problem: Imagine standing to the right of the tree. Return the values you can see, from top to bottom. That's the rightmost node of each level.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [0, 100]. · -100 ≤ Node.val ≤ 100

From brute force to the pattern: Collecting every level fully and then taking its last element is still O(n). Either BFS or right-first DFS gives the view in one pass.

Spot it: "one value per row, top to bottom" is a per-level question, so level order.

Approach:

1. Run level-order BFS with a frozen size.
2. While popping the level_size nodes of a level, remember the last one popped.
3. After the level ends, append that last value: it's the rightmost node.

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        view = []                         # one value per level: the rightmost one
        # deque: queue.append(x) adds at the BACK, queue.popleft() takes from the FRONT.
        queue = deque()
        queue.append(root)
        while len(queue) > 0:
            level_size = len(queue)       # freeze the size of this level
            for i in range(level_size):
                node = queue.popleft()
                # The last node popped in this level is the rightmost one.
                if i == level_size - 1:
                    view.append(node.val)
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
        return view

What the code is doing, line by line:

1. An empty tree has no view. Otherwise start the queue with the root.
2. Each round freezes level_size and pops exactly that many nodes, so one round = one level.
3. The counter i tells us how many nodes of this level we have popped. When i == level_size - 1 it's the last one, which is the rightmost node, so its value goes into view.
4. Children are pushed left then right, keeping the queue in left-to-right order for the next level.

Dry run on root = [1,2,3,null,5,null,4]:

Edge cases to test:

• A left child visible because the right side is shorter, e.g. [1, 2] → [1, 2].
• An empty tree.
• Only right children.

Complexity: O(n) time, O(w) space.

Problem: Given two nodes p and q in a binary tree (not a BST), return their lowest common ancestor: the deepest node that has both of them in its subtree. A node counts as its own descendant.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [2, 10⁵]. · -10⁹ ≤ Node.val ≤ 10⁹ · All Node.val are unique. · p != q · p and q will exist in the tree.

From brute force to the pattern: Storing the root-to-node paths of p and q and comparing them is O(n) time and space. One post-order recursion returning the found node (or None) is O(n) with only the recursion stack.

Spot it: Each node needs to know "did my left / right subtree contain p or q?". That information flows up, so postorder.

Approach:

1. Base case: if the node is None, return None; if it is p or q, return it as is.
2. Recurse into the left and right subtrees.
3. If both sides returned something non-null, p and q are split across this node, so this node is the LCA.
4. Otherwise return whichever side is non-null. It carries p, q, or the LCA found deeper down.

class Solution:
    # LeetCode calls the two targets p and q; here they are named node_p and node_q.
    def lowestCommonAncestor(self, root: 'TreeNode', node_p: 'TreeNode', node_q: 'TreeNode') -> 'TreeNode':
        # Ran off the tree: nothing found down here.
        if root is None:
            return None
        # Found one of the targets: report it to the parent.
        if root is node_p or root is node_q:
            return root
        # Postorder: ask both subtrees first.
        found_left = self.lowestCommonAncestor(root.left, node_p, node_q)
        found_right = self.lowestCommonAncestor(root.right, node_p, node_q)
        # One target on each side: this node is where they split, so it is the LCA.
        if found_left is not None and found_right is not None:
            return root
        # Otherwise pass up whatever was found (it may be None).
        if found_left is not None:
            return found_left
        return found_right

What the code is doing, line by line:

1. LeetCode names the two target nodes p and q. The code calls them node_p and node_q so the names say what they are; LeetCode passes them by position, so this still works there.
2. If root is None we fell off the tree: nothing found, return None.
3. If root is node_p or node_q, return it. We don't need to look below it: if the other target is underneath, this node is the LCA anyway.
4. Otherwise search both subtrees (postorder) and keep what each one reports in found_left and found_right.
5. If both are non-None, one target is on each side, so this node is the lowest common ancestor.
6. Otherwise pass up whichever side found something (or None if neither did).

Dry run on root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1:

Edge cases to test:

• p is an ancestor of q → p.
• p and q on opposite sides of the root → the root.
• Deep, unbalanced trees.

Complexity: O(n) time, O(h) space.

Problem: Design an iterator over a BST: next() returns the next smallest value, and hasNext() says whether any remain. Aim for average O(1) time and O(h) memory.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [1, 10⁵]. · 0 ≤ Node.val ≤ 10⁶ · At most 10⁵ calls will be made to hasNext, and next.

From brute force to the pattern: Flattening the whole tree into a list in the constructor uses O(n) memory. The controlled stack keeps only O(h) nodes, with amortised O(1) per next().

Spot it: "next smallest" in a BST is inorder. To "pause" between calls, keep the iterative inorder stack as object state.

Approach:

1. In the constructor, push the root and all of its left descendants (the "slide left" step).
2. next(): pop the top node. That's the answer.
3. Before returning, slide left from that node's right child, pushing nodes. That prepares the next call.
4. hasNext() is just "is the stack non-empty?".

class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.stack = []                   # the paused iterative-inorder stack
        self.push_left(root)              # smallest value ends up on top

    def push_left(self, node: Optional[TreeNode]) -> None:
        # The "slide left" step of iterative inorder: push node and all its left descendants.
        while node is not None:
            self.stack.append(node)
            node = node.left

    def next(self) -> int:
        node = self.stack.pop()           # next smallest value
        self.push_left(node.right)        # its successor lives in the right subtree
        return node.val

    def hasNext(self) -> bool:
        # Values remain exactly when the stack is not empty.
        return len(self.stack) > 0

What the code is doing, line by line:

1. The constructor creates an empty stack and calls push_left(root), so the path down to the smallest value is on the stack with the smallest on top.
2. push_left(node) is the "slide left" step of iterative inorder: push the node, move to its left child, repeat until None.
3. next() pops the top node (the next smallest value). Before returning, it slides left from that node's right child, so the following value is ready on top.
4. hasNext() returns True while the stack still holds nodes.
5. Each node is pushed once and popped once, so over all calls next() costs O(1) on average.

Dry run on root = [7,3,15,null,null,9,20]:

Edge cases to test:

• A single node.
• A skewed tree.
• hasNext() called after the last value → False.

Complexity: next() is amortized O(1) because each node is pushed and popped once. O(h) memory.

Problem: Return True if the two binary trees p and q have the same shape and the same values.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in both trees is in the range [0, 100]. · -10⁴ ≤ Node.val ≤ 10⁴

From brute force to the pattern: Serialising both trees with null markers and comparing the strings works in O(n) but uses extra memory. A lock-step recursion stops at the first difference.

Spot it: Compare two trees node by node → one recursion that takes a node from each tree.

Approach:

1. Both nodes missing → equal so far: True.
2. Exactly one missing, or the values differ → False.
3. Otherwise both left subtrees must be the same and both right subtrees must be the same.

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None and q is None:
            return True            # both empty: identical
        if p is None or q is None:
            return False           # only one is empty: different shape
        if p.val != q.val:
            return False           # same position, different value
        # identical only if BOTH pairs of subtrees are identical
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

What the code is doing, line by line:

1. if p is None and q is None: return True: two empty trees match.
2. if p is None or q is None: return False: we already know they aren't both None, so exactly one is. The shapes differ.
3. if p.val != q.val: return False: same position, different value.
4. return ... and ...: both subtrees must match. and stops early: if the left side fails, the right side is never checked.

Dry run on the example:

p = [1, 2], q = [1, null, 2] (LeetCode Example 2). Returns False.

Edge cases to test:

• Both empty → True.
• Same values, different shape, e.g. [1, 2] vs [1, null, 2].
• Same shape, different values.

Complexity: O(min(m, n)) time (stops at the first difference), O(h) recursion space.

Problem: Return True if the tree is a mirror image of itself around its centre.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [1, 1000]. · -100 ≤ Node.val ≤ 100

From brute force to the pattern: Building a mirrored copy and comparing it with the original is O(n) time and space. Comparing the two halves in mirrored lock-step uses only the recursion stack.

Spot it: A tree is symmetric when its left subtree mirrors its right subtree. "Mirror" is Same Tree with crossed children: a.left pairs with b.right, and a.right with b.left.

Approach:

1. Write a helper mirror(a, b) that checks whether two subtrees mirror each other.
2. Both missing → True; one missing or values differ → False.
3. Otherwise the outer pair (a.left, b.right) and the inner pair (a.right, b.left) must both mirror.
4. The answer is mirror(root.left, root.right).

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def mirror(a, b):
            if a is None and b is None:
                return True
            if a is None or b is None:
                return False
            if a.val != b.val:
                return False
            # outer children pair up, and inner children pair up
            return mirror(a.left, b.right) and mirror(a.right, b.left)

        return mirror(root.left, root.right)

What the code is doing, line by line:

1. def mirror(a, b): true when the subtree at a is the mirror image of the subtree at b.
2. The first three checks are the same as Same Tree: matching emptiness and equal values.
3. mirror(a.left, b.right): the outer edges of the two halves must match.
4. mirror(a.right, b.left): and so must the inner ones.
5. return mirror(root.left, root.right): the root itself sits on the mirror line, so only its two subtrees are compared.

Dry run on the example:

root = [1, 2, 2, 3, 4, 4, 3] (LeetCode Example 1). Returns True. Call the two 2s 2L and 2R.

Edge cases to test:

• A single node → True.
• Same values but asymmetric shape, e.g. [1, 2, 2, null, 3, null, 3] → False.
• An empty subtree on one side only.

Complexity: O(n) time, O(h) recursion space.

Problem: Return the number of nodes on the longest path from the root down to a leaf.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [0, 10⁴]. · -100 ≤ Node.val ≤ 100

From brute force to the pattern: This is already a single O(n) traversal; BFS counting levels works equally well. The recursion is the most direct form.

Spot it: A value that depends on both subtrees → post-order recursion: ask each child for its depth, then combine.

Approach:

1. An empty tree has depth 0.
2. Get the depth of the left and right subtrees recursively.
3. This node adds one level: return 1 + max(left, right).

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        # this node is one more level on top of its deeper subtree
        return 1 + max(left_depth, right_depth)

What the code is doing, line by line:

1. if root is None: return 0: no node, no depth. This is what makes a leaf's depth come out as 1.
2. left_depth, right_depth: the recursion answers the same question for each subtree.
3. return 1 + max(...): the longest path goes through the deeper side, plus this node.

Dry run on the example:

root = [3, 9, 20, null, null, 15, 7] (LeetCode Example 1). Returns 3.

Edge cases to test:

• An empty tree → 0.
• A skewed tree (depth n).
• A single node → 1.

Complexity: O(n) time, O(h) recursion space.

Problem: nums is sorted ascending. Build a height-balanced BST from it (subtree heights differ by at most 1 at every node).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 10⁴ · -10⁴ ≤ nums[i] ≤ 10⁴ · nums is sorted in a strictly increasing order.

From brute force to the pattern: Inserting the values one by one into a BST in sorted order gives a skewed tree. Picking the middle element at each level gives a balanced tree in O(n).

Spot it: BST + sorted input: the in-order of the tree must equal nums. Picking the middle element as the root puts half of the values on each side, which keeps the tree balanced. Then do the same for each half.

Approach:

1. build(lo, hi) builds a tree from nums[lo..hi]; an empty range gives None.
2. mid = (lo + hi) // 2 becomes the root.
3. The left subtree is build(lo, mid − 1), the right is build(mid + 1, hi).
4. Return build(0, n − 1).

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def build(lo, hi):
            if lo > hi:
                return None              # empty range: no node
            mid = (lo + hi) // 2
            node = TreeNode(nums[mid])
            # smaller values on the left, larger on the right
            node.left = build(lo, mid - 1)
            node.right = build(mid + 1, hi)
            return node

        return build(0, len(nums) - 1)

What the code is doing, line by line:

1. def build(lo, hi): works on index ranges instead of slicing, so no list copies are made.
2. if lo > hi: return None: an empty range is a missing child.
3. mid = (lo + hi) // 2, TreeNode(nums[mid]): the middle value; the two halves differ in size by at most 1, which is what keeps the tree balanced.
4. node.left = build(lo, mid - 1): everything smaller; node.right = build(mid + 1, hi): everything larger. That's exactly the BST rule.

Dry run on the example:

nums = [-10, -3, 0, 5, 9] (LeetCode Example 1). Our code returns [0, -10, 5, null, -3, null, 9], one of the accepted answers.

Edge cases to test:

• One or two elements.
• An even length: either middle element works.
• Negative values.

Complexity: O(n) time (each element becomes one node), O(log n) recursion depth.

Problem: A tree is height-balanced if, at every node, the heights of its two subtrees differ by at most 1. Check it.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [0, 5000]. · -10⁴ ≤ Node.val ≤ 10⁴

From brute force to the pattern: Calling a separate height function at every node is O(n²) on skewed trees. Returning the height and the balance status together makes it O(n).

Spot it: Each node needs both subtree heights → post-order. Computing heights separately at every node costs O(n²); instead return the height and use -1 to mean "already unbalanced below".

Approach:

1. A helper height(node) returns the subtree's height, or -1 if it is unbalanced anywhere.
2. Empty tree → height 0.
3. Get both child heights; if either is -1, pass the -1 up immediately.
4. If they differ by more than 1, return -1. Otherwise return 1 + max(left, right).
5. The tree is balanced if height(root) != -1.

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(node):
            # returns the height, or -1 if this subtree is unbalanced somewhere
            if node is None:
                return 0
            left = height(node.left)
            if left == -1:
                return -1
            right = height(node.right)
            if right == -1:
                return -1
            if abs(left - right) > 1:
                return -1
            return 1 + max(left, right)

        return height(root) != -1

What the code is doing, line by line:

1. def height(node): one function, two jobs: the height, and an "unbalanced" flag (-1, which can never be a real height).
2. if node is None: return 0: empty subtrees have height 0.
3. if left == -1: return -1: an unbalanced subtree makes the whole tree unbalanced. Stop early (we don't even visit the right side).
4. if abs(left - right) > 1: return -1: this node itself breaks the rule.
5. return 1 + max(left, right): the normal height.
6. return height(root) != -1: balanced exactly when no -1 reached the top.

Dry run on the example:

root = [1, 2, 2, 3, 3, null, null, 4, 4] (LeetCode Example 2). Returns False. Name the left 2 2a (children 3a, 3b; 3a has two children 4) and the right 2 2b (a leaf).

height(root) is −1, so isBalanced returns False. The root is the only node that breaks the rule.

Edge cases to test:

• An empty tree → True.
• Balanced at the root but not deeper down → False.
• A long chain → False.

Complexity: O(n) time (each node visited once), O(h) recursion space.

Problem: Mirror the binary tree (swap every node's left and right children) and return its root.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [0, 100]. · -100 ≤ Node.val ≤ 100

From brute force to the pattern: This is already O(n): every node must be visited once. Recursion or a BFS with a queue both work.

Spot it: "Do something to every node" on a tree → a recursive traversal. Each node's job is local: swap its two children.

Approach:

1. An empty tree is already inverted: return None.
2. Recursively invert the left subtree and the right subtree.
3. Swap them: the inverted right becomes the new left and vice versa.
4. Return the node.

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        # invert both subtrees first (post-order) ...
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        # ... then swap them
        root.left = right
        root.right = left
        return root

What the code is doing, line by line:

1. if root is None: return None: the base case. Every leaf's missing children end here.
2. left = self.invertTree(root.left) and right = ...: trust the recursion to mirror each subtree completely.
3. root.left = right, root.right = left: swap the two (already mirrored) subtrees. Saving them in variables first means no temporary is needed.
4. return root: the parent call attaches this mirrored subtree on its opposite side.

Dry run on the example:

root = [4, 2, 7, 1, 3, 6, 9] (LeetCode Example 1). Returns [4, 7, 2, 9, 6, 3, 1]. Rows are in the order the calls finish.

Edge cases to test:

• An empty tree.
• A single node.
• A skewed tree.

Complexity: O(n) time (every node once), O(h) space for the recursion stack (h = height).

Problem: Return the minimum absolute difference between the values of any two different nodes in a BST.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [2, 10⁴]. · 0 ≤ Node.val ≤ 10⁵

From brute force to the pattern: Comparing every pair of nodes is O(n²). An in-order walk compares only neighbours in sorted order: O(n).

Spot it: An in-order traversal of a BST visits values in sorted order, and in a sorted list the closest pair is always adjacent. So walk in order and compare each value with the previous one.

Approach:

1. Do an in-order traversal (left, node, right), remembering the previously visited value prev.
2. At each node, if there is a prev, update best with node.val − prev.
3. Set prev = node.val and continue to the right subtree.

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        prev = None             # value of the previous node in sorted order
        best = float("inf")

        def inorder(node):
            nonlocal prev, best
            if node is None:
                return
            inorder(node.left)
            if prev is not None:
                # sorted order: the closest value to node.val is its neighbour
                best = min(best, node.val - prev)
            prev = node.val
            inorder(node.right)

        inorder(root)
        return best

What the code is doing, line by line:

1. prev = None: no value visited yet. best = float("inf"): any real difference beats infinity.
2. inorder(node.left) → handle node → inorder(node.right): that order lists BST values from smallest to largest.
3. if prev is not None: best = min(best, node.val - prev): values are increasing, so the difference is never negative and abs isn't needed.
4. prev = node.val: this node becomes the neighbour of the next one.

Dry run on the example:

root = [4, 2, 6, 1, 3] (LeetCode Example 1). In-order: 1, 2, 3, 4, 6. Returns 1.

Edge cases to test:

• Two nodes.
• The closest pair spans the root (e.g. the root and its in-order successor).
• A skewed tree.

Complexity: O(n) time, O(h) recursion space.

Problem: The diameter is the number of edges on the longest path between any two nodes. The path does not have to pass through the root. Return it.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [1, 10⁴]. · -100 ≤ Node.val ≤ 100

From brute force to the pattern: Computing heights separately for each node as the bend point is O(n²). Returning heights while tracking the best left + right is O(n).

Spot it: The longest path bends at some node: down its left side and down its right side. At every node, left height + right height is a candidate. Post-order recursion gives both heights; a variable outside the recursion keeps the best candidate.

Approach:

1. best = 0 holds the longest path seen.
2. A helper height(node) returns how many nodes are on the longest downward path from node (0 for None).
3. At each node: get the left and right heights. The path that bends here has left + right edges; update best.
4. Return 1 + max(left, right) to the parent.

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        best = 0

        def height(node):
            nonlocal best
            if node is None:
                return 0
            left = height(node.left)
            right = height(node.right)
            # the longest path that bends at this node uses left + right edges
            best = max(best, left + right)
            # the parent can only extend ONE side of this node
            return 1 + max(left, right)

        height(root)
        return best

What the code is doing, line by line:

1. best = 0: the answer, updated as the recursion visits every node.
2. nonlocal best: lets the inner function change best from the outer function (without it, Python would create a new local best).
3. left = height(node.left), right = height(node.right): nodes on the longest path down each side.
4. best = max(best, left + right): going down left nodes on one side and right nodes on the other is a path of exactly left + right edges through this node.
5. return 1 + max(left, right): a parent can continue the path through only one of our sides, so it gets the taller one.

Dry run on the example:

root = [1, 2, 3, 4, 5] (LeetCode Example 1). Returns 3 (path 4 → 2 → 1 → 3 or 5 → 2 → 1 → 3).

Edge cases to test:

• A single node → 0.
• The longest path doesn't go through the root.
• A skewed tree.

Complexity: O(n) time, O(h) recursion space.

Problem: Return True if some node of root, together with all its descendants, is identical to the tree subRoot.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the root tree is in the range [1, 2000]. · The number of nodes in the subRoot tree is in the range [1, 1000]. · -10⁴ ≤ root.val ≤ 10⁴ · -10⁴ ≤ subRoot.val ≤ 10⁴

From brute force to the pattern: Same Tree from every node is O(m · n) in the worst case, which is acceptable here. Serialising both trees and doing a substring search (with careful separators) or tree hashing gets close to O(m + n).

Spot it: Two layers: a traversal that visits every candidate node of root, and Same Tree (LeetCode 100) to compare a candidate with subRoot.

Approach:

1. Write same(a, b) exactly as in Same Tree.
2. If root is None, there is nothing to match: False.
3. If same(root, subRoot), we're done: True.
4. Otherwise the match must be inside the left or right subtree: recurse.

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def same(a, b):
            if a is None and b is None:
                return True
            if a is None or b is None or a.val != b.val:
                return False
            return same(a.left, b.left) and same(a.right, b.right)

        if root is None:
            return False
        if same(root, subRoot):
            return True
        # not at this node: try every node below it
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

What the code is doing, line by line:

1. def same(a, b): LeetCode 100 in a few lines: equal shape and equal values.
2. if root is None: return False: ran out of candidates on this path.
3. if same(root, subRoot): return True: the subtree starting here matches exactly.
4. return ... or ...: look for a match anywhere in the left subtree, otherwise anywhere in the right subtree. or stops at the first success.

Dry run on the example:

root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2] (LeetCode Example 1). Returns True.

The left subtree of 3 matched, so or never needs to try the 5.

Edge cases to test:

• subRoot equal to the whole tree.
• Equal values but an extra node below, e.g. a leaf vs a node with a child.
• Repeated values (several candidate starting points).

Complexity: O(m · n) time in the worst case (Same Tree from each of the m nodes), O(h) recursion space.

Problem: Given the in-order and post-order traversals of a binary tree with unique values, rebuild the tree.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ inorder.length ≤ 3000 · postorder.length == inorder.length · -3000 ≤ inorder[i], postorder[i] ≤ 3000 · inorder and postorder consist of unique values. · Each value of postorder also appears in inorder. · inorder is guaranteed to be the inorder traversal of the tree. · postorder is guaranteed to be the postorder traversal of the tree.

From brute force to the pattern: Searching the inorder list for each root costs O(n) per node, O(n²) total. A value → index map and a pointer moving backwards through the postorder make it O(n).

Spot it: Mirror of LeetCode 105. Post-order is left, right, root, so the root is at the end. Its position in the in-order list splits the values into the left subtree and the right subtree.

Key insight: Reading post-order backwards gives root, right, left. So take values from the end of postorder and build the right subtree before the left one. A dictionary value → in-order index makes each split O(1).

Approach:

1. Map every value to its index in inorder.
2. Keep a pointer post_i at the last element of postorder.
3. build(lo, hi) builds the subtree whose values are inorder[lo..hi]: take postorder[post_i] as the root and move post_i left.
4. Find the root's in-order index mid. Build the right subtree from mid + 1..hi first, then the left from lo..mid − 1.
5. An empty range returns None.

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # value -> its position in inorder, to split left/right in O(1)
        index_of = {}
        for i in range(len(inorder)):
            index_of[inorder[i]] = i
        # we consume postorder from the END: root, then right subtree, then left
        post_i = len(postorder) - 1

        def build(lo, hi):
            nonlocal post_i
            if lo > hi:
                return None
            root_val = postorder[post_i]
            post_i = post_i - 1
            node = TreeNode(root_val)
            mid = index_of[root_val]
            # right first, because postorder read backwards is root, right, left
            node.right = build(mid + 1, hi)
            node.left = build(lo, mid - 1)
            return node

        return build(0, len(inorder) - 1)

What the code is doing, line by line:

1. index_of: where each value sits in inorder. Values are unique, so this is well defined.
2. post_i = len(postorder) - 1: the next root to use, starting from the end.
3. if lo > hi: return None: no values for this subtree.
4. root_val = postorder[post_i], post_i = post_i - 1: take the next root.
5. mid = index_of[root_val]: in-order values left of mid form the left subtree and values right of it form the right subtree.
6. node.right = build(mid + 1, hi) before node.left: the element just before a root in post-order belongs to its right subtree. Building left first would hand the left subtree the wrong roots.

Dry run on the example:

inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3] (LeetCode Example 1). Returns [3, 9, 20, null, null, 15, 7].

Edge cases to test:

• A single node.
• Skewed trees.
• Forgetting to build the right subtree first gives the wrong tree.

Complexity: O(n) time, O(n) space for the map and recursion.

Problem: Flatten the tree in place into a "linked list" that uses the right pointers, in pre-order (node, left, right). Every left pointer must become None.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [0, 2000]. · -100 ≤ Node.val ≤ 100

From brute force to the pattern: Collecting the pre-order into a list and re-linking uses O(n) space. Splicing each left subtree in place uses O(1) extra space and still touches every edge a constant number of times: O(n).

Spot it: Pre-order puts the whole left subtree between a node and its right subtree. So for each node with a left child: hang the right subtree off the rightmost node of the left subtree, then move the left subtree over to the right. O(1) extra space, no recursion.

Approach:

1. Walk cur down the right pointers from the root.
2. If cur has a left subtree: find that subtree's rightmost node tail (the last node of the left subtree in pre-order).
3. Attach cur.right to tail.right, then make cur.right = cur.left and cur.left = None.
4. Move cur = cur.right and repeat until cur is None.

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        cur = root
        while cur is not None:
            if cur.left is not None:
                # the last node of the left subtree in pre-order is its rightmost node
                tail = cur.left
                while tail.right is not None:
                    tail = tail.right
                # the right subtree comes after the whole left subtree
                tail.right = cur.right
                # move the left subtree into the right slot
                cur.right = cur.left
                cur.left = None
            cur = cur.right

What the code is doing, line by line:

1. cur = root: we work down the chain that is being built.
2. if cur.left is not None: only nodes with a left subtree need re-wiring.
3. tail = cur.left, then while tail.right is not None: tail = tail.right: the rightmost node of the left subtree is visited last in pre-order, so the right subtree must follow it.
4. tail.right = cur.right: hang the old right subtree after that last node.
5. cur.right = cur.left, cur.left = None: the left subtree now comes right after cur, and no left pointers remain.
6. cur = cur.right: continue. Nodes deeper down still get the same treatment when cur reaches them.

Dry run on the example:

root = [1, 2, 5, 3, 4, null, 6] (LeetCode Example 1). Result [1, null, 2, null, 3, null, 4, null, 5, null, 6].

Edge cases to test:

• An empty tree.
• Only left children.
• Already flat (only right children).

Complexity: O(n) time (each tail walk covers edges no other walk covers), O(1) extra space.

Problem: In a BST, return the lowest node that has both p and q as descendants (a node counts as a descendant of itself).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [2, 10⁵]. · -10⁹ ≤ Node.val ≤ 10⁹ · All Node.val are unique. · p != q · p and q will exist in the BST.

From brute force to the pattern: The general LCA algorithm explores the whole tree (O(n)). In a BST the ordering tells you which way to go, so you follow one path: O(h).

Spot it: BST order tells you which side each value is on. While both values are smaller than the current node, the LCA is on the left; while both are larger, on the right. The first node where they split (or that equals one of them) is the LCA.

Approach:

1. Start at the root.
2. If both p.val and q.val are smaller than node.val, move left.
3. If both are larger, move right.
4. Otherwise they are on different sides (or one of them is this node): return it.

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        node = root
        while node is not None:
            if p.val < node.val and q.val < node.val:
                node = node.left      # both are in the left subtree
            elif p.val > node.val and q.val > node.val:
                node = node.right     # both are in the right subtree
            else:
                # they split here (or one of them IS this node)
                return node
        return None

What the code is doing, line by line:

1. node = root: an iterative walk. No recursion is needed because we only ever go down one path.
2. if p.val < node.val and q.val < node.val: in a BST everything smaller lives on the left, so the LCA must be there too.
3. elif p.val > node.val and q.val > node.val: both on the right.
4. else: return node: one value is ≤ and the other ≥ this node, so this is the deepest node above both.
5. return None: unreachable when p and q are in the tree, as the problem guarantees.

Dry run on the example:

root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4 (LeetCode Example 2). Returns 2.

Edge cases to test:

• p is an ancestor of q.
• p and q are the root's two children.
• A skewed BST.

Complexity: O(h) time (one root-to-node path), O(1) space.

Problem: grid is an n × n matrix of 0s and 1s (n a power of 2). Build its quad tree: a uniform square becomes a leaf with that value; otherwise the node has four children for the top-left, top-right, bottom-left and bottom-right quarters.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: n == grid.length == grid[i].length · n == 2x where 0 ≤ x ≤ 6

From brute force to the pattern: Checking uniformity by scanning each square is O(n² log n) overall. A 2-D prefix sum checks a square in O(1), giving O(n²).

Spot it: A tree defined by recursive splitting → recursion that builds one node per square. Each node has four children instead of two.

Approach:

1. build(row, col, size) handles the square whose top-left corner is (row, col).
2. Check whether every cell in it equals the first cell.
3. If so, return a leaf: Node(val = that value, isLeaf = True).
4. Otherwise split into four squares of size // 2 and return an internal node with those four children.

class Solution:
    def construct(self, grid: List[List[int]]) -> "Node":
        def build(row, col, size):
            # is every cell in this square the same as its first cell?
            first = grid[row][col]
            uniform = True
            for r in range(row, row + size):
                for c in range(col, col + size):
                    if grid[r][c] != first:
                        uniform = False
                        break
                if not uniform:
                    break
            if uniform:
                return Node(first == 1, True)
            half = size // 2
            # not uniform: split into four quarters
            return Node(True, False,
                        build(row, col, half),                 # top-left
                        build(row, col + half, half),          # top-right
                        build(row + half, col, half),          # bottom-left
                        build(row + half, col + half, half))   # bottom-right

        return build(0, 0, len(grid))

What the code is doing, line by line:

1. def build(row, col, size): a square is described by its corner and side length, so no sub-grids are copied.
2. The two nested loops compare every cell with first and break out at the first mismatch.
3. if uniform: return Node(first == 1, True): a leaf. LeetCode stores the value as a boolean, so first == 1 turns 1/0 into True/False.
4. half = size // 2: the side of each quarter.
5. Node(True, False, ...): an internal node (isLeaf = False; its val can be anything) with four recursively built children, in the order top-left, top-right, bottom-left, bottom-right.

Dry run on the example:

grid = [[0, 1], [1, 0]] (LeetCode Example 1). Returns [[0, 1], [1, 0], [1, 1], [1, 1], [1, 0]] (each pair is [isLeaf, val]).

Edge cases to test:

• A 1 × 1 grid.
• A uniform grid → a single leaf.
• A checkerboard → maximum splitting.

Complexity: O(n² log n) time (each level of splitting re-scans all cells once), O(log n) recursion depth.

Problem: Return every structurally unique BST that stores exactly the values 1..n.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 8

From brute force to the pattern: Inserting every permutation of 1..n gives n! trees with many duplicates. Building by root choice produces each tree once.

Spot it: In a BST, choosing the root r splits the values: lo..r − 1 go left, r + 1..hi go right. The trees for a range are built recursively from the trees of its two sub-ranges: a tree-building recursion (divide and conquer).

Why not another pattern? Backtracking over insert orders produces the same tree many times (different insert orders give equal trees).

Approach:

1. build(lo, hi) returns all BSTs using values lo..hi; an empty range gives [None] (one empty tree).
2. For each root r in lo..hi: get lefts = build(lo, r − 1), rights = build(r + 1, hi).
3. For every pair (left, right), make a new root r with those children.
4. Memoise on (lo, hi): subtrees can be shared between results since they're never modified.

from functools import lru_cache

class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        @lru_cache(maxsize=None)
        def build(lo, hi):
            if lo > hi:
                return [None]  # one way to build an empty tree
            trees = []
            for root in range(lo, hi + 1):  # try every value as the root
                for left in build(lo, root - 1):  # all BSTs of the smaller values
                    for right in build(root + 1, hi):  # all BSTs of the larger values
                        trees.append(TreeNode(root, left, right))
            return trees

        return build(1, n)

What the code is doing, line by line:

1. [None] (not []) for an empty range is what makes a leaf possible: one way to have no left child.
2. Every combination of a left subtree and a right subtree under root r is a distinct BST.
3. Sharing subtrees between answers is safe because nothing is modified after it's built.
4. The number of trees is the Catalan number Cₙ (42 for n = 5).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → one single-node tree.
• The empty range must return [None], not [].
• Shared subtrees between results (fine because they're never mutated).

Complexity: O(Cₙ · n) time and space (Cₙ ≈ 4ⁿ / n^1.5): proportional to the output.

Problem: Return how many structurally unique BSTs store exactly the values 1..n.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 19

From brute force to the pattern: Building every tree costs as much as the answer itself (exponential). The DP is O(n²).

Spot it: Only the count is needed, and it depends only on the number of values, not which ones. With root r, the left side has r − 1 values and the right side n − r: multiply their counts and add over all roots.

Why not another pattern? Generating every tree (LeetCode 95) is exponential; counting needs only a small DP table.

Approach:

1. count[0] = count[1] = 1.
2. For each size m from 2 to n: count[m] = Σ count[r − 1] · count[m − r] for r = 1..m.
3. Return count[n].

class Solution:
    def numTrees(self, n: int) -> int:
        count = [0] * (n + 1)
        count[0] = 1  # the empty tree
        count[1] = 1
        for m in range(2, n + 1):  # number of values in the tree
            for root in range(1, m + 1):
                count[m] += count[root - 1] * count[m - root]  # left shapes x right shapes
        return count[n]

What the code is doing, line by line:

1. The shape count for a set of values depends only on how many values there are.
2. Root root leaves root − 1 values on the left and m − root on the right; every pair of shapes is a new tree.
3. These are the Catalan numbers: 1, 1, 2, 5, 14, 42, …

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → 1.
• The empty subtree counts as one shape.
• n = 19 fits in a 32-bit integer.

Complexity: O(n²) time, O(n) space.

Problem: Exactly two nodes of a BST had their values swapped. Fix the tree without changing its structure.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [2, 1000]. · -2³¹ ≤ Node.val ≤ 2³¹ - 1

From brute force to the pattern: Collect values, sort them, write them back in order: O(n log n) and O(n) space. Tracking drops during one walk is O(n).

Spot it: A BST's in-order traversal is sorted. Swapping two values creates one or two places where prev > current. The first wrong node is the prev of the first drop; the second is the current of the last drop.

Why not another pattern? Copying values out, sorting and writing them back works but uses O(n) space and ignores that only two are wrong.

Approach:

1. Walk the tree in order (iteratively, with a stack), remembering the previous node.
2. At each drop prev.val > node.val: if it's the first, set first = prev; always set second = node.
3. Swap first.val and second.val.

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        stack = []
        node = root
        prev = first = second = None
        while stack or node:
            while node:
                stack.append(node)  # go as far left as possible
                node = node.left
            node = stack.pop()  # next node in sorted order
            if prev and prev.val > node.val:  # order is broken here
                if first is None:
                    first = prev  # the larger value that moved forward
                second = node  # the smaller value that moved back
            prev = node
            node = node.right
        first.val, second.val = second.val, first.val  # put them back

What the code is doing, line by line:

1. The iterative in-order walk visits nodes in what should be increasing order.
2. Adjacent swapped nodes produce one drop (first = prev, second = node at that drop).
3. Non-adjacent swaps produce two drops: first comes from the first, second from the second.
4. Only the values are swapped; the structure stays as it was.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• The swapped nodes are adjacent in in-order (one drop).
• The root is one of them.
• Two-node tree.

Complexity: O(n) time, O(h) space for the stack (Morris traversal brings it to O(1)).

Problem: Return the node values level by level from the bottom level up (left to right within each level).

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [0, 2000]. · -1000 ≤ Node.val ≤ 1000

From brute force to the pattern: Prepending each level to the answer shifts the whole list each time; one reverse at the end is O(levels).

Spot it: "Level by level" is BFS with a queue, processing one level per loop. Bottom-up just reverses the finished list.

Why not another pattern? Inserting each level at the front of a list is O(levels²); append and reverse once instead.

Approach:

1. Queue starts with the root.
2. While the queue isn't empty: pop exactly len(queue) nodes (one level), collect their values, push their children.
3. Reverse the levels at the end.

from collections import deque

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        levels = []
        queue = deque([root])
        while queue:
            level = []
            for _ in range(len(queue)):  # exactly the nodes of this level
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            levels.append(level)
        return levels[::-1]  # bottom level first

What the code is doing, line by line:

1. len(queue) at the start of each round is the size of the current level, so children wait for the next round.
2. Levels are produced top-down; reversing once gives bottom-up.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Empty tree → [].
• A tree that is a single path.
• Only the root.

Complexity: O(n) time, O(width) space for the queue.

Problem: In a perfect binary tree, set each node's next to the node on its right in the same level (or None).

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [0, 2¹² - 1]. · -1000 ≤ Node.val ≤ 1000

From brute force to the pattern: BFS with a queue is O(n) space; walking each linked level is O(1).

Spot it: A BFS queue does it in O(n) space. In a perfect tree there's a constant-space trick: once a level is linked, walk it via next and link its children: left.next = right, and right.next = node.next.left.

Why not another pattern? BFS with a queue is correct but uses O(n) extra space; the follow-up asks for constant space.

Approach:

1. leftmost = the first node of the current level, starting at the root.
2. Walk the level with node = node.next: set node.left.next = node.right, and if node.next, node.right.next = node.next.left.
3. Move down: leftmost = leftmost.left, until the leaves.

class Solution:
    def connect(self, root: "Optional[Node]") -> "Optional[Node]":
        leftmost = root
        while leftmost and leftmost.left:  # there is a level below to link
            node = leftmost
            while node:  # walk this level using the next pointers already set
                node.left.next = node.right  # siblings under the same parent
                if node.next:
                    node.right.next = node.next.left  # across to the neighbouring parent
                node = node.next
            leftmost = leftmost.left  # go down one level
        return root

What the code is doing, line by line:

1. The root level is trivially linked (one node, next = None).
2. Each linked level lets us reach every pair of neighbouring children without a queue.
3. Children of the same parent link directly; children of neighbouring parents link through node.next.
4. The tree is perfect, so left exists exactly when right does.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Empty tree.
• Only the root.
• The rightmost node of each level keeps next = None.

Complexity: O(n) time, O(1) extra space.

Problem: Count the nodes of a complete binary tree in less than O(n) time.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [0, 5 * 10⁴]. · 0 ≤ Node.val ≤ 5 * 10⁴ · The tree is guaranteed to be complete.

From brute force to the pattern: Counting every node is O(n); using perfect subtrees skips most of them.

Spot it: In a complete tree, at least one of the two subtrees is perfect, and a perfect tree's size is 2^h − 1 without visiting it. Compare the depth down the far-left edge with the depth down the far-right edge: equal means perfect.

Why not another pattern? Any traversal counts in O(n); the complete shape allows O(log² n).

Approach:

1. Measure the left-edge height and right-edge height of the current node.
2. If equal, return 2^h − 1.
3. Otherwise return 1 + count(left) + count(right); one of the two calls stops right away.

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        left_h = 0
        node = root
        while node:
            left_h = left_h + 1  # depth along the leftmost path
            node = node.left
        right_h = 0
        node = root
        while node:
            right_h = right_h + 1  # depth along the rightmost path
            node = node.right
        if left_h == right_h:
            return (1 << left_h) - 1  # perfect tree: 2^h - 1 nodes
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

What the code is doing, line by line:

1. Equal edge heights mean every level is full, so the size follows from the height.
2. When they differ, recursing into both children is fine: one child is always perfect and returns immediately.
3. There are O(log n) levels of recursion, each spending O(log n) on the edge walks.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Empty tree → 0.
• A perfect tree (answered at the root).
• The last level has a single node.

Complexity: O(log² n) time, O(log n) recursion space.

Problem: Repeatedly collect and remove all leaves until the tree is empty; return the groups in removal order.

Solve it on LeetCode ↗ (Premium)

Constraints: The number of nodes in the tree is in the range [1, 100] · -100 ≤ Node.val ≤ 100

From brute force to the pattern: Deleting leaves round by round is O(n · h); grouping by height is one O(n) walk.

Spot it: A node is removed in round h, where h is its height (leaves have height 0). Height needs the children first: a post-order DFS that returns 1 + max(left, right) and appends the node to rounds[h].

Why not another pattern? Actually deleting leaves round by round re-walks the tree each round: O(n · h).

Approach:

1. height(node): None → −1; otherwise h = 1 + max(height(left), height(right)).
2. Append node.val to rounds[h] (create the list when h is new).
3. Return rounds.

class Solution:
    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
        rounds = []

        def height(node):
            if node is None:
                return -1
            h = 1 + max(height(node.left), height(node.right))  # children first (post-order)
            if h == len(rounds):
                rounds.append([])  # first node removed in round h
            rounds[h].append(node.val)
            return h

        height(root)
        return rounds

What the code is doing, line by line:

1. A node becomes a leaf once all nodes below it are gone, which takes height rounds.
2. Post-order visits nodes left to right within each height, matching the expected order.
3. Heights are reached in increasing order the first time, so h == len(rounds) is enough to grow the list.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A single node → [[val]].
• A path-shaped tree (one node per round).
• Leaves at different depths.

Complexity: O(n) time, O(h) recursion space.

Problem: Delete the node with value key from a BST (if present) and return the root; the result must still be a BST.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [0, 10⁴]. · -10⁵ ≤ Node.val ≤ 10⁵ · Each node has a unique value. · root is a valid binary search tree. · -10⁵ ≤ key ≤ 10⁵

From brute force to the pattern: Collecting all values except key and rebuilding is O(n); deleting along one path is O(h).

Spot it: Find the node by BST search. Zero or one child: replace it with that child. Two children: copy in its in-order successor (smallest value in the right subtree) and delete that successor, which has at most one child.

Why not another pattern? Rebuilding the BST from its sorted values is O(n); deleting in place is O(h).

Approach:

1. If key < root.val, delete from the left subtree; if greater, from the right.
2. Found it: no left child → return the right; no right child → return the left.
3. Both: find the minimum of the right subtree, copy its value here, delete that value from the right subtree.

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if root is None:
            return None  # key not found
        if key < root.val:
            root.left = self.deleteNode(root.left, key)  # it's in the left subtree
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            if root.left is None:
                return root.right  # zero or one child: lift the child up
            if root.right is None:
                return root.left
            succ = root.right
            while succ.left:
                succ = succ.left  # smallest value in the right subtree
            root.val = succ.val  # the successor takes this node's place
            root.right = self.deleteNode(root.right, succ.val)
        return root

What the code is doing, line by line:

1. Each recursive call returns the new root of its subtree, so parents re-attach whatever comes back.
2. A node with at most one child is replaced by that child (or None).
3. The in-order successor is larger than everything on the left and smaller than the rest of the right, so it can take the node's place.
4. The successor has no left child, so deleting it is the simple case.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• key not in the tree.
• Deleting the root.
• Empty tree.

Complexity: O(h) time and recursion space (h = height).

Problem: The width of a level is the distance between its leftmost and rightmost nodes, counting the gaps. Return the maximum width.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [1, 3000]. · -100 ≤ Node.val ≤ 100

From brute force to the pattern: Materialising null placeholders in a complete tree can need 2^depth entries; heap indices need one number per node.

Spot it: Give each node its position in a complete tree: root 0, children 2i and 2i + 1. Then a level's width is just last − first + 1. Visit level by level with BFS.

Why not another pattern? Filling the gaps with placeholder nodes explodes exponentially on deep, sparse trees.

Approach:

1. Queue of (node, index), starting with (root, 0).
2. For each level: width = index of last − index of first + 1.
3. Push children with indices 2i and 2i + 1, rebased to the level's first index to keep numbers small.

from collections import deque

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        best = 0
        queue = deque([(root, 0)])  # (node, position in a complete tree)
        while queue:
            first = queue[0][1]
            last = queue[-1][1]
            best = max(best, last - first + 1)  # gaps between them count
            for _ in range(len(queue)):
                node, i = queue.popleft()
                i = i - first  # rebase so indices stay small
                if node.left:
                    queue.append((node.left, 2 * i))
                if node.right:
                    queue.append((node.right, 2 * i + 1))
        return best

What the code is doing, line by line:

1. Heap numbering places every possible position of a level on a number line, so the gap count is a subtraction.
2. The queue holds exactly one level at the start of each round, ordered left to right.
3. Subtracting first before doubling keeps indices bounded by the level width instead of growing as 2^depth.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A single node → 1.
• A deep zig-zag tree (indices would overflow without rebasing).
• The widest level isn't the last one.

Complexity: O(n) time, O(width) space.

Problem: Insert val (not already present) into a BST and return the root. Any valid BST is accepted.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree will be in the range [0, 10⁴]. · -10⁸ ≤ Node.val ≤ 10⁸ · All the values Node.val are unique. · -10⁸ ≤ val ≤ 10⁸ · It's guaranteed that val does not exist in the original BST.

From brute force to the pattern: Collecting values and rebuilding is O(n); walking one path is O(h).

Spot it: BST search tells you exactly where val would be: follow left/right comparisons until a missing child, and put it there.

Why not another pattern? Rebuilding or rebalancing isn't required; inserting at a leaf keeps the BST property in O(h).

Approach:

1. Empty tree: return a new node.
2. Walk from the root: go left if val < node.val, else right.
3. When that child is None, attach the new node there.

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return TreeNode(val)
        node = root
        while True:
            if val < node.val:
                if node.left is None:
                    node.left = TreeNode(val)  # found the empty spot
                    return root
                node = node.left  # smaller: go left
            else:
                if node.right is None:
                    node.right = TreeNode(val)
                    return root
                node = node.right  # larger: go right

What the code is doing, line by line:

1. The search path is the only place val can go without breaking the ordering.
2. The new node is always a leaf, so no other node moves.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Empty tree.
• val smaller than every value (goes far left).
• A skewed tree.

Complexity: O(h) time, O(1) extra space.

Problem: Each node has some coins (total = number of nodes). One move shifts one coin across an edge. Return the minimum moves to give every node exactly one coin.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is n. · 1 ≤ n ≤ 100 · 0 ≤ Node.val ≤ n · The sum of all Node.val is n.

From brute force to the pattern: Simulating coin moves is messy and slow; counting per-edge flow is one O(n) post-order walk.

Spot it: Look at an edge between a node and its parent: the subtree below has coins − nodes extra (or missing) coins, and exactly that many must cross this edge. That excess needs the children first: post-order DFS.

Why not another pattern? Simulating moves greedily is complicated and slow; counting flow per edge is exact.

Approach:

1. excess(node) = node.val − 1 + excess(left) + excess(right).
2. Add |excess(left)| + |excess(right)| to the moves: that many coins cross each child edge.
3. Return the moves after visiting the root.

class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        self.moves = 0

        def excess(node):  # coins this subtree must send up (negative = must receive)
            if node is None:
                return 0
            left = excess(node.left)
            right = excess(node.right)
            self.moves += abs(left) + abs(right)  # coins crossing the two child edges
            return node.val - 1 + left + right

        excess(root)
        return self.moves

What the code is doing, line by line:

1. Each subtree needs exactly one coin per node; its surplus or deficit must pass through the edge to its parent.
2. Every crossing coin costs one move, and no coin needs to cross an edge twice, so summing |excess| over edges is optimal.
3. The root's own excess is 0 because the total coins equal the number of nodes.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Every node already has one coin → 0.
• All coins at one leaf.
• A deficit in one branch and a surplus in another.

Complexity: O(n) time, O(h) recursion space.

Problem: Delete every node whose value is in to_delete and return the roots of the remaining trees (any order).

Solve it on LeetCode ↗

Constraints: The number of nodes in the given tree is at most 1000. · Each node has a distinct value between 1 and 1000. · to_delete.length ≤ 1000 · to_delete contains distinct values between 1 and 1000.

From brute force to the pattern: Deleting nodes one by one and searching for orphans each time is O(n · k); one DFS is O(n).

Spot it: A node starts a new tree exactly when it is kept and its parent is deleted (or it's the root). Pass "is my parent gone?" down the DFS and return None for deleted nodes so parents cut them off.

Why not another pattern? Deleting nodes one at a time and searching for the new roots afterwards re-walks the tree for each deletion.

Approach:

1. Put to_delete in a set.
2. walk(node, parent_deleted): deleted = node.val in remove. If kept and parent_deleted, it's a new root.
3. Recurse into children with parent_deleted = deleted; assign the results back (they may be None).
4. Return None if this node is deleted, else the node.

class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        remove = set(to_delete)
        roots = []

        def walk(node, parent_deleted):
            if node is None:
                return None
            deleted = node.val in remove
            if parent_deleted and not deleted:
                roots.append(node)  # its parent is gone: it heads a new tree
            node.left = walk(node.left, deleted)  # children cut off if they are deleted
            node.right = walk(node.right, deleted)
            return None if deleted else node

        walk(root, True)  # the root behaves as if its parent were deleted
        return roots

What the code is doing, line by line:

1. Calling walk(root, True) makes the root a tree root if it's kept.
2. Assigning node.left = walk(...) detaches a deleted child automatically, since the call returns None.
3. Children of a deleted node are checked with parent_deleted = True, so kept ones become roots.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Deleting the root.
• Deleting nothing → [root].
• Deleting a leaf (no new roots).

Complexity: O(n) time, O(h + |to_delete|) space.

Problem: Levels are numbered from 1 at the root. Return the smallest level whose node values have the largest sum.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [1, 10⁴]. · -10⁵ ≤ Node.val ≤ 10⁵

From brute force to the pattern: Computing each level's sum with a separate depth-limited DFS is O(n · h); one BFS is O(n).

Spot it: Per-level sums → BFS one level at a time. Update the answer only on a strictly larger sum so the smallest level wins ties.

Why not another pattern? A DFS with a depth-indexed sum array also works; BFS just makes the per-level loop explicit.

Approach:

1. Queue with the root; level = 1.
2. Sum the values of exactly len(queue) nodes, pushing their children.
3. If the sum beats the best, record the level.

from collections import deque

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        best_sum = float("-inf")
        best_level = 1
        level = 0
        queue = deque([root])
        while queue:
            level = level + 1
            total = 0
            for _ in range(len(queue)):  # one full level
                node = queue.popleft()
                total += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if total > best_sum:  # strictly larger: earlier levels win ties
                best_sum = total
                best_level = level
        return best_level

What the code is doing, line by line:

1. Each outer iteration handles exactly one level.
2. Values can be negative, so the best sum starts at −∞.
3. Using > (not >=) keeps the smallest level on ties.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Negative values everywhere.
• Ties between levels (smallest wins).
• A single node.

Complexity: O(n) time, O(width) space.

Problem: Return the shortest path from node startValue to node destValue as letters L, R (to a child) and U (to the parent).

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is n. · 2 ≤ n ≤ 10⁵ · 1 ≤ Node.val ≤ n · All the values in the tree are unique. · 1 ≤ startValue, destValue ≤ n · startValue != destValue

From brute force to the pattern: BFS over an undirected copy of the tree plus parent tracking works but builds a whole graph; two root paths are enough.

Spot it: The path goes up from the start to their lowest common ancestor, then down to the destination. Record both paths from the root as L/R strings; their common prefix is the way to the LCA.

Why not another pattern? Converting the tree to an undirected graph and running BFS works but needs O(n) extra structure and a path rebuild.

Approach:

1. Find the root-to-start path and root-to-dest path as strings of L/R (iterative DFS).
2. Remove their common prefix.
3. Answer: 'U' × len(rest of start path) + rest of dest path.

class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        def path_to(target):
            stack = [(root, "")]
            while stack:
                node, path = stack.pop()
                if node.val == target:
                    return path  # moves from the root down to target
                if node.left:
                    stack.append((node.left, path + "L"))
                if node.right:
                    stack.append((node.right, path + "R"))

        to_start = path_to(startValue)
        to_dest = path_to(destValue)
        i = 0
        while i < len(to_start) and i < len(to_dest) and to_start[i] == to_dest[i]:
            i = i + 1  # shared part: the way down to the common ancestor
        return "U" * (len(to_start) - i) + to_dest[i:]

What the code is doing, line by line:

1. Both root paths share the moves down to the lowest common ancestor; the first difference is where they split.
2. From the start, every remaining step of its path must be undone with a U.
3. Then follow the rest of the destination path down.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• The start is an ancestor of the destination (no U).
• The destination is an ancestor of the start (only U).
• Both in different subtrees of the root.

Complexity: O(n) time; the string building is O(n · h) in the worst case (a list-based path brings it to O(n)).

Problem: Each row [parent, child, isLeft] describes one edge of a binary tree with unique values. Build the tree and return its root.

Solve it on LeetCode ↗

Constraints: 1 ≤ descriptions.length ≤ 10⁴ · descriptions[i].length == 3 · 1 ≤ parenti, childi ≤ 10⁵ · 0 ≤ isLefti ≤ 1 · The binary tree described by descriptions is valid.

From brute force to the pattern: Building the tree by searching for each parent node is O(n²); a dictionary makes each edge O(1).

Spot it: A hash map value → node lets you link edges in any order. The root is the one parent that never appears as a child (a set).

Why not another pattern? Searching the partly built tree for each parent is O(n) per edge.

Approach:

1. For each row, get or create the parent and child nodes in nodes.
2. Attach the child to the left or right; add the child value to children.
3. Return the node whose value isn't in children.

class Solution:
    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
        nodes = {}  # value -> node, created the first time it's seen
        children = set()
        for parent, child, is_left in descriptions:
            if parent not in nodes:
                nodes[parent] = TreeNode(parent)
            if child not in nodes:
                nodes[child] = TreeNode(child)
            if is_left:
                nodes[parent].left = nodes[child]
            else:
                nodes[parent].right = nodes[child]
            children.add(child)
        for parent, _, _ in descriptions:
            if parent not in children:
                return nodes[parent]  # never a child: the root

What the code is doing, line by line:

1. Nodes can be referenced as children before or after they appear as parents; the map makes that irrelevant.
2. Every node except the root has exactly one parent, so the root is the only value missing from children.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Edges given in any order.
• A path-shaped tree.
• One edge.

Complexity: O(n) time and space.

Problem: For every node of a tree, return the sum of its distances to all other nodes.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 3 * 10⁴ · edges.length == n - 1 · edges[i].length == 2 · 0 ≤ ai, bi < n · ai != bi · The given input represents a valid tree.

From brute force to the pattern: BFS from every node: O(n²). Two passes with the rerooting formula: O(n).

Spot it: Running BFS from every node is O(n²). Rerooting: compute the answer for root 0 with one DFS (using subtree sizes), then derive each child's answer from its parent's: moving from p to child c brings size[c] nodes one step closer and the other n − size[c] one step further.

Why not another pattern? BFS from each node is O(n²) = 9·10⁸ for n = 3·10⁴.

Approach:

1. Pass 1 (post-order from root 0): size[u] and down[u] = sum of distances from u to nodes in its subtree. down[u] = Σ (down[c] + size[c]).
2. answer[0] = down[0].
3. Pass 2 (pre-order): answer[c] = answer[p] − size[c] + (n − size[c]).

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        adj = [[] for _ in range(n)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        parent = [-1] * n
        order = [0]  # DFS order from root 0 (parents before children)
        for u in order:
            for v in adj[u]:
                if v != parent[u]:
                    parent[v] = u
                    order.append(v)
        size = [1] * n
        down = [0] * n  # sum of distances from u into its own subtree
        for u in reversed(order):  # children before parents
            p = parent[u]
            if p >= 0:
                size[p] += size[u]
                down[p] += down[u] + size[u]  # every node under u is one step further from p
        answer = [0] * n
        answer[0] = down[0]
        for u in order[1:]:  # parents before children
            answer[u] = answer[parent[u]] - size[u] + (n - size[u])  # reroot from parent to u
        return answer

What the code is doing, line by line:

1. order is built iteratively (no recursion limit problems) and lists every parent before its children.
2. Walking order backwards accumulates subtree sizes and the subtree distance sums.
3. At the root, the subtree is the whole tree, so down[0] is its full answer.
4. Moving the root from p to u: the size[u] nodes in u's subtree get 1 closer, the other n − size[u] get 1 further.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → [0].
• A path (long chain).
• A star.

Complexity: O(n) time and space.

Problem: Root at (row 0, col 0); a left child is at (row + 1, col − 1), a right child at (row + 1, col + 1). Return the columns left to right, each top to bottom, ties in the same cell sorted by value.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [1, 1000]. · 0 ≤ Node.val ≤ 1000

From brute force to the pattern: Repeated scans per column are O(n · columns); one sort of the triples is O(n log n).

Spot it: The order rule is a sort key: (col, row, val). Collect that triple for every node with any traversal, sort once, then split into columns.

Why not another pattern? A BFS keeps rows in order but still needs sorting for equal (row, col) cells, so the sort is unavoidable.

Approach:

1. DFS from the root carrying (row, col); record (col, row, val) for each node.
2. Sort the triples.
3. Walk them; start a new group whenever the column changes.

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        cells = []
        stack = [(root, 0, 0)]
        while stack:
            node, row, col = stack.pop()
            if node:
                cells.append((col, row, node.val))  # the sort key: column, then row, then value
                stack.append((node.left, row + 1, col - 1))
                stack.append((node.right, row + 1, col + 1))
        cells.sort()
        result = []
        last_col = None
        for col, row, val in cells:
            if col != last_col:
                result.append([])  # a new column starts
                last_col = col
            result[-1].append(val)
        return result

What the code is doing, line by line:

1. Any traversal order works because the sort fixes the final order.
2. Sorting tuples compares column first, then row, then value — exactly the problem's rules.
3. Consecutive triples with the same column form one output list.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Two nodes in the same row and column (sort by value).
• A single node.
• A tree leaning entirely left.

Complexity: O(n log n) time, O(n) space.

Problem: Given a parent array (root 0), answer many queries: the k-th ancestor of node, or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ n ≤ 5 * 10⁴ · parent.length == n · parent[0] == -1 · 0 ≤ parent[i] < n for all 0 < i < n · 0 ≤ node < n · There will be at most 5 * 10⁴ queries.

From brute force to the pattern: Following parents one step at a time is O(k) per query. Binary lifting answers in O(log k).

Spot it: Walking up k parents per query is O(k). Binary lifting precomputes jumps of size 1, 2, 4, …: up[j][v] = up[j − 1][up[j − 1][v]]. Any k is a sum of powers of two, so a query takes O(log k) jumps.

Why not another pattern? Storing every ancestor of every node is O(n²) memory; walking up is O(n) per query.

Approach:

1. up[0] = parent.
2. For j ≥ 1: up[j][v] = up[j − 1][up[j − 1][v]] (or −1 if the half-way node doesn't exist).
3. Query: for each set bit j of k, node = up[j][node]; stop with −1 if it falls off the root.

class TreeAncestor:
    def __init__(self, n: int, parent: List[int]):
        self.up = [parent[:]]  # up[j][v] = ancestor 2^j steps above v
        for j in range(1, n.bit_length()):
            prev = self.up[-1]
            self.up.append([prev[prev[v]] if prev[v] != -1 else -1 for v in range(n)])  # two half jumps

    def getKthAncestor(self, node: int, k: int) -> int:
        j = 0
        while k and node != -1:
            if k & 1:
                if j >= len(self.up):
                    return -1  # jump longer than any path in the tree
                node = self.up[j][node]  # take the 2^j jump
            k >>= 1
            j = j + 1
        return node

What the code is doing, line by line:

1. A jump of 2^j is two jumps of 2^(j−1), which builds each table row from the previous one.
2. n.bit_length() rows are enough: no path is longer than n − 1.
3. The query decomposes k into powers of two (its binary digits) and takes those jumps in any order.
4. Falling off the root gives −1, which then stays −1.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k larger than the depth → −1.
• Querying the root.
• A path-shaped tree (deepest possible).

Complexity: O(n log n) preprocessing and space, O(log k) per query.

Problem: Each edge on the path between u and v gets weight 1 or 2. For each query, count weightings whose path cost is odd (mod 10⁹ + 7).

Solve it on LeetCode ↗

Constraints: 2 ≤ n ≤ 10⁵ · edges.length == n - 1 · edges[i] == [ui, vi] · 1 ≤ queries.length ≤ 10⁵ · queries[i] == [ui, vi] · 1 ≤ ui, vi ≤ n · edges represents a valid tree.

From brute force to the pattern: Walking each query's path is O(n) per query. Binary-lifting LCA is O(log n) per query.

Spot it: Only the parity matters, and only weight-1 edges change it. With L edges, exactly half of the 2^L choices have an odd number of 1s: 2^(L−1) (0 when L = 0). L = depth[u] + depth[v] − 2·depth[lca], and the LCA is a binary lifting query.

Why not another pattern? Walking the path for each query is O(n), O(n · q) overall.

Approach:

1. BFS from node 1 to get depth and parent.
2. Build the binary-lifting table up[j][v].
3. For each query: lift the deeper node to the same depth, then lift both while their ancestors differ; the LCA is the parent.
4. L from depths; answer pow(2, L − 1, MOD) or 0.

from collections import deque

class Solution:
    def assignEdgeWeights(self, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        MOD = 10**9 + 7
        n = len(edges) + 1
        adj = [[] for _ in range(n + 1)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        depth = [0] * (n + 1)
        parent = [0] * (n + 1)  # 0 means "above the root"
        seen = [False] * (n + 1)
        seen[1] = True
        queue = deque([1])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if not seen[v]:
                    seen[v] = True
                    parent[v] = u
                    depth[v] = depth[u] + 1
                    queue.append(v)
        up = [parent]  # up[j][v] = ancestor 2^j steps above v
        for j in range(1, max(1, n.bit_length())):
            prev = up[-1]
            up.append([prev[prev[v]] for v in range(n + 1)])

        def lca(u, v):
            if depth[u] < depth[v]:
                u, v = v, u
            diff = depth[u] - depth[v]
            for j in range(len(up)):
                if diff >> j & 1:
                    u = up[j][u]  # lift u to v's depth
            if u == v:
                return u
            for j in range(len(up) - 1, -1, -1):
                if up[j][u] != up[j][v]:
                    u = up[j][u]  # jump both while they stay below the LCA
                    v = up[j][v]
            return parent[u]

        answer = []
        for u, v in queries:
            length = depth[u] + depth[v] - 2 * depth[lca(u, v)]  # edges on the path
            answer.append(pow(2, length - 1, MOD) if length else 0)  # half of 2^length are odd
        return answer

What the code is doing, line by line:

1. Weight 2 never changes the parity; the cost is odd exactly when an odd number of edges get weight 1: 2^(L−1) ways.
2. BFS gives depths and parents; index 0 is a sentinel above the root, so jumps past the root stay at 0.
3. LCA: equalise depths using the binary digits of the difference, then jump both from the largest power down while their ancestors differ.
4. Path length = depth[u] + depth[v] − 2·depth[lca].

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• u == v → 0 (no edges).
• Adjacent nodes → 1.
• A long chain (deep tree).

Complexity: O((n + q) log n) time, O(n log n) space.

Problem: Return every root-to-leaf path whose values sum to targetSum.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [0, 5000]. · -1000 ≤ Node.val ≤ 1000 · -1000 ≤ targetSum ≤ 1000

From brute force to the pattern: Listing every root-to-leaf path and summing each is the same DFS without pruning work; backtracking with one list avoids copies.

Spot it: All root-to-leaf paths → DFS with backtracking: keep the current path, add the node going down, remove it coming back.

Why not another pattern? Building a new list at every node copies paths over and over; one shared path with undo is cheaper.

Approach:

1. dfs(node, remaining): append node.val.
2. At a leaf with remaining == node.val, record a copy of the path.
3. Recurse into children with remaining − node.val; pop the node.

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        paths = []
        path = []

        def dfs(node, remaining):
            if node is None:
                return
            path.append(node.val)  # choose
            if node.left is None and node.right is None and remaining == node.val:
                paths.append(path[:])  # a complete root-to-leaf path with the right sum
            dfs(node.left, remaining - node.val)
            dfs(node.right, remaining - node.val)
            path.pop()  # un-choose

        dfs(root, targetSum)
        return paths

What the code is doing, line by line:

1. Only leaves end a path, so internal nodes with the right partial sum are not recorded.
2. Values can be negative, so you can't stop early when the sum overshoots.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Empty tree → [].
• Negative values.
• Several paths with the same sum.

Complexity: O(n · h) time in the worst case (copying paths), O(h) extra space.

Problem: Return the node values column by column, left to right; within a column top to bottom, and left to right for nodes in the same row.

Solve it on LeetCode ↗ (Premium)

Constraints: The number of nodes in the tree is in the range [0, 100] · -100 ≤ Node.val ≤ 100

From brute force to the pattern: DFS plus sorting by (column, row) is O(n log n); BFS gets the order for free in O(n).

Spot it: The required order inside a column is exactly BFS order (row by row, left to right). So run BFS with each node's column (left child col − 1, right col + 1) and append to a hash map of columns.

Why not another pattern? DFS visits a deeper left node before a shallower right one in the same column, which breaks the top-to-bottom rule (unless you sort by row).

Approach:

1. Queue of (node, col) starting at (root, 0).
2. Pop, append node.val to columns[col], push children with col ∓ 1.
3. Output columns from the smallest column index to the largest.

from collections import defaultdict, deque

class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        columns = defaultdict(list)
        queue = deque([(root, 0)])
        while queue:
            node, col = queue.popleft()
            columns[col].append(node.val)  # BFS order = top to bottom, left to right
            if node.left:
                queue.append((node.left, col - 1))
            if node.right:
                queue.append((node.right, col + 1))
        return [columns[c] for c in range(min(columns), max(columns) + 1)]

What the code is doing, line by line:

1. BFS processes rows in order and, inside a row, left to right, which is the tie-break the problem asks for.
2. Columns are contiguous, so ranging from the minimum to the maximum column covers them all.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Empty tree → [].
• Two nodes in the same row and column (left one first).
• A skewed tree.

Complexity: O(n) time and space.

Problem: Return the boundary anticlockwise from the root: root, left boundary, leaves, then the right boundary bottom-up (no duplicates).

Solve it on LeetCode ↗ (Premium)

Constraints: The number of nodes in the tree is in the range [1, 10⁴] · -1000 ≤ Node.val ≤ 1000

From brute force to the pattern: Several passes are already linear; the work is in getting the parts and their order right.

Spot it: Split the boundary into three traversals: walk down the left edge (prefer left child), collect leaves with a DFS, walk down the right edge (prefer right child) and reverse it. Leaves are excluded from the edges so they appear once.

Why not another pattern? One clever DFS with flags works but is easy to get wrong; three simple passes are clearer.

Approach:

1. If the root is a leaf, return [root.val].
2. Left boundary: from root.left, add non-leaves, moving left if possible else right.
3. Leaves: DFS left to right (skip the root).
4. Right boundary: from root.right, same with right first; reverse it.

class Solution:
    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
        def is_leaf(node):
            return node.left is None and node.right is None

        if is_leaf(root):
            return [root.val]
        result = [root.val]
        node = root.left
        while node:  # left edge, top to bottom
            if not is_leaf(node):
                result.append(node.val)
            node = node.left if node.left else node.right
        stack = [root]
        while stack:  # leaves, left to right
            node = stack.pop()
            if node is not root and is_leaf(node):
                result.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)  # popped first: left side first
        right = []
        node = root.right
        while node:  # right edge, collected top to bottom
            if not is_leaf(node):
                right.append(node.val)
            node = node.right if node.right else node.left
        return result + right[::-1]  # right edge goes bottom to top

What the code is doing, line by line:

1. Leaves are skipped on both edges so each leaf is added exactly once, in the leaf pass.
2. An empty left subtree means there's no left boundary at all (the root isn't repeated).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A single node.
• No left subtree.
• A leaf that is also on an edge.

Complexity: O(n) time, O(h) space.

Problem: Return the longest path of consecutive values (increasing or decreasing by 1 along the path); the path may go child-parent-child.

Solve it on LeetCode ↗ (Premium)

Constraints: The number of nodes in the tree is in the range [1, 3 * 10⁴] · -3 * 10⁴ ≤ Node.val ≤ 3 * 10⁴

From brute force to the pattern: Searching from every node is O(n²); one post-order pass is O(n).

Spot it: A path through a node is an increasing run on one side and a decreasing run on the other. Each node needs its children's runs → post-order DFS returning (inc, dec): longest runs starting at the node and going down.

Why not another pattern? Starting a search from every node is O(n²).

Approach:

1. walk(node) returns (inc, dec), both at least 1.
2. For each child: if child.val == node.val + 1, inc = max(inc, child_inc + 1); if == node.val − 1, dec = max(dec, child_dec + 1).
3. Update best = max(best, inc + dec − 1) (the node is counted twice).

class Solution:
    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        self.best = 0

        def walk(node):  # (longest +1 chain going down, longest -1 chain going down)
            if node is None:
                return 0, 0
            inc = dec = 1
            for child in (node.left, node.right):
                if child:
                    c_inc, c_dec = walk(child)
                    if child.val == node.val + 1:
                        inc = max(inc, c_inc + 1)
                    elif child.val == node.val - 1:
                        dec = max(dec, c_dec + 1)
            self.best = max(self.best, inc + dec - 1)  # up one side, down the other
            return inc, dec

        walk(root)
        return self.best

What the code is doing, line by line:

1. An increasing run below and a decreasing run below form one consecutive path through the node, e.g. 1-2-3 with 2 in the middle.
2. − 1 removes the double-counted node.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Single node → 1.
• Path through the root using both children.
• Equal values (not consecutive).

Complexity: O(n) time, O(h) space.

Problem: Return a height-balanced BST with the same values (any valid answer).

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [1, 10⁴]. · 1 ≤ Node.val ≤ 10⁵

From brute force to the pattern: Inserting values into a new BST in sorted order makes a chain; always choosing the middle balances it.

Spot it: A BST's in-order traversal is sorted. Rebuilding from a sorted array by taking the middle as the root (Convert Sorted Array to BST) gives a balanced tree.

Why not another pattern? Rotations (AVL / Day–Stout–Warren) also work but are far harder to write in an interview.

Approach:

1. In-order traversal into a list.
2. build(lo, hi): middle element is the root; recurse on both halves.

class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        values = []

        def inorder(node):
            if node:
                inorder(node.left)
                values.append(node.val)  # sorted order
                inorder(node.right)

        def build(lo, hi):
            if lo > hi:
                return None
            mid = (lo + hi) // 2  # middle value keeps both sides the same size
            return TreeNode(values[mid], build(lo, mid - 1), build(mid + 1, hi))

        inorder(root)
        return build(0, len(values) - 1)

What the code is doing, line by line:

1. Taking the middle splits the remaining values evenly, so the two subtree sizes differ by at most one at every node.
2. The in-order list is sorted, so the rebuilt tree is a BST.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already balanced.
• A chain-shaped tree.
• One node.

Complexity: O(n) time and space.

Problem: Each node has a parent pointer (no root given). Return the lowest common ancestor of nodes p and q.

Solve it on LeetCode ↗ (Premium)

Constraints: The number of nodes in the tree is in the range [2, 10⁵] · -10⁹ ≤ Node.val ≤ 10⁹ · All Node.val are unique · p != q · p and q exist in the tree

From brute force to the pattern: A set of p's ancestors costs O(h) space; the switching two-pointer walk uses O(1).

Spot it: Following parent from p and from q gives two linked lists that merge at the LCA and end at the root. It's Intersection of Two Linked Lists: two pointers that switch to the other start when they run out meet exactly at the merge point.

Why not another pattern? Storing all of p's ancestors in a set works but uses O(h) space.

Approach:

1. a = p, b = q.
2. While a is not b: a = a.parent (or q when it runs off the top); b = b.parent (or p).
3. Return a.

class Solution:
    def lowestCommonAncestor(self, p: "Node", q: "Node") -> "Node":
        a, b = p, q
        while a is not b:
            a = a.parent if a else q  # ran past the root: restart from the other node
            b = b.parent if b else p
        return a  # both walked the same total distance to the meeting point

What the code is doing, line by line:

1. If p is x steps below the LCA and q is y steps below it, with z steps from the LCA to the root: pointer a walks x + z + 1 + y before reaching the LCA the second time, and b walks y + z + 1 + x. Equal lengths, so they meet there.
2. If one is an ancestor of the other, they meet at that ancestor.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• p is an ancestor of q.
• p and q are siblings.
• Two-node tree.

Complexity: O(h) time, O(1) space.

Problem: Count nodes whose value equals the floor of the average of their subtree's values.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [1, 1000]. · 0 ≤ Node.val ≤ 1000

From brute force to the pattern: Summing every subtree separately is O(n²); one post-order pass is O(n).

Spot it: A subtree's average needs its sum and size, which come from the children → post-order DFS returning (sum, count).

Why not another pattern? Recomputing each subtree separately is O(n²).

Approach:

1. walk(node) returns (sum, count).
2. Combine children with the node; if sum // count == node.val, count it.

class Solution:
    def averageOfSubtree(self, root: TreeNode) -> int:
        self.matches = 0

        def walk(node):  # (sum, number of nodes) of this subtree
            if node is None:
                return 0, 0
            ls, lc = walk(node.left)
            rs, rc = walk(node.right)
            total, count = ls + rs + node.val, lc + rc + 1
            if total // count == node.val:
                self.matches += 1
            return total, count

        walk(root)
        return self.matches

What the code is doing, line by line:

1. Children report their totals before the parent needs them (post-order).
2. Values are non-negative, so // is the required rounding down.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Leaves always match.
• Rounding down (average 4.5 matches 4).
• Single node.

Complexity: O(n) time, O(h) space.

Problem: Houses form a binary tree; robbing two directly linked houses alerts the police. Return the maximum loot.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [1, 10⁴]. · 0 ≤ Node.val ≤ 10⁴

From brute force to the pattern: Trying both choices per node without memo is exponential; the pair-returning DFS is O(n).

Spot it: House Robber on a tree → DP on trees with a post-order DFS. Each node reports two numbers: the best for its subtree if it is robbed, and if it isn't.

Why not another pattern? Plain recursion that tries both choices at every node recomputes subtrees exponentially.

Approach:

1. walk(node) returns (rob, skip).
2. rob = node.val + left.skip + right.skip.
3. skip = max(left) + max(right).
4. Answer: max(walk(root)).

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def walk(node):  # (best if node is robbed, best if it is not)
            if node is None:
                return 0, 0
            l_rob, l_skip = walk(node.left)
            r_rob, r_skip = walk(node.right)
            rob = node.val + l_skip + r_skip  # children must be skipped
            skip = max(l_rob, l_skip) + max(r_rob, r_skip)  # children are free to choose
            return rob, skip

        return max(walk(root))

What the code is doing, line by line:

1. Robbing a node forbids its children but not its grandchildren.
2. Returning both options means each node is visited once.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Single node.
• Grandchildren beat children.
• Skewed tree.

Complexity: O(n) time, O(h) space.

Problem: Node values 0–25 are letters. Return the lexicographically smallest string from any leaf up to the root.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [1, 8500]. · 0 ≤ Node.val ≤ 25

From brute force to the pattern: This is the exhaustive DFS; the greedy shortcut is incorrect.

Spot it: All leaf-to-root strings → DFS with a path. Greedy choices fail (a shorter prefix can lose later), so compare complete strings at the leaves.

Why not another pattern? Choosing the smaller child at each step is wrong: the comparison depends on the whole leaf-to-root string.

Approach:

1. DFS with path (root to current).
2. At a leaf: s = reversed path; keep the smallest.
3. Pop on the way back.

class Solution:
    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
        self.best = None
        path = []

        def dfs(node):
            if node is None:
                return
            path.append(chr(97 + node.val))
            if node.left is None and node.right is None:
                s = "".join(reversed(path))  # read from the leaf up
                if self.best is None or s < self.best:
                    self.best = s
            dfs(node.left)
            dfs(node.right)
            path.pop()

        dfs(root)
        return self.best

What the code is doing, line by line:

1. Strings start at a leaf, so the root-to-leaf path is reversed.
2. Only leaves end a string; internal nodes aren't valid starts.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Single node.
• One leaf string is a prefix of another (ab < abc).
• Equal letters.

Complexity: O(n · h) time (building strings at leaves), O(h) space.

Problem: Replace each BST node's value with the sum of all values greater than or equal to it.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [1, 100]. · 0 ≤ Node.val ≤ 100 · All the values in the tree are unique.

From brute force to the pattern: Summing larger values per node is O(n²); one reverse in-order pass is O(n).

Spot it: In a BST, a reverse in-order traversal visits values from largest to smallest, so a running total is exactly the sum of everything ≥ the current node.

Why not another pattern? For each node, summing all larger values separately is O(n²).

Approach:

1. Visit right subtree, then node, then left subtree.
2. total += node.val; node.val = total.

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        total = 0
        stack = []
        node = root
        while stack or node:
            while node:
                stack.append(node)
                node = node.right  # biggest values first
            node = stack.pop()
            total += node.val
            node.val = total  # sum of all values >= this one
            node = node.left
        return root

What the code is doing, line by line:

1. Reverse in-order of a BST is descending order.
2. The running sum at a node includes itself and every larger value.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Single node.
• Skewed tree.
• Zero values.

Complexity: O(n) time, O(h) space.

Problem: Sum the values of nodes whose grandparent has an even value.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [1, 10⁴]. · 1 ≤ Node.val ≤ 100

From brute force to the pattern: Searching for each node's grandparent is O(n · h); passing values down is O(n).

Spot it: A node only needs its ancestors' values → DFS carrying the parent and grandparent values.

Why not another pattern? Looking up grandparents separately needs parent pointers or repeated searches.

Approach:

1. dfs(node, parent, grand): add node.val if grand is even.
2. Recurse with (child, node.val, parent).

class Solution:
    def sumEvenGrandparent(self, root: TreeNode) -> int:
        def dfs(node, parent, grand):
            if node is None:
                return 0
            total = node.val if grand % 2 == 0 else 0  # grandparent value is even
            total += dfs(node.left, node.val, parent)  # shift the window down a level
            total += dfs(node.right, node.val, parent)
            return total

        return dfs(root, 1, 1)  # odd placeholders: the root has no grandparent

What the code is doing, line by line:

1. Passing values down avoids parent pointers.
2. Odd placeholders make the top two levels contribute nothing.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No even values → 0.
• Tree with fewer than 3 levels → 0.
• All even.

Complexity: O(n) time, O(h) space.

Problem: Infection spreads each minute to adjacent nodes, starting from node start. How many minutes until the whole tree is infected?

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [1, 10⁵]. · 1 ≤ Node.val ≤ 10⁵ · Each node has a unique value. · A node with a value of start exists in the tree.

From brute force to the pattern: Simulating minute by minute over all nodes is O(n²); BFS is O(n).

Spot it: Spreading through neighbours (children and parent) one step per minute → BFS on the tree treated as an undirected graph.

Why not another pattern? DFS heights alone miss paths that go up through ancestors (unless combined carefully).

Approach:

1. DFS to record each node's parent and find the start node.
2. BFS from start over left, right and parent.
3. Count layers minus one.

from collections import deque

class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        parent = {root: None}
        source = None
        stack = [root]
        while stack:
            node = stack.pop()
            if node.val == start:
                source = node
            for child in (node.left, node.right):
                if child:
                    parent[child] = node
                    stack.append(child)
        seen = {source}
        queue = deque([source])
        minutes = -1
        while queue:
            minutes += 1  # one more minute of spreading
            for _ in range(len(queue)):
                node = queue.popleft()
                for nb in (node.left, node.right, parent[node]):
                    if nb and nb not in seen:
                        seen.add(nb)
                        queue.append(nb)
        return minutes

What the code is doing, line by line:

1. Parent links make the tree an undirected graph.
2. BFS layer t is everything infected at minute t; the last layer gives the answer.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Start at the root.
• Start at a leaf.
• Single node → 0.

Complexity: O(n) time and space.

Problem: Return the k-th largest level sum (not necessarily distinct), or −1 if there are fewer than k levels.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is n. · 2 ≤ n ≤ 10⁵ · 1 ≤ Node.val ≤ 10⁶ · 1 ≤ k ≤ n

From brute force to the pattern: Sorting the level sums is fine too; a heap of size k is slightly better.

Spot it: Per-level sums come from BFS; then it's a top-k question on those sums.

Why not another pattern? Nothing smarter is needed; the levels are at most n.

Approach:

1. BFS one level at a time, summing values.
2. If fewer than k levels, −1; else the k-th largest sum.

import heapq
from collections import deque

class Solution:
    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
        sums = []
        queue = deque([root])
        while queue:
            total = 0
            for _ in range(len(queue)):  # one level
                node = queue.popleft()
                total += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            sums.append(total)
        if len(sums) < k:
            return -1
        return heapq.nlargest(k, sums)[-1]  # k-th largest

What the code is doing, line by line:

1. Each BFS round is one level.
2. nlargest(k, …)[-1] is the k-th largest using a size-k heap.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Fewer than k levels → −1.
• Equal sums (counted separately).
• Single node.

Complexity: O(n + L log k) time for L levels, O(n) space.

Problem: In a tree rooted at 1, take a deepest node. Count weightings (1 or 2 per edge) of the root-to-node path with an odd total (mod 10⁹ + 7).

Solve it on LeetCode ↗

Constraints: 2 ≤ n ≤ 10⁵ · edges.length == n - 1 · edges[i] == [ui, vi] · 1 ≤ ui, vi ≤ n · edges represents a valid tree.

From brute force to the pattern: Enumerating 2^d weightings is exponential; parity gives 2^(d−1) directly.

Spot it: Only the path length d matters (any deepest node has the same depth). Weight 2 doesn't change parity, so the cost is odd when an odd number of edges weigh 1: exactly half of the 2^d choices. Find d with a BFS over the tree.

Why not another pattern? Enumerating weightings is 2^d.

Approach:

1. BFS from node 1 to get the maximum depth d.
2. Return 2^(d − 1) mod p.

from collections import deque

class Solution:
    def assignEdgeWeights(self, edges: List[List[int]]) -> int:
        n = len(edges) + 1
        adj = [[] for _ in range(n + 1)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        depth = [-1] * (n + 1)
        depth[1] = 0
        queue = deque([1])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if depth[v] < 0:
                    depth[v] = depth[u] + 1
                    queue.append(v)
        d = max(depth)  # edges on the path to a deepest node
        return pow(2, d - 1, 10**9 + 7)  # half of all 2^d weightings are odd

What the code is doing, line by line:

1. Flipping the first edge between 1 and 2 pairs up odd and even weightings, so exactly half are odd.
2. n ≥ 2 guarantees d ≥ 1.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Two nodes → 1.
• A long path.
• Many deepest nodes.

Complexity: O(n) time and space.

Problem: A camera monitors its parent, itself and its children. Return the fewest cameras to monitor every node.

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [1, 1000]. · Node.val == 0

From brute force to the pattern: Trying placements is exponential; tree DP with 3 states (or this greedy) is O(n).

Spot it: Leaves should never hold cameras: their parent covers more. Decide bottom-up (post-order): each node reports one of three states, and a node puts a camera exactly when a child is uncovered.

Why not another pattern? Trying camera placements is exponential; a top-down greedy misplaces cameras.

Approach:

1. state(node): 0 = not covered, 1 = has a camera, 2 = covered without a camera. None counts as covered (2).
2. If any child is 0 → place a camera here (1).
3. Else if any child is 1 → covered (2). Else → 0 (let the parent handle it).
4. If the root ends up 0, add one camera.

class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        self.cameras = 0
        NEEDS, CAMERA, COVERED = 0, 1, 2

        def state(node):
            if node is None:
                return COVERED  # empty spots never need cameras
            left, right = state(node.left), state(node.right)
            if left == NEEDS or right == NEEDS:
                self.cameras += 1  # a child is unmonitored: put a camera here
                return CAMERA
            if left == CAMERA or right == CAMERA:
                return COVERED  # a child's camera watches this node
            return NEEDS  # leave it to the parent

        if state(root) == NEEDS:
            self.cameras += 1  # the root has no parent to cover it
        return self.cameras

What the code is doing, line by line:

1. Delaying cameras to the parent of an uncovered node covers the most nodes per camera.
2. Treating None as covered stops leaves from asking for cameras below them.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Single node → 1.
• A long chain.
• Full binary tree.

Complexity: O(n) time, O(h) space.

Problem: The preorder output writes each node as D dashes (its depth) followed by its value. Rebuild the tree (a single child is always a left child).

Solve it on LeetCode ↗

Constraints: The number of nodes in the original tree is in the range [1, 1000]. · 1 ≤ Node.val ≤ 10⁹

From brute force to the pattern: Recursive splitting is O(n²) in the worst case; the stack parse is O(n).

Spot it: Preorder with depths: the stack of the current path tells you the parent. Pop until the stack has exactly depth nodes; the top is the parent; attach as left child, or right if left is taken.

Why not another pattern? Recursively splitting the string by depth markers is fiddly and quadratic in the worst case.

Approach:

1. Read dashes → depth, digits → value.
2. Pop the stack while its size > depth.
3. Attach to the top (left first), push the new node.

class Solution:
    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
        stack = []  # the path from the root to the last node added
        i, n = 0, len(traversal)
        while i < n:
            depth = 0
            while traversal[i] == "-":
                depth += 1
                i += 1
            j = i
            while j < n and traversal[j].isdigit():
                j += 1
            node = TreeNode(int(traversal[i:j]))
            i = j
            while len(stack) > depth:
                stack.pop()  # climb back up to the parent's level
            if stack:
                parent = stack[-1]
                if parent.left is None:
                    parent.left = node
                else:
                    parent.right = node
            stack.append(node)
        return stack[0]

What the code is doing, line by line:

1. In preorder, a node's parent is the most recent node one level up, which is the stack element at index depth − 1.
2. Values can have several digits, so they're parsed as runs of digits.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Multi-digit values.
• Single node.
• Deep left chain.

Complexity: O(n) time, O(h) space.

Problem: Return the maximum sum of keys of any subtree that is a BST (0 if all such sums are negative).

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [1, 4 * 10⁴]. · -4 * 10⁴ ≤ Node.val ≤ 4 * 10⁴

From brute force to the pattern: Validating every subtree is O(n²); one post-order pass is O(n).

Spot it: A subtree is a BST if both children are BSTs and left.max < node.val < right.min. Those facts come from the children → post-order DFS returning (is_bst, min, max, sum).

Why not another pattern? Validating each subtree separately is O(n²).

Approach:

1. Empty subtree: BST with min = +∞, max = −∞, sum 0.
2. Node is a BST if both are and l.max < val < r.min; update the best sum.
3. Otherwise mark it not a BST.

class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        self.best = 0
        INF = float("inf")

        def walk(node):  # (is BST, min, max, sum)
            if node is None:
                return True, INF, -INF, 0
            l_ok, l_min, l_max, l_sum = walk(node.left)
            r_ok, r_min, r_max, r_sum = walk(node.right)
            if l_ok and r_ok and l_max < node.val < r_min:
                total = l_sum + node.val + r_sum
                self.best = max(self.best, total)
                return True, min(l_min, node.val), max(r_max, node.val), total
            return False, 0, 0, 0  # not a BST: ancestors can't be BSTs either

        walk(root)
        return self.best

What the code is doing, line by line:

1. The empty subtree's min = +∞, max = −∞ makes the comparison pass for leaves.
2. best starts at 0 because an empty BST is allowed.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All negative → 0.
• The whole tree is a BST.
• Duplicate values (not a BST).

Complexity: O(n) time, O(h) space.

Problem: Given n small BSTs with distinct roots, repeatedly replace a leaf with the tree whose root has that value. Return the final BST if all merge into one valid BST, else None.

Solve it on LeetCode ↗

Constraints: n == trees.length · 1 ≤ n ≤ 5 * 10⁴ · The number of nodes in each tree is in the range [1, 3]. · Each node in the input may have children but no grandchildren. · No two roots of trees have the same value. · All the trees in the input are valid BSTs. · 1 ≤ TreeNode.val ≤ 5 * 10⁴.

From brute force to the pattern: Trying merge orders is exponential; the forced structure plus one validating DFS is linear.

Spot it: Each tree root can attach under exactly one matching leaf, so the final root is the only root that isn't a leaf value anywhere (a hash map of roots and a count of leaves). Then DFS from that root, replacing leaves from the map, and validate the BST with value bounds.

Why not another pattern? Trying merge orders is exponential; any order of valid attachments gives the same tree.

Approach:

1. Map root value → tree; collect all leaf values.
2. The final root is a tree whose root value isn't a leaf value (must be exactly one).
3. DFS with bounds (lo, hi): a leaf matching a stored root is replaced by that tree (removing it from the map); fail if any value breaks the bounds.
4. Succeed only if every tree was used.

class Solution:
    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:
        roots = {t.val: t for t in trees}
        leaves = set()
        for t in trees:
            for child in (t.left, t.right):
                if child:
                    leaves.add(child.val)
        top = [t for t in trees if t.val not in leaves]
        if len(top) != 1:
            return None  # no unique final root
        root = top[0]
        del roots[root.val]

        def build(node, lo, hi):  # attach trees at leaves and check BST bounds
            if node is None:
                return True
            if not lo < node.val < hi:
                return False
            if node.left is None and node.right is None and node.val in roots:
                sub = roots.pop(node.val)  # replace this leaf with its tree
                node.left, node.right = sub.left, sub.right
            return build(node.left, lo, node.val) and build(node.right, node.val, hi)

        ok = build(root, float("-inf"), float("inf"))
        return root if ok and not roots else None  # every tree must be used

What the code is doing, line by line:

1. Root values are distinct and each leaf can take one tree, so the merge structure is forced; only the root is free.
2. Checking bounds while attaching validates the whole merged tree in one pass.
3. Leftover trees mean some couldn't be attached (or a cycle), so the answer is None.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Two trees attaching to each other (cycle) → None.
• Already a single tree.
• A merge that breaks BST order.

Complexity: O(n) time and space (each tree has at most 3 nodes).