Problem Statement

Determine the depth (or height) of a binary tree, which refers to the number of nodes along the longest path from the root node to the farthest leaf node. If the tree is empty, the depth is 0.

Example:

1. • Input

        1
       / \
      2   3
     / \
    4   5
   

   Output: 3
   Explanation: The longest path is 1->2->4 or 1->2->5 with 3 nodes.

2. • Input:

     1
      \
       2
        \
         3
     

   • Expected Output: 3
   • Justification: There's only one path 1->2->3 with 3 nodes.
3. • Input:

         1
        / \
       2   3
      / \
     4   7
          \
           9
     

   • Expected Output: 4
   • Justification: The longest path is 1->2->7->9 with 4 nodes.

Solution

What's the 'Depth'?

Picture a ladder. Each step is a level in our tree. The depth? It's just how many steps there are! If we have a 3-step ladder, our tree has a depth of 3.

Breaking Down the Approach:

1. Recursive Approach: The depth of a binary tree can be computed recursively. The maximum depth of a tree is the maximum of the depths of its left and right subtrees plus one (the root node).

2. Base Condition: If the node is null, return 0. This ensures that we've reached the end of a branch or the tree is empty.

3. Recursive Calculation: For each node, compute the depth of its left subtree and the depth of its right subtree. The depth of the current node is 1 + the maximum of these two depths.

4. Result: For the root node, this recursive approach will provide the maximum depth of the entire tree.

Algorithm Walkthrough:

Given Input:

    1
   / \
  2   3
 / 
4 

• Start with the root node which has value 1.
• The left subtree has a depth of:
  • 1 (for node 2) + max(depth of left subtree of node 2, depth of right subtree of node 2)
  • This is equal to 1 + 1 (for node 4) = 2.
• The right subtree of the root node has depth 1 (just node 3).
• So, the maximum depth of the tree is 1 (for the root node) + max(2, 1) = 3.

Code

Complexity Analysis

• Time Complexity: O(n) where n is the number of nodes in the tree, since we visit each node once.
• Space Complexity: O(h) where h is the height of the tree. This is because of the depth of the recursion stack, which is determined by the tree height.