Trees and Binary Search Trees Questions

Approach
Use recursion with backtracking. A path sum is the sum of values from the root to a leaf. Because node values can be negative, I would not prune when the running sum gets too large, since later negative values could bring it back down.

def has_path_sum(root, target_sum):
    def dfs(node, remaining):
        if node is None:
            return False

        remaining -= node.val
        if node.left is None and node.right is None:
            return remaining == 0

        return dfs(node.left, remaining) or dfs(node.right, remaining)

    return dfs(root, target_sum)

Worked example
For the path 5 -> 4 -> 11 and target 20, the recursion checks 20 - 5 = 15, then 15 - 4 = 11, then 11 - 11 = 0, so it returns True.

Why backtracking is enough
Each recursive call gets its own remaining value, so there is no shared state to clean up. The function explores one root-to-leaf path at a time and stops as soon as it finds a match.

Complexity
Time is O(n) in the worst case, and space is O(h) for the recursion stack, where h is tree height.

Conventions first
I would define height as the number of edges on the longest path from a node to a leaf. That makes an empty tree height -1 and a leaf height 0. I would define depth as the number of edges from the root to a node, so the root has depth 0. That keeps the API consistent.

def tree_height(root):
    if root is None:
        return -1
    return 1 + max(tree_height(root.left), tree_height(root.right))


def node_depth(root, target):
    def dfs(node, depth):
        if node is None:
            return None
        if node is target:
            return depth
        left = dfs(node.left, depth + 1)
        if left is not None:
            return left
        return dfs(node.right, depth + 1)

    return dfs(root, 0)

Worked example
If the tree is 10 -> 4 -> 2, then tree_height(root) is 2, node_depth(root, 10) is 0, and node_depth(root, 2) is 2.

API design choice
I would return None if the target node is not present, rather than guessing. That makes the behavior explicit and avoids ambiguity.

Approach
I would keep one mutable list for the current path, append when I go down a node, and pop when I backtrack. At a leaf, I join a copy of the current path into a string. That avoids corrupting earlier paths.

def binary_tree_paths(root):
    result = []
    path = []

    def dfs(node):
        if node is None:
            return

        path.append(str(node.val))

        if node.left is None and node.right is None:
            result.append('->'.join(path))
        else:
            dfs(node.left)
            dfs(node.right)

        path.pop()

    dfs(root)
    return result

Worked example
For a tree 1 -> 2 -> 5 and 1 -> 3, the output is ['1->2->5', '1->3'].

Memory cost
The extra working memory is O(h) for the current path, where h is tree height. But the returned output can be much larger, because the number of root-to-leaf paths can grow quickly with the number of leaves. If callers do not need all paths at once, a generator would be more memory-friendly.

What I would change before shipping
For production, I would remove recursion from any traversal or path algorithm that could see a deep tree. An explicit stack is safer than trying to raise Python's recursion limit, because sys.setrecursionlimit only hides the risk and can still crash the process on very deep inputs.

Concrete changes

• Replace recursive traversals with iterative versions.
• Use explicit stacks for inorder, postorder, and path-sum checks.
• Add tests for degenerate trees, such as a single chain of 20,000 nodes.
• Decide what to do on missing nodes or empty trees, and return that consistently.
• Add observability, such as logging maximum depth seen in production.

Example
If a customer uploads a tree shaped like a linked list, a recursive path-sum solution may fail even though the logic is correct. An iterative DFS with (node, state) pairs avoids that failure mode.

Production rule
My default is: if input depth is unbounded, do not rely on recursion. Use iterative code and make memory use predictable.

Design
I would compare nodes by identity, not by value, because duplicate values make value-based matching ambiguous. To avoid false positives, the helper should return both the candidate ancestor and whether each target was actually found.

def lowest_common_ancestor(root, p, q):
    def dfs(node):
        if node is None:
            return None, False, False

        left_lca, left_has_p, left_has_q = dfs(node.left)
        if left_lca is not None and left_has_p and left_has_q:
            return left_lca, True, True

        right_lca, right_has_p, right_has_q = dfs(node.right)
        if right_lca is not None and right_has_p and right_has_q:
            return right_lca, True, True

        has_p = left_has_p or right_has_p or node is p
        has_q = left_has_q or right_has_q or node is q

        if has_p and has_q:
            return node, True, True

        return None, has_p, has_q

    lca, has_p, has_q = dfs(root)
    return lca if has_p and has_q else None

Worked example
If p is in the left subtree and q is in the right subtree, the root becomes the LCA. If q is missing from the tree, the final has_q flag stays false, so the function returns None instead of a misleading ancestor.

Why this is safe
The function only reports an ancestor when both targets are confirmed present in the tree.