Tree Depth-First Search

Recursive structure

Most tree problems are recursive: solve the left and right subtrees, then combine (depth is 1 plus the larger child depth). Pass constraints down when needed: validating a binary search tree passes the allowed (low, high) range, because comparing only with direct children misses violations deeper down. Path problems subtract values on the way down and check at leaves. Recursion depth equals tree height.

Depth, BST validation and path sums, run

I ran this with Python 3.12.3 (standard library only). The second tree fails BST validation because 9 sits in the left subtree of 8, even though it is larger than its parent 3; root-to-leaf paths 8-3-6 and 8-10-14 sum to 17 and 32.

# Tree DFS: depth, BST validation and path sum
class T:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def depth(n):
    return 0 if n is None else 1 + max(depth(n.left), depth(n.right))

def is_bst(n, lo=float("-inf"), hi=float("inf")):
    if n is None:
        return True
    if not lo < n.val < hi:
        return False
    return is_bst(n.left, lo, n.val) and is_bst(n.right, n.val, hi)

def has_path_sum(n, target):
    if n is None:
        return False
    if n.left is None and n.right is None:
        return n.val == target
    return has_path_sum(n.left, target - n.val) or has_path_sum(n.right, target - n.val)

good = T(8, T(3, T(1), T(6)), T(10, None, T(14)))
bad = T(8, T(3, T(1), T(9)), T(10))      # 9 is in the left subtree of 8
print(depth(good), is_bst(good), is_bst(bad))
print(has_path_sum(good, 17), has_path_sum(good, 32), has_path_sum(good, 100))

Output:

3 True False
True True False

State the base case first

Start every recursive function with what happens for an empty node.

त्वरित जाँच: Why must BST validation pass bounds down the tree?

• To count nodes
• To make it faster
• Because recursion requires parameters
• A node must respect all ancestors, not just its parent