Tree Properties: Height and Diameter

1. Calculating the Height (or Maximum Depth) of a Tree

One of the most fundamental properties of a tree is its height. This tells us how "tall" the tree is.

Definition: The height or maximum depth of a binary tree is the number of nodes along the longest path from the root node down to the farthest leaf node.

• An empty tree has a height of 0.
• A tree with only a root node has a height of 1.

We can solve this problem using the traversal techniques you've already learned. Let's explore the two most common approaches.

1.1 Recursive DFS Approach

The recursive approach is the most direct and elegant. The logic follows a postorder traversal pattern: to find the height of a tree, we must first find the heights of its left and right subtrees.

The core idea is:
height(node) = 1 + max(height(node.left), height(node.right))

The base case for the recursion is an empty tree (a None node), which has a height of 0.

Here is the Python code for this approach:

# Assume TreeNode class is defined
def maxDepth_recursive(root: TreeNode) -> int:
    # Base case: an empty tree has depth 0
    if not root:
        return 0

    # Recursively find the depth of left and right subtrees
    left_depth = maxDepth_recursive(root.left)
    right_depth = maxDepth_recursive(root.right)

    # The depth of the tree is 1 (for the current node) plus the max of the two subtrees
    return 1 + max(left_depth, right_depth)

This solution has a time complexity of $O(N)$ because it visits every node once. The space complexity is $O(H)$ where $H$ is the height of the tree, due to the recursion call stack.

1.2 Iterative BFS Approach

Remember how level-order traversal works? It explores the tree layer by layer. This gives us another very intuitive way to find the height: the height of the tree is simply the number of levels it has.

You can adapt the level-order traversal algorithm you learned in the last lesson. You just need to keep a count of the levels you process.

Here's the code, which should look very familiar:

from collections import deque

# Assume TreeNode class is defined
def maxDepth_iterative_bfs(root: TreeNode) -> int:
    if not root:
        return 0

    level = 0
    queue = deque([root])

    while queue:
        # Each iteration of the outer loop is one level
        level += 1
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return level

This solution also has a time complexity of $O(N)$. Its space complexity is $O(W)$, where $W$ is the maximum width of the tree, which in the worst case can be $O(N)$.

2. Finding the Diameter of a Binary Tree

The diameter is another key property, but it's a bit more complex than height.

Definition: The diameter of a binary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The length is typically measured by the number of edges.

The fact that the longest path might not pass through the root is the crucial insight needed to solve this problem correctly.

For any given node, the longest path that passes through it has a length equal to:
height(node.left) + height(node.right)
(Here, height is defined as the number of edges, which is depth - 1)

The diameter of the entire tree is the maximum of these path lengths calculated for every node in the tree.

A brute-force approach would be to iterate through every node, and for each node, calculate the height of its left and right subtrees. This would be inefficient, resulting in an $O(N^2)$ solution because you'd be recalculating heights repeatedly.

Can we do better? Yes, with a single DFS pass.

The Optimal Recursive DFS Solution

The trick is to realize that during a single postorder traversal to calculate height, we have all the information we need. For each node, as we return its height up to its parent, we can also calculate the diameter that passes through it (left_height + right_height) and update a global maximum.

So, our recursive function will do two things:

1. Return Value: It will return the height of the current subtree, which is needed by its parent node.
2. Side Effect: It will update a variable (e.g., a nonlocal or class-level variable) that tracks the maximum diameter found so far across the entire tree.

This is a powerful pattern in tree algorithms.

To reinforce this concept and see the code, let's look at a written resource.

Here is the implementation, which encapsulates this logic within a class, a common pattern in competitive programming platforms.

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        # Use a list or a simple variable with `nonlocal` to store the result.
        # A list is mutable, so it can be updated inside the nested function.
        max_diameter = [0]

        def dfs(node):
            # Base case: height of a null node is -1 so that a leaf node has height 0.
            # This corresponds to counting edges.
            if not node:
                return -1

            # Recursively find the height of left and right subtrees.
            left_height = dfs(node.left)
            right_height = dfs(node.right)

            # Calculate the diameter passing through the current node.
            # The number of edges is (left_height + 1) + (right_height + 1)
            current_diameter = left_height + right_height + 2
            
            # Update the maximum diameter found so far.
            max_diameter[0] = max(max_diameter[0], current_diameter)

            # Return the height of the subtree rooted at the current node.
            # Height is 1 + max height of children.
            return 1 + max(left_height, right_height)

        # Start the DFS traversal from the root.
        dfs(root)
        
        return max_diameter[0]

The resource "Diameter of Binary Tree" also has an excellent "Common Pitfalls" section. The most common mistake is to have the recursive function return the diameter instead of the height, which breaks the logic for nodes higher up in the tree. Always remember: the function returns height to its parent but updates a global/nonlocal diameter.

Conclusion

Congratulations! You've now learned how to apply your knowledge of tree traversals to calculate two of the most important structural properties of a binary tree.

Key Takeaways:

• Tree Height/Depth can be found efficiently using either a recursive DFS (postorder) or an iterative BFS (level-order) approach, both in $O(N)$ time.
• Tree Diameter is the longest path between any two nodes and may not pass through the root.
• The optimal solution for diameter uses a single DFS (postorder) traversal. The recursive helper function cleverly returns the height of the subtree while simultaneously updating a global/nonlocal variable with the maximum diameter found so far.

These problems are not just academic exercises; they are templates for a wide range of other tree problems where you need to gather information from subtrees to compute a result for the whole tree.

Up Next:
In our final lesson of this module, we will tackle another classic and crucial problem: finding the lowest common ancestor (LCA) of two nodes in a binary tree. The recursive thinking you've honed today will be directly applicable.