List the ancestors of a binary tree node

You're in a LinkedIn technical screen and the interviewer pulls up a binary tree diagram. "Given a target node in this tree," they say, "can you return a list of all its ancestors, ordered from the closest parent up to the root?" This problem, also known as "Find All Ancestors of a Node in Binary Tree" on other platforms, tests your ability to combine DFS traversal with backtracking. It's a pattern that shows up frequently in tree problems at companies like Twitter and LinkedIn.

TL;DR

Use a recursive DFS helper that returns a boolean: true if the target was found in the current subtree, false otherwise. When a recursive call returns true, the current node is an ancestor, so add its data to the output list. This builds the ancestor list from closest-to-target to farthest (the root). The approach runs in O(n) time and O(n) space.

Why This Problem Matters

Finding ancestors in a binary tree is a building block for several harder problems. Lowest common ancestor, path queries, and distance calculations between nodes all rely on the ability to trace a path from a node back to the root. If you can write a clean recursive builder that collects ancestors during backtracking, you already have the core logic for these more advanced questions.

Binary Trees: Quick Refresher

A binary tree is a hierarchical structure where each node has at most two children. The node at the top is the root, and nodes with no children are leaves.

In this tree, node 4's ancestors are 3 and 1 (closest to farthest). Node 2's only ancestor is 1. The root node 1 has no ancestors at all.

Understanding the Problem

Let's pin down exactly what we need:

Given: The root of a binary tree and an integer n Find: The node with data == n, then return the data of all its ancestors Ordering: Closest ancestor first, root last Edge cases: Return an empty list if the target doesn't exist or has no ancestors

Here are some examples from the tree above:

listAncestors(root, 5) -> [3, 1]
listAncestors(root, 4) -> [3, 1]
listAncestors(root, 3) -> [1]
listAncestors(root, 2) -> [1]
listAncestors(root, 1) -> []

The highlighted path below shows ancestors of node 4:

And here's the path for node 5:

Edge Cases

1. Target is the root: No ancestors exist, return an empty list
2. Target doesn't exist: DFS never finds it, return an empty list
3. Single-node tree: If the target is the root, empty list. If not, also empty
4. Skewed tree: All nodes on one side, the ancestor list could be as long as n-1

Solution Approach

The trick here is figuring out which nodes lie on the path between the root and the target. A simple traversal visits every node, but we only want to collect the ones that are direct ancestors.

The Backtracking Insight

Think of it this way. You're exploring a maze, and you need to find a specific room. At every fork, you try one direction. If it leads to a dead end, you backtrack and try the other. When you finally find the room, you retrace your steps and mark every corridor you walked through.

That's exactly how our recursive builder works:

1. If the current node is null, return false (dead end)
2. If the current node's data matches n, return true (found it!)
3. Recursively search the left subtree, then the right subtree
4. If either subtree returns true, the current node is an ancestor. Add it to the list and return true
5. If neither subtree contains the target, return false

The boolean return value is the key. It propagates upward through the call stack, telling each parent node whether to include itself in the ancestor list.

Tracing Through the Algorithm

Let's walk through listAncestors(root, 4) on our example tree:

The DFS visits node 1, then goes left to node 2. Node 2 has no children and is not the target, so it returns false. Back at node 1, we try the right child: node 3. Node 3 goes left to node 4, which matches our target. Node 4 returns true. Back at node 3, the left subtree returned true, so we add 3 to the list and return true. Back at node 1, the right subtree returned true, so we add 1 to the list.

Final result: [3, 1].

Implementation

Prefer a different language? Jump to solutions in other languages.

Here's the complete Java solution:

import java.util.LinkedList;
import java.util.List;

public class Solution {
  public List<Integer> listAncestors(TreeNode root, int n) {
    List<Integer> out = new LinkedList<>();
    build(root, out, n);
    return out;
  }

  private boolean build(TreeNode node, List<Integer> list, int n) {
    if (node == null) return false;
    else if (node.data == n) return true;
    else if (build(node.left, list, n) || build(node.right, list, n)) {
      list.add(node.data);
      return true;
    } else return false;
  }
}

The listAncestors method creates an empty list, kicks off the recursive build, and returns the result. The build method does all the heavy lifting. Notice how the list is passed by reference, so every ancestor along the path adds itself as the recursion unwinds.

Why This Ordering Works

The closest ancestor gets added first because of how recursion unwinds. Node 3 (the parent of node 4) returns from its recursive call before node 1 (the grandparent). Each node adds itself to the list on the way back up, producing the closest-to-farthest order naturally.

Complexity Analysis

Time Complexity: O(n)

In the worst case, DFS visits every node in the tree before finding the target or confirming it doesn't exist. Each node is processed in constant time (one comparison, at most two recursive calls), so the total time is O(n).

Space Complexity: O(n)

Two factors contribute to the O(n) space usage:

• Call stack: In a skewed tree (every node has only one child), the recursion depth reaches n. For balanced trees, this is O(log n).
• Output list: The ancestor list can hold up to n-1 elements in a skewed tree.

Common Pitfalls

1. Forgetting the boolean return value: Without the boolean, you have no way to know which nodes are on the target's path. Some candidates try to use the list size as a signal, but that breaks when the target is absent.

2. Adding the target node itself: The problem asks for ancestors only. The target node returns true immediately, before any list.add call, so it never adds itself. But be careful if you restructure the conditions.

3. Wrong ordering: If you add the node data before the recursive call instead of after, you get root-to-target order instead of target-to-root order. The problem specification asks for closest ancestor first.

4. Not handling missing targets: If the target doesn't exist in the tree, every recursive call returns false, nothing gets added to the list, and you return an empty list. Make sure your code handles this gracefully.

Interview Tips

When you see this problem in an interview:

1. Clarify the return order. Some versions want root-first, others want closest-first. This changes where you insert into the list.

2. Mention the backtracking pattern by name. Interviewers appreciate when you recognize this as a DFS with backtracking problem rather than just ad-hoc recursion.

3. Draw the tree and trace through a small example. Showing how the boolean propagates back up from the target to the root makes the algorithm click.

4. Discuss the BST optimization. If the tree is a binary search tree, you can find the target in O(log n) by following the ordering property. Every node you visit on the way down is an ancestor.

5. Connect to related problems. This builder pattern appears in lowest common ancestor, root-to-leaf path sum, and tree diameter problems.

Solutions in Other Languages

Python

class Solution:
    def list_ancestors(self, root, n):
        out = []
        self.build(root, out, n)
        return out

    def build(self, node, arr, n):
        if node is None:
            return False
        elif node.data == n:
            return True
        elif self.build(node.left, arr, n) or self.build(node.right, arr, n):
            arr.append(node.data)
            return True
        else:
            return False

JavaScript

class Solution {
  listAncestors(root, n) {
    const out = [];
    this.build(root, out, n);
    return out;
  }

  build(node, arr, n) {
    if (node === null) return false;
    else if (node.data === n) return true;
    else if (this.build(node.left, arr, n) || this.build(node.right, arr, n)) {
      arr.push(node.data);
      return true;
    } else return false;
  }
}

TypeScript

class Solution {
  listAncestors(root: TreeNode | null, n: number): number[] {
    const out: number[] = [];
    this.build(root, out, n);
    return out;
  }

  private build(node: TreeNode | null, arr: number[], n: number): boolean {
    if (node === null) return false;
    else if (node.data === n) return true;
    else if (this.build(node.left, arr, n) || this.build(node.right, arr, n)) {
      arr.push(node.data);
      return true;
    } else return false;
  }
}

C++

#include <vector>

class Solution {
public:
  std::vector<int> listAncestors(TreeNode *root, int n) {
    std::vector<int> out;
    build(root, out, n);
    return out;
  }

private:
  bool build(TreeNode *node, std::vector<int> &builderVector, int n) {
    if (node == nullptr) return false;
    else if (node->data == n) return true;
    else if (build(node->left, builderVector, n) ||
             build(node->right, builderVector, n)) {
      builderVector.push_back(node->data);
      return true;
    } else return false;
  }
};

Scala

import scala.collection.mutable

class Solution {
  def listAncestors(root: TreeNode, n: Int): List[Int] = {
    val arr = mutable.ArrayBuffer[Int]()
    build(root, arr, n)
    arr.toList
  }

  private def build(
    node: TreeNode,
    arr: mutable.ArrayBuffer[Int],
    n: Int
  ): Boolean = {
    if (node == null) false
    else if (node.data == n) true
    else if (build(node.left, arr, n) || build(node.right, arr, n)) {
      arr.append(node.data)
      true
    }
    else false
  }
}

Kotlin

import java.util.LinkedList

class Solution {
    fun listAncestors(root: TreeNode?, n: Int): List<Int> {
        val out = LinkedList<Int>()
        build(root, out, n)
        return out
    }

    private fun build(node: TreeNode?, list: MutableList<Int>, n: Int): Boolean {
        if (node == null) return false
        else if (node.data == n) return true
        else if (build(node.left, list, n) || build(node.right, list, n)) {
            list.add(node.data)
            return true
        } else return false
    }
}

Swift

class Solution {
    func listAncestors(_ root: TreeNode?, _ n: Int) -> [Int] {
        var out = [Int]()
        build(root, &out, n)
        return out
    }

    @discardableResult
    private func build(_ node: TreeNode?, _ list: inout [Int], _ n: Int) -> Bool {
        if node == nil { return false }
        else if node!.data == n { return true }
        else if build(node!.left, &list, n) || build(node!.right, &list, n) {
            list.append(node!.data)
            return true
        } else { return false }
    }
}

Rust

impl Solution {
    pub fn list_ancestors(&self, root: Option<Box<TreeNode>>, n: i32) -> Vec<i32> {
        let mut out: Vec<i32> = Vec::new();
        Self::build(&root, &mut out, n);
        out
    }

    fn build(node: &Option<Box<TreeNode>>, list: &mut Vec<i32>, n: i32) -> bool {
        if node.is_none() {
            return false;
        }
        let current = node.as_ref().unwrap();
        if current.data == n {
            return true;
        }
        if Self::build(&current.left, list, n) || Self::build(&current.right, list, n) {
            list.push(current.data);
            return true;
        }
        false
    }
}

Ruby

class Solution
  def list_ancestors(root, n)
    result = []
    build(root, result, n)
    result
  end

  def build(node, list, n)
    return false if node.nil?
    return true if node.data == n
    if build(node.left, list, n) || build(node.right, list, n)
      list << node.data
      return true
    end
    false
  end
end

C#

using System.Collections.Generic;

public class Solution {
    public List<int> ListAncestors(TreeNode? root, int n) {
        var output = new List<int>();
        Build(root, output, n);
        return output;
    }

    private bool Build(TreeNode? node, List<int> list, int n) {
        if (node == null) return false;
        else if (node.data == n) return true;
        else if (Build(node.left, list, n) || Build(node.right, list, n)) {
            list.Add(node.data);
            return true;
        } else return false;
    }
}

Dart

class Solution {
  List<int> listAncestors(TreeNode? root, int n) {
    List<int> out = [];
    build(root, out, n);
    return out;
  }

  bool build(TreeNode? node, List<int> list, int n) {
    if (node == null) return false;
    else if (node.data == n) return true;
    else if (build(node.left, list, n) || build(node.right, list, n)) {
      list.add(node.data);
      return true;
    } else return false;
  }
}

PHP

class Solution {
    public function listAncestors(?TreeNode $root, int $n): array {
        $out = [];
        $this->build($root, $out, $n);
        return $out;
    }

    private function build(?TreeNode $node, array &$list, int $n): bool {
        if ($node === null) return false;
        elseif ($node->data === $n) return true;
        elseif ($this->build($node->left, $list, $n) || $this->build($node->right, $list, $n)) {
            $list[] = $node->data;
            return true;
        } else return false;
    }
}

Related Problems and Practice

Once you've nailed ancestor finding, these related problems build on the same recursive builder pattern:

• Lowest Common Ancestor: Find where two nodes' ancestor paths diverge
• Root-to-Leaf Path Sum: Check if any root-to-leaf path sums to a target
• Binary Tree Diameter: Use height calculations with backtracking
• Tree Path Finder: Return the actual path between two nodes

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. The spaced repetition system helps you internalize these patterns so they're second nature when interview day arrives.