problemmediumalgorithmsget-the-height-of-a-node-in-a-binary-treeget the height of a node in a binary treegettheheightofanodeinabinarytree

Find the depth of a node in a binary tree

MediumUpdated: Aug 2, 2025

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](/cs/algorithms/tree/height-and-depth-of-a-node-in-tree.md/#depth)

Examples

Example 1

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

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

Java
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)
    }
}
Python
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.

Comments