Trees and Binary Search Trees Questions

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.

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.

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
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.