Distance of a node from the root of a binary tree

You're in a Facebook phone screen and the interviewer asks you to find how far a particular node is from the root of a binary tree. Sounds straightforward, right? But the tree could be unbalanced, the target could be buried deep on one side, and you need to handle dead-end paths gracefully. This problem, also known as "Find Node Distance from Root in Binary Tree" on other platforms, is a staple DFS exercise that tests your recursive thinking and your ability to handle edge cases cleanly.

TL;DR

Use a recursive DFS helper that carries a step counter starting at 1. If the current node is null, return Integer.MAX_VALUE (dead end). If it matches the target, return the step count. Otherwise, recurse into both subtrees and return the minimum. This runs in O(n) time and O(n) space in the worst case.

Why This Problem Matters

Finding the distance from the root to a target node is one of the building blocks of tree algorithms. It appears directly in interviews at companies like Facebook and TripAdvisor, and the pattern behind it - recursive DFS with a running counter - transfers to dozens of other problems: finding the diameter, computing the lowest common ancestor, and determining the depth of the deepest node. Get this one right and you'll have a template you can reuse over and over.

Binary Trees: Quick Refresher

A binary tree is a hierarchical structure where every node has at most two children. Here is the example tree from the problem:

Key terminology:

• Root: The top node (node 1 in our tree)
• Leaf: A node with no children (nodes 4, 5, and 6)
• Distance: The number of nodes on the path from root to target, including both endpoints

Understanding the Problem

Given: The root of a binary tree and a target integer. Find: The minimum number of nodes on the path from the root to a node whose data equals the target. Guarantee: At least one node with the target value exists.

Let's look at two examples using our tree:

nodeDistance(root, 6) returns 3 - the path is 1, 3, 6.

nodeDistance(root, 2) returns 2 - the path is 1, 2.

Notice that the distance includes both the starting node (root) and the target node itself. This is different from some definitions that count edges instead of nodes.

Edge Cases

1. Target is the root: Distance is 1
2. Single-node tree: If that node matches the target, distance is 1
3. Target appears in both subtrees: Return the minimum distance (closest occurrence)
4. Skewed tree: Target might be at the very bottom, requiring a full traversal

Solution Approach

The recursive insight here is similar to finding the height of a tree: ask each subtree for its answer, then combine.

For each node, we carry a step counter that tracks how many nodes deep we are from the root (starting at 1). Three things can happen:

1. Null node: We've gone past a leaf without finding the target. Return Integer.MAX_VALUE to signal "not found down this path."
2. Match: The current node's data equals the target. Return the current step.
3. No match yet: Recurse into both children with step + 1, and return whichever side gives the smaller result.

The use of Integer.MAX_VALUE is a clean trick: since we're taking Math.min of the two subtree results, any valid distance will always beat MAX_VALUE. No special-case if statements needed.

Here is how every node in our example tree maps to its distance from the root:

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

Implementation

public class Solution {
  public int nodeDistance(TreeNode root, int target) {
    // Start the DFS with step = 1 (root counts as distance 1)
    return dfsDistance(root, target, 1);
  }

  private int dfsDistance(TreeNode node, int target, int step) {
    // Dead end: no node here
    if (node == null) return Integer.MAX_VALUE;

    // Found the target
    if (node.data == target) return step;

    // Search both subtrees, return the closer match
    return Math.min(
        dfsDistance(node.left, target, step + 1),
        dfsDistance(node.right, target, step + 1)
    );
  }
}

Let's trace through nodeDistance(root, 6) on our example tree:

The recursion visits the left subtree first, finds no match (all paths return MAX_VALUE), then visits the right subtree where node 6 is found at step 3. The min operations bubble the result back up to the root.

Complexity Analysis

Time Complexity: O(n)

Every node is visited at most once. In the worst case, the target is the last node explored, so all n nodes are checked. Each node does constant work: one comparison plus two recursive calls.

Space Complexity: O(n)

The space is dominated by the recursion call stack. For a balanced tree, the maximum recursion depth is O(log n). For a completely skewed tree (all nodes on one side), the depth is O(n). Since the problem states the tree can have up to 10,000 nodes, a skewed tree would use that much stack space.

Could We Do Better?

If we only need the distance to one target, O(n) time is optimal since we might need to examine every node. However, BFS (level-order traversal) would find the target the moment it reaches its level, potentially visiting fewer nodes if the target is near the top. The worst case is still O(n), but the average case can be better for shallow targets.

Common Pitfalls

1. Using -1 instead of MAX_VALUE for null nodes: If you return -1, the Math.min call will pick -1 over any valid distance, giving you a wrong answer. Either use MAX_VALUE or add explicit null checks before the min call.

2. Starting step at 0 instead of 1: The problem defines distance as including both endpoints. Starting at 0 would give you the edge count, which is off by one.

3. Only searching one subtree: If you return early when you find the target in the left subtree without checking the right, you might miss a closer occurrence. Always search both sides and take the minimum.

4. Integer overflow when adding to MAX_VALUE: In theory, step + 1 on a MAX_VALUE return could overflow. In practice this doesn't happen because we never add to a returned MAX_VALUE - we only pass it through Math.min. But it's worth mentioning if your interviewer probes edge cases.

Interview Tips

When you get this problem in an interview:

1. Clarify the distance definition: "Does distance count nodes or edges? Is the root at distance 0 or 1?" This shows attention to detail.

2. Mention the MAX_VALUE trick early: Explain why you chose it over -1 or a boolean flag. Interviewers appreciate clean design choices.

3. Draw the recursion: Sketch the tree, pick a target, and trace through two or three nodes. Show how MAX_VALUE propagates up from null children and how the real distance bubbles up from the match.

4. Discuss BFS as an alternative: "BFS would also work and might find shallow targets faster, but the worst case is the same. I'm choosing DFS because it leads to cleaner recursive code."

5. Prepare for follow-ups:

   • "What if you needed the distance between two arbitrary nodes?" (Find LCA, then sum distances)
   • "What if the tree were a BST?" (You could prune one subtree at each step)
   • "Return the path, not just the distance." (Collect nodes in a list during recursion)

Key Takeaways

• A recursive DFS with a step counter is the standard approach for finding node distance from the root. Start at step 1, increment on each recursive call, and return the step when the target is found.
• Returning Integer.MAX_VALUE for null nodes lets you use Math.min directly without conditional branching, keeping the code concise and less error-prone.
• Time complexity is O(n) because every node might need to be visited. Space complexity is O(n) worst case due to the call stack on a skewed tree, O(log n) for a balanced tree.
• This "DFS with running state" pattern is the foundation for many tree problems: diameter, path sums, LCA, and more. Internalizing it pays dividends across your entire interview prep.
• Always clarify whether distance counts nodes or edges. Off-by-one errors from wrong assumptions are one of the most common ways candidates lose points on tree problems.

Practice and Related Problems

Once you have this pattern down, challenge yourself with these related problems that build on the same recursive DFS approach:

• Height of a binary tree - Same structure, but you're maximizing instead of searching for a target
• Lowest common ancestor - Find the LCA, then compute distances from it
• Diameter of a binary tree - Combine left and right heights at each node
• Root-to-leaf path sum - Carry a running sum instead of a step counter

Consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you're just starting or preparing for your dream job at a FAANG company, mastering tree traversal fundamentals like this will set you up for success.

Solutions in Other Languages

Python

class Solution:
    def node_distance(self, root, target):
        return self.dfs_distance(root, target, 1)

    def dfs_distance(self, node, target, step):
        if node is None:
            return 10001
        if node.data == target:
            return step
        return min(
            self.dfs_distance(node.left, target, step + 1),
            self.dfs_distance(node.right, target, step + 1)
        )

Python uses 10001 as the sentinel since node values are capped at 10,000, guaranteeing any valid distance is smaller.

JavaScript

class Solution {
  nodeDistance(root, target) {
    return this.dfsDistance(root, target, 1);
  }

  dfsDistance(node, target, step) {
    if (node === null) return Number.POSITIVE_INFINITY;
    if (node.data === target) return step;
    return Math.min(
      this.dfsDistance(node.left, target, step + 1),
      this.dfsDistance(node.right, target, step + 1)
    );
  }
}

TypeScript

class Solution {
  nodeDistance(root: TreeNode | null, target: number): number {
    return this.dfsDistance(root, target, 1);
  }

  dfsDistance(node: TreeNode | null, target: number, step: number): number {
    if (node === null) return Number.POSITIVE_INFINITY;
    if (node.data === target) return step;
    return Math.min(
      this.dfsDistance(node.left, target, step + 1),
      this.dfsDistance(node.right, target, step + 1)
    );
  }
}

C++

class Solution {
public:
  int nodeDistance(TreeNode *root, int target) {
    return dfsDistance(root, target, 1);
  }

private:
  int dfsDistance(TreeNode *node, int target, int step) {
    if (node == nullptr) return INT_MAX;
    if (node->data == target) return step;
    return std::min(
      dfsDistance(node->left, target, step + 1),
      dfsDistance(node->right, target, step + 1)
    );
  }
};

Go

func (s *Solution) NodeDistance(root *TreeNode, target int) int {
    return dfsDistance(root, target, 1)
}

func dfsDistance(node *TreeNode, target int, step int) int {
    if node == nil {
        return math.MaxInt32
    }
    if node.Data == target {
        return step
    }
    left := dfsDistance(node.Left, target, step+1)
    right := dfsDistance(node.Right, target, step+1)
    if left < right {
        return left
    }
    return right
}

Scala

class Solution {
  def nodeDistance(root: TreeNode, target: Int): Int = {
    dfsDistance(root, target, 1)
  }

  private def dfsDistance(node: TreeNode, target: Int, step: Int): Int = {
    if (node == null) Int.MaxValue
    else if (node.data == target) step
    else Math.min(
      dfsDistance(node.left, target, step + 1),
      dfsDistance(node.right, target, step + 1)
    )
  }
}

Kotlin

class Solution {
    fun nodeDistance(root: TreeNode?, target: Int): Int {
        return dfsDistance(root, target, 1)
    }

    private fun dfsDistance(node: TreeNode?, target: Int, step: Int): Int {
        if (node == null) return Int.MAX_VALUE
        if (node.data == target) return step
        return minOf(
            dfsDistance(node.left, target, step + 1),
            dfsDistance(node.right, target, step + 1)
        )
    }
}

Swift

class Solution {
    func nodeDistance(_ root: TreeNode?, _ target: Int) -> Int {
        return dfsDistance(root, target, 1)
    }

    private func dfsDistance(_ node: TreeNode?, _ target: Int, _ step: Int) -> Int {
        if node == nil { return Int.max }
        if node!.data == target { return step }
        return min(
            dfsDistance(node!.left, target, step + 1),
            dfsDistance(node!.right, target, step + 1)
        )
    }
}

Ruby

class Solution
  def node_distance(root, target)
    dfs_distance(root, target, 1)
  end

  def dfs_distance(node, target, step)
    return Float::INFINITY if node.nil?
    return step if node.data == target
    [dfs_distance(node.left, target, step + 1),
     dfs_distance(node.right, target, step + 1)].min
  end
end

Rust

impl Solution {
    pub fn node_distance(&self, root: Option<Box<TreeNode>>, target: i32) -> i32 {
        Self::dfs_distance(&root, target, 1)
    }

    fn dfs_distance(node: &Option<Box<TreeNode>>, target: i32, step: i32) -> i32 {
        match node {
            None => i32::MAX,
            Some(current) => {
                if current.data == target {
                    return step;
                }
                std::cmp::min(
                    Self::dfs_distance(&current.left, target, step + 1),
                    Self::dfs_distance(&current.right, target, step + 1),
                )
            }
        }
    }
}

C#

public class Solution {
    public int NodeDistance(TreeNode? root, int target) {
        return DfsDistance(root, target, 1);
    }

    private int DfsDistance(TreeNode? node, int target, int step) {
        if (node == null) return int.MaxValue;
        if (node.data == target) return step;
        return Math.Min(
            DfsDistance(node.left, target, step + 1),
            DfsDistance(node.right, target, step + 1)
        );
    }
}

Dart

class Solution {
  int nodeDistance(TreeNode? root, int target) {
    return _dfsDistance(root, target, 1);
  }

  int _dfsDistance(TreeNode? node, int target, int step) {
    if (node == null) return 1 << 62;
    if (node.data == target) return step;
    return min(
      _dfsDistance(node.left, target, step + 1),
      _dfsDistance(node.right, target, step + 1),
    );
  }
}

PHP

class Solution {
    public function nodeDistance(?TreeNode $root, int $target): int {
        return $this->dfsDistance($root, $target, 1);
    }

    private function dfsDistance(?TreeNode $node, int $target, int $step): int {
        if ($node === null) return PHP_INT_MAX;
        if ($node->data === $target) return $step;
        return min(
            $this->dfsDistance($node->left, $target, $step + 1),
            $this->dfsDistance($node->right, $target, $step + 1)
        );
    }
}