Find the height of a node in a binary tree

Problem

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

Definition

[Height and Depth of a Node in Tree#Height](/cs/algorithms/tree/height-and-depth-of-a-node-in-tree.md/#height)

Examples

Example 1

Input:
Binary Tree: 
         1
        / \
       2   3
      / \
     4   5
Node: 2
 
Output:
2

Explanation:
The subtree rooted at node 2 has two levels (edges from 2 to 4 and from 4 to 5). The longest path from node 2 to a leaf consists of 2 edges.

Example 2

Input:
Binary Tree:
         1
        / \
       2   3
Node: 1
 
Output:
2

Explanation:
The longest path from node 1 to a leaf passes through node 2 and ends at node 4 or node 5, both of which are on level 2.

Example 3

Input:
Binary Tree: 
         1
        / \
       2   3
      /
     4
Node: 1
 
Output:
2
 
Explanation:
The longest path from node 1 to a leaf passes through node 2 and ends at node 4. In this case, there are two edges from node 1 to node 4, so the height is 2.

Solution

Method 1 - Using DFS

The height of a node in a binary tree can be calculated recursively:

• If the node is a leaf (no children), its height is 0.
• Else, the height of the node is 1 + max(height of left child, height of right child).

This recursive relation allows us to break the problem into smaller subproblems where the height of a node is determined based on the height of its children.

Approach

1. Define the Recursive Function: Create a function to compute the height of a given node.
2. Base Case: If the current node is null, return -1 since there's no path.
3. Recursive Case: Compute the height of the left and right subtrees and return 1 + max(leftHeight, rightHeight).

Code

Java

class Solution {
    // Method to calculate height of a given node
    public int findHeight(TreeNode node) {
        // Base case: if node is null, return -1
        if (node == null) {
            return -1;
        }
        // Recursive case: compute left and right subtree heights
        int leftHeight = findHeight(node.left);
        int rightHeight = findHeight(node.right);

        // Height of current node = 1 + max(leftHeight, rightHeight)
        return 1 + Math.max(leftHeight, rightHeight);
    }

    // Example usage
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        Solution solution = new Solution();
        System.out.println(solution.findHeight(root.left));  // Output: 2
        System.out.println(solution.findHeight(root.right)); // Output: 0
        System.out.println(solution.findHeight(root));       // Output: 2
    }
}

Python

class Solution:
    def findHeight(self, node):
        # Base case: if the node is None, return -1
        if not node:
            return -1
        
        # Recursive case: calculate height of left and right subtree
        left_height = self.findHeight(node.left)
        right_height = self.findHeight(node.right)
        
        # Height of the current node = 1 + max(left_height, right_height)
        return 1 + max(left_height, right_height)

# Example usage
if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)

    solution = Solution()
    print(solution.findHeight(root.left))  # Output: 2
    print(solution.findHeight(root.right)) # Output: 0
    print(solution.findHeight(root))       # Output: 2

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.