Find All Ancestors of a Node in a Binary Tree

Finding the ancestors of a node in a binary tree means collecting every node on the path from the root down to the target, root included, the target itself excluded.

This is a standard DSA problem in placement drives for CSE, ECE, and IT students. The recursive solution fits on a whiteboard in three minutes. The iterative version is the follow-up interviewers reach for when they want to know whether you can translate recursion into an explicit stack.

What “ancestor” means

Consider this binary tree, which serves as the running example throughout this article:

        15
       /  \
      12   18
     /  \     \
    8   13    24
              /  \
             22   27

The ancestors of each node, ordered from immediate parent up to root:

Node	Ancestors
15	(none — root node)
12	15
18	15
8	12, 15
13	12, 15
24	18, 15
22	24, 18, 15
27	24, 18, 15

Some problems ask for the list in root-to-parent order instead (the reverse of what is shown above). Confirm the expected order with the interviewer or the problem statement before writing code.

The Wikipedia article on tree traversal covers the formal DFS classifications (pre-order, in-order, post-order) that the two approaches below build on.

Recursive approach

The idea is a post-order DFS. On the way down, the function checks if the current node is the target. On the way back up (the unwinding phase), any call frame that received True from a subtree appends its node value to the ancestor list.

Algorithm steps

• Step 1: If root is None, return False.
• Step 2: If root.data == key, return True.
• Step 3: Recurse into the left subtree. If it returns True, append root.data and return True.
• Step 4: Recurse into the right subtree. If it returns True, append root.data and return True.
• Step 5: Return False (key not found in this subtree).

Python code

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.data = key


def find_ancestors_recursive(root, key, ancestors):
    """Return True if key is found; populate ancestors on the unwinding phase."""
    if not root:
        return False
    if root.data == key:
        return True
    if (find_ancestors_recursive(root.left, key, ancestors) or
            find_ancestors_recursive(root.right, key, ancestors)):
        ancestors.append(root.data)
        return True
    return False


# Build the example tree
root = Node(15)
root.left = Node(12)
root.right = Node(18)
root.left.left = Node(8)
root.left.right = Node(13)
root.right.right = Node(24)
root.right.right.left = Node(22)
root.right.right.right = Node(27)

ancestors = []
find_ancestors_recursive(root, 22, ancestors)
print(ancestors)  # [24, 18, 15]

Note that ancestors is a required parameter here, not a default []. Using a mutable default argument in Python creates a shared list object across calls. After the first successful run, a second call finds stale data already in the list. The safest pattern is to pass it in explicitly, as shown above.

Call trace for node 22

The call sequence, simplified to show which nodes append:

• Call on 15: recurse left (12).
  • Call on 12: recurse left (8) returns False; recurse right (13) returns False. 12 returns False.
• Call on 15 continues: recurse right (18).
  • Call on 18: no left child; recurse right (24).
    • Call on 24: recurse left (22).
      • Call on 22: root.data == key. Return True.
    • 24 receives True from left, appends 24, returns True.
  • 18 receives True from right, appends 18, returns True.
• 15 receives True from right, appends 15, returns True.

Result: ancestors = [24, 18, 15]. The list fills in order from the deepest ancestor outward to root.

Iterative approach

The iterative method builds a parent-pointer dictionary as it traverses the tree. When the target is found, it walks the dictionary from the target node up to the root.

Algorithm steps

• Step 1: Push the root onto a stack; record parent[root] = None.
• Step 2: Pop a node. If node.data == key, stop the loop.
• Step 3: Otherwise push right child (if any) and left child (if any), recording their parent entries.
• Step 4: After the loop, if the key was not found, return an empty list.
• Step 5: Walk the parent chain from the found node up to the root, collecting each parent’s value.

Python code

def find_ancestors_iterative(root, key):
    if not root:
        return []

    stack = [root]
    parent = {root: None}

    node = None
    while stack:
        node = stack.pop()
        if node.data == key:
            break
        if node.right:
            stack.append(node.right)
            parent[node.right] = node
        if node.left:
            stack.append(node.left)
            parent[node.left] = node

    # Guard: key was not found in the tree
    if node is None or node.data != key:
        return []

    ancestors = []
    while parent.get(node) is not None:
        ancestors.append(parent[node].data)
        node = parent[node]

    return ancestors


print(find_ancestors_iterative(root, 22))  # [24, 18, 15]
print(find_ancestors_iterative(root, 8))   # [12, 15]
print(find_ancestors_iterative(root, 15))  # [] (root has no ancestors)
print(find_ancestors_iterative(root, 99))  # [] (key not in tree)

The key-not-found guard on the third-to-last block is absent from many legacy implementations. Without it, the function walks a random leaf’s parent chain and returns a nonsense list.

Time and space complexity

Both methods visit each node at most once.

Approach	Time	Space	Notes
Recursive	O(N)	O(N)	Stack depth = tree height; worst case N for a fully skewed tree
Iterative	O(N)	O(N)	Explicit stack + parent dictionary each grow up to N entries

For a balanced tree the height is log2(N), so average recursion depth is O(log N). For a skewed tree (every node has exactly one child) the height equals N, and Python’s default recursion limit of 1000 frames becomes a practical ceiling. The iterative version has no such limit.

In a placement interview, lead with the recursive approach to demonstrate DFS understanding, then offer the iterative version as the production-safe alternative for trees of unknown or large depth. That two-step answer is what most technical rounds reward.

See space complexity of algorithms with examples for a structured walkthrough of how recursion depth translates into stack-space cost.

What to expect in placement rounds

The base problem is frequently extended in the following ways:

• Lowest Common Ancestor (LCA): given two nodes, find their nearest shared ancestor. The ancestor-path logic above is a direct component of standard LCA algorithms.
• Path from root to node: print the complete root-to-node path. The ancestors list from the recursive function gives this path in reverse; call ancestors[::-1] after collecting it.
• Check if X is an ancestor of Y: call find_ancestors_recursive(root, Y, ancestors) and check whether X is in the returned list.
• Depth of a node: the length of the ancestor list equals the depth of the node, with the root at depth 0.

If the traversal-and-collect pattern here feels familiar, it is the same structure used in finding the equilibrium index of an array and in finding all symmetric pairs in an array: traverse once, accumulate state, exit when a condition is met.

GeeksforGeeks lists this problem in its canonical tree-traversal interview set, which gives a sense of how often it appears in company coding rounds.

The recursive call-stack propagation pattern from the approach above (return a boolean upward, collect values on the unwind) is a core tree idiom that also turns up in AI-assisted code generation tasks. TinkerLLM at ₹299 lets you run those prompts hands-on, experiment with how models generate and debug recursive tree code, and build the kind of project that placement interviewers in product companies notice.