2773. Height of Special Binary Tree - Detailed Explanation

Problem Statement

You are given the root of a special binary tree. In this special tree, every non-leaf node has exactly two children. Your task is to compute the height of this tree. The height is defined as the number of nodes along the longest path from the root down to a leaf node.

Consider the following examples:

Example 1

• Input: A tree with a single node

      1
  

• Output: 1
• Explanation: The tree only contains the root, so the height is 1.

Example 2

• Input:

        1
       / \
      2   3
  

• Output: 2
• Explanation: The longest path is from the root (1) to either leaf (2 or 3), which consists of 2 nodes.

Example 3

• Input:

          1
         / \
        2   3
       /
      4
  

• Output: 3
• Explanation: The longest path is 1 → 2 → 4, totaling 3 nodes.

Hints

1. Recursive Insight:
   Think of computing the height of the tree recursively. For any given node, the height is 1 plus the maximum height of its left and right subtrees.

2. Base Case Consideration:
   When you reach a leaf node (or an empty node), the height should be defined appropriately. For an empty subtree, you can return 0, and for a leaf node, return 1.

Approaches

Approach 1: Recursive Depth-First Search (DFS)

Explanation

1. Base Case:
   If the current node is null (or None in Python), return 0. This accounts for the scenario when you have an empty tree or you’ve reached beyond a leaf node.

2. Recursive Case:

   • Recursively call the function for both the left and right children.
   • The height of the current node is 1 + max(left_subtree_height, right_subtree_height).
   • For a special binary tree, every non-leaf node has two children, so both recursive calls will be made (unless you are at a leaf).

Walkthrough with Example

For Example 3:

• Start at root (node with value 1).
• Compute height of left subtree (rooted at 2) and right subtree (rooted at 3).
• For node 2:
  • Its left subtree is rooted at node 4, which is a leaf, so height is 1.
  • Its right subtree is null, so height is 0.
  • Height at node 2 becomes 1 + max(1, 0) = 2.
• For node 3:
  • Both children are null, so height is 1 + max(0, 0) = 1.
• Height at root (node 1) becomes 1 + max(2, 1) = 3.

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes. Every node is visited exactly once.
• Space Complexity: O(h), where h is the height of the tree. This is the space used by the recursion call stack. In the worst case (a skewed tree), this could be O(n).

Approach 2: Iterative Level-Order Traversal (Breadth-First Search, BFS)

Explanation

1. Use a Queue for BFS:
   With level-order traversal, process the tree level by level.

2. Count Levels:
   Start by enqueueing the root node and then process nodes level by level. The number of levels you process equals the height of the tree.

3. Iteration:
   For every level, iterate over the nodes currently in the queue; for each node, add its non-null children to the queue. Once a level is fully processed, increment the height counter.

Walkthrough with Example

For Example 3:

• Level 1:
  Queue initially contains node 1. Process node 1 and enqueue nodes 2 and 3. Height becomes 1.
• Level 2:
  Queue contains nodes 2 and 3. Process node 2 (enqueue node 4) and node 3 (both children are null). Height becomes 2.
• Level 3:
  Queue now has node 4. Process node 4 (it is a leaf, so no children are enqueued). Height becomes 3.
• There are no more nodes to process; hence, the tree height is 3.

Complexity Analysis

• Time Complexity: O(n), since every node is processed once.
• Space Complexity: O(w), where w is the maximum number of nodes at any level. In the worst-case scenario (balanced tree), this is O(n).

Code Solutions

Python Implementation (Recursive DFS)

Java Implementation (Recursive DFS)