Problem

Given a binary tree, determine the depth of a given node in the tree.

Definition

Height and Depth of a Node in Tree#Depth

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: Binary Tree = [1, 2, 3, null, 4], Node = 4  
Output: 2  
Explanation: The binary tree can be represented as:  
                 1  
                / \  
               2   3  
                \  
                 4  
              Node 4 is at depth 2 (edges from root: 1 -> 2 -> 4).

Example 2

1
2
3
4
5
6
7

Input: Binary Tree = [1, 2, 3, null, null], Node = 5  
Output: -1  
Explanation: The binary tree can be represented as:  
                 1  
                / \  
               2   3  
              Node 5 does not exist in the tree, so the result is -1.

Solution

Method 1 - Using DFS

To find the depth of a given node in the binary tree:

  1. Start from the root and traverse the tree using a recursive or iterative method.
  2. Check at each step whether the current node matches the target node.
  3. Keep track of the depth as you traverse down the tree.
  4. If the node is found, return the depth; otherwise, continue searching through left and right subtrees.
  5. If the entire tree is traversed and the node is not found, return -1.

Approach

  • Use recursion to explore the left and right subtrees.
  • Pass the current depth as an argument to keep track of how far we have traversed from the root.
  • If the target node is found, return the current depth.
  • If traversal completes and the target node is not found, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

    private static int dfsHelper(TreeNode node, int target, int currentDepth) {
        if (node == null) return -1; // Base case: Node is not found

        if (node.val == target) return currentDepth; // Target node found

        // Check left and right subtrees
        int left = dfsHelper(node.left, target, currentDepth + 1);
        if (left != -1) return left; // Found in left subtree

        int right = dfsHelper(node.right, target, currentDepth + 1);
        return right; // Found in right subtree or not found (-1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def findDepth(self, root, target):
        def dfs(node, current_depth):
            if not node:  # Base case: Node not found
                return -1

            if node.val == target:  # Target node found
                return current_depth

            # Search in left subtree
            left = dfs(node.left, current_depth + 1)
            if left != -1:  # Found in left subtree
                return left

            # Search in right subtree
            return dfs(node.right, current_depth + 1)

        return dfs(root, 0)

Complexity

  • ⏰ Time complexity: O(n), where n is the total number of nodes in the binary tree. We traverse each node once to compute the height.
  • 🧺 Space complexity: O(h). The recursion calls will use stack space proportional to the height of the tree (h), which is the depth of the recursion.