Trees and Binary Search Trees Questions

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.

Approach
Inorder traversal means: visit the left child, then the node itself, then the right child. I would use recursion because it matches the tree structure naturally.

def inorder_traversal(root):
    result = []

    def dfs(node):
        if node is None:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)

    dfs(root)
    return result

Worked example
For a tree with root 2, left child 1, and right child 3, the result is [1, 2, 3].

Empty tree
If root is None, the helper returns immediately and the answer is an empty list. That is the correct result because there are no nodes to visit.

Why recursion can fail
Python has a finite call stack. On a pathologically deep tree, such as a chain of 10,000 nodes, recursive calls can raise RecursionError even though the logic is correct. In that case, I would switch to an iterative traversal with an explicit stack.

Approach
This is postorder traversal, which means left child, right child, then node. Since recursion is off the table, I would use an explicit stack and a last_visited pointer to know when a node's right subtree has already been processed.

def postorder_traversal(root):
    result = []
    stack = []
    current = root
    last_visited = None

    while current is not None or stack:
        if current is not None:
            stack.append(current)
            current = current.left
        else:
            peek = stack[-1]
            if peek.right is not None and last_visited is not peek.right:
                current = peek.right
            else:
                result.append(peek.val)
                last_visited = stack.pop()

    return result

Stack walk-through
For root 1 with left 2 and right 3:

• Push 1, then push 2.
• Node 2 has no children, so pop and output 2.
• Back at 1, move to 3, push 3, then pop and output 3.
• Finally pop and output 1.

Why this works
The stack always holds the path to the current node. last_visited prevents revisiting a right subtree after it has already been processed. Time is O(n), space is O(h), where h is tree height.

Idea
The slow part in the original version is recomputing heights for the same subtree many times. I would make one DFS return the height of a subtree, and use -1 as a sentinel meaning unbalanced. That lets me stop early as soon as imbalance is detected.

def is_balanced(root):
    def height(node):
        if node is None:
            return 0

        left_h = height(node.left)
        if left_h == -1:
            return -1

        right_h = height(node.right)
        if right_h == -1:
            return -1

        if abs(left_h - right_h) > 1:
            return -1

        return max(left_h, right_h) + 1

    return height(root) != -1

Worked example
For a skewed chain 1 -> 2 -> 3 -> 4, the imbalance is detected near the top once the left and right subtree heights differ by more than 1, and the -1 bubbles upward immediately.

Why this is better
Each subtree is processed once, so the runtime becomes O(n) instead of repeatedly revisiting nodes. Space is O(h) for the recursion stack.

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.