Understanding Tree Algorithms — Implementation Deep Dive

Recursive vs iterative approaches, stack-based implementations, and production-ready code for finding the Lowest Common Ancestor.

Author

Mr. Oz

Date

21 March 2026

Read

8 mins

Now that we understand the family gathering analogy, let's dive into the actual implementation. We'll explore recursive solutions, iterative approaches, and production-ready patterns.

The Tree Node Structure

First, let's define a binary tree node. A node contains three things:

Value/Data: The actual content (number, string, object, etc.)
Left pointer: Reference to the left child (or null/None)
Right pointer: Reference to the right child (or null/None)

# Python implementation
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left    # Left child
        self.right = right  # Right child

// Java implementation
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

// C++ implementation
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

The Recursive LCA Algorithm

The recursive approach follows these steps:

Base case: If current node is null, p, or q — return it
Recurse: Search left and right subtrees
Combine: If both sides return non-null, current is LCA
Propagate: Return whichever side is non-null

def lowestCommonAncestor(root, p, q):
    # Base case: found target or reached end
    if not root or root == p or root == q:
        return root

    # Search both subtrees
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)

    # If both found, current is LCA
    if left and right:
        return root

    # Propagate the found node upward
    return left if left else right

Why Does This Work?

The algorithm exploits a key insight: the first node where p and q are found in different subtrees IS the LCA.

Both null

Neither p nor q in this subtree → return null

One non-null

Found p OR q in this subtree → propagate up

Both non-null

p and q in different branches → THIS is LCA!

Time & Space Complexity

Time: O(n)

In the worst case, we visit every node once. The algorithm terminates early if both targets are found in the same subtree.

Space: O(h)

The recursion stack uses space proportional to tree height h. O(n) for skewed trees, O(log n) for balanced trees.

Common Pitfalls to Avoid

Comparing by value instead of reference: Two nodes may have the same value but be different objects. Always use == for reference comparison.
Forgetting a node is its own ancestor: If p is an ancestor of q, p is the LCA — not p's parent!
Assuming nodes exist: This implementation assumes both p and q exist in the tree. Handle missing nodes separately if needed.

Production Tips

Validate inputs: Check if root, p, or q is null before starting
Consider iterative version: For very deep trees, use iterative approach with parent pointers to avoid stack overflow
Cache results: If you need to find LCA multiple times, consider preprocessing with parent pointers or binary lifting