Find distance from root to given node in binary tree

Problem

Find distance from root to a given node in a binary tree.

Examples

Example 1

graph TD;
    A[3] --> B[5]
    A[3] --> C[1]
    B[5] --> D[6]
    B[5] --> E[2]
    C[1] --> F[0]
    C[1] --> G[8]
    E[2] --> H[7]
    E[2] --> I[4]

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 4
Output: 3
Explanation: The path to node `4` is {3 -> 5 -> 2 -> 4}, which requires traversing 3 edges. Hence, the distance is 3.

Example 2

nput: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5
Output: 1
Explanation: The path to node `5` is {3 -> 5}, which requires traversing 1 edge. Hence, the distance is 1.`

Example 3

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 3
Output: 0
Explanation: The distance between a node and itself is 0.

Similar Problem

[[Find path from root to given node in a binary tree]]

Solution

Method 1 - DFS

Reasoning or Intuition

• The distance represents the depth of the tree node from the root.
• Begin at the root node and follow its children recursively in a depth-first manner. Check whether the current node matches the target value.
• Maintain a counter to track the depth level during traversal. For the target node, return the corresponding depth.

Approach

1. Recursive Traversal:
   • Implement a helper function for depth-first search (DFS).
   • Each recursive call increments a "current depth" counter.
   • If the target node is found, the depth counter is returned.
   • If the target node doesn't exist in the tree, return -1 (or user-defined value for non-existence).
2. Base Cases:
   • If the root is null, return -1.
   • If the current node matches the target value, return the current depth.

Code

Java

class Solution {
    public int findDistance(TreeNode root, int target) {
        return findDepth(root, target, 0);
    }

    private int findDepth(TreeNode node, int target, int depth) {
        if (node == null) {
            return -1; // Target not found
        }
        if (node.val == target) {
            return depth; // Target found
        }

        int left = findDepth(node.left, target, depth + 1);
        if (left != -1) {
            return left;
        }

        int right = findDepth(node.right, target, depth + 1);
        return right;
    }
}

Python

class Solution:
    def findDistance(self, root: TreeNode, target: int) -> int:
        def find_depth(node, target, depth):
            if not node:
                return -1  # Target not found
            if node.val == target:
                return depth  # Target found
            # Search left and right subtrees
            left = find_depth(node.left, target, depth + 1)
            if left != -1:
                return left
            right = find_depth(node.right, target, depth + 1)
            return right

        return find_depth(root, target, 0)

Complexity

• ⏰ Time complexity: O(n). The algorithm traverses each node exactly once in the worst-case scenario.
• 🧺 Space complexity: O(h). The space requirement is proportional to the height of the tree due to the recursive call stack.