Solving Tree Problems: Height, Diameter, and Maximum Path Sum

Concept 1: Measuring Tree Height (Maximum Depth)

The most fundamental measurement of a tree is its height or depth. This concept is the building block for the more complex problems that follow.

Technical Explanation

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.

• The height of an empty tree is 0.
• The height of a tree with a single node is 1.
• For any other node, its height is 1 (for the node itself) plus the height of its tallest subtree.

This definition lends itself perfectly to a recursive solution:

We simply ask the left and right children for their heights, take the greater of the two, and add one for the current node. This is a classic post-order traversal pattern (process children, then process the node).

To see this in action, along with alternative iterative approaches, let's turn to a clear visual explanation.

Metaphor: Finding the Deepest Root of a Plant

Imagine you're an analyst for a botany-themed startup, "Rootify." You need to find the maximum depth of a plant's root system. You can't see the whole system at once.

The recursive approach is to tell your two primary sub-roots: "Tell me your maximum depth." They, in turn, ask the same of their sub-roots, and so on. When a tiny rootlet hits the end (null), it reports a depth of 0. As the answers come back up, each root junction takes the maximum depth reported by its children and adds 1 (for itself) before reporting back to its parent. Eventually, the main root gets the two final numbers and calculates the total depth.

Python Code Snippet: Recursive and Iterative (BFS) Solutions

Here are the two most common and important ways to implement this.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Approach 1: Recursive DFS (Most elegant)
def maxDepth_recursive(root: TreeNode) -> int:
    if not root:
        return 0
    
    left_height = maxDepth_recursive(root.left)
    right_height = maxDepth_recursive(root.right)
    
    return 1 + max(left_height, right_height)

# Approach 2: Iterative BFS (Level-by-Level)
from collections import deque

def maxDepth_bfs(root: TreeNode) -> int:
    if not root:
        return 0
    
    level = 0
    q = deque([root])
    
    while q:
        # Process all nodes at the current level
        for i in range(len(q)):
            node = q.popleft()
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        
        # Increment level after processing all nodes at the current depth
        level += 1
        
    return level

The time complexity for both is $O(N)$ as we visit every node once. The space complexity is $O(H)$ for the recursive solution due to the call stack, and $O(W)$ for the BFS solution, where $H$ is the tree height and $W$ is the maximum width of the tree.

Concept 2: Defining and Solving for Tree Diameter

With height under our belts, we can tackle a more interesting problem: the diameter. This is a common interview question that builds directly on the height calculation.

Technical Explanation

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.

Here's the critical insight: for any node, the longest path that passes through it as the highest point (or "pivot") is the sum of the heights of its left and right subtrees.

The overall tree's diameter is the maximum of these values calculated for every node in the tree.

A naive, brute-force approach would be:

1. Traverse every node in the tree.
2. For each node, calculate the height of its left subtree and its right subtree.
3. Sum them to find the diameter at that node.
4. Keep track of the maximum diameter found.

This would work, but since calculating height is an $O(N)$ operation, doing it for every node results in an $O(N^2)$ algorithm. We can do much better.

The Optimized Approach: Single-Pass DFS

The key to an $O(N)$ solution is to realize we can compute heights and check for the diameter in the same recursive pass. This introduces a powerful pattern: a recursive function that returns one value (for its parent's calculation) while updating a global state (the final answer).

Here, our DFS function for any given node will:

1. Return: The height of the subtree rooted at that node. The parent node needs this value to compute its own height.
2. Update: A global (or nonlocal) variable max_diameter with left_height + right_height if it's a new maximum.

Metaphor: The "Most Remote Offices" Problem

Imagine you're designing the network for Google's global offices, which are structured like a tree. You need to find the two offices with the highest network latency between them (the diameter).

The $O(N^2)$ way is for the team at each office (node) to ping every other office to find its farthest partner, then compare results. This is slow.

The optimized $O(N)$ way is for a single engineer to travel the network (DFS). At each office, they ask their sub-networks for a report. The sub-networks report back two things:

1. "My most distant internal office is X milliseconds away from me (my height)."
2. "By the way, the longest path I found entirely within my sub-network was Y milliseconds (an internal diameter)."

The engineer uses the "height" (X) from the left and right sub-networks to calculate the diameter passing through the current office. They compare this to their running "max diameter found so far" and update it if needed. Then, they report their own height up to their manager. This single traversal finds the answer efficiently.

Python Code Snippet: Optimized Diameter Calculation

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        # We use a list to hold the max_diameter so it's mutable 
        # and can be modified by the nested function.
        max_diameter = [0] 

        def dfs(node: TreeNode) -> int:
            """
            This function does two things:
            1. Returns the height of the subtree rooted at `node`.
            2. Updates `max_diameter[0]` if a longer path is found.
            """
            if not node:
                return 0 # Height of a null tree is 0 (in terms of edges)

            # Recursively find the height of left and right subtrees
            left_height = dfs(node.left)
            right_height = dfs(node.right)
            
            # Update the max diameter found so far.
            # The diameter at this node is the sum of heights of its children.
            current_diameter = left_height + right_height
            max_diameter[0] = max(max_diameter[0], current_diameter)
            
            # Return the height of the current subtree to the parent
            return 1 + max(left_height, right_height)

        dfs(root)
        return max_diameter[0]

Note: The problem on LeetCode defines diameter as the number of edges, which is why the base case returns 0 and not -1. If defined by nodes, the logic would be slightly different.

Concept 3: Binary Tree Maximum Path Sum

This problem is a more complex variation of the diameter problem. It's considered a "Hard" problem on LeetCode and is an excellent test of your recursive thinking.

Technical Explanation

You are given a binary tree where each node has an integer value (which can be positive, negative, or zero). You need to find the maximum path sum. A path is a sequence of connected nodes, and a node can appear at most once. The path does not need to pass through the root.

This problem is similar to the diameter problem because for any node, it could be the "pivot" or highest point of the maximal path. However, there are two key differences:

1. Values matter: We are summing node values, not just counting nodes/edges.
2. Negative values: A subtree might have a negative maximum path sum. In this case, we are better off not including that subtree in our path. We can simply treat its contribution as 0.

To get a firm grasp of the problem, read through the following explanation.

Metaphor: The Most Profitable Road Trip

You're given a map of cities (nodes), and each city offers a certain profit or loss (the node's value). Roads connect the cities. You need to plan a continuous road trip (a path) that maximizes your total profit.

You can start in any city and end in any city. At any junction (node), you might have a path coming from your left, going through the current city, and continuing to your right. This would be a complete trip that "pivots" at that city.

However, if you're just passing through a city as part of a larger trip towards your parent city, you can't go both left and right. You must pick the more profitable of the two branches to continue your journey upwards. And if a whole region of cities (a subtree) would result in a net loss, you'd just skip it entirely.

Concept 4: The "Max Gain" Recursive Pattern

The solution to the Maximum Path Sum problem uses a refined version of the recursive pattern from the diameter problem.

Technical Explanation

We will design a recursive helper function, let's call it max_gain(node), that performs two critical tasks:

1. Calculates & Updates Global Maximum: It calculates the maximum path sum that has the node as its pivot. This path can include the node's value, the max gain from the left subtree, and the max gain from the right subtree.

   $$\text{path\_at\_node}=\text{node.val}+\text{left\_gain}+\text{right\_gain}$$

   It then updates a global max_sum variable with this value if it's a new maximum.

2. Returns "Max Gain" to Parent: It returns the maximum gain this node can contribute to a path that continues upwards to its parent. A path can't fork, so it can only include one of the children's subtrees.

   $$\text{return\_value}=\text{node.val}+\max (\text{left\_gain},\text{right\_gain})$$

The term "gain" is used because we apply max(0, ...) to the recursive calls. This elegantly handles the case of negative-sum subtrees: if a subtree's best path provides negative gain, we simply don't include it (gain = 0).

Let's dive into the specifics of the implementation.

Python Code Snippet: Max Path Sum

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        # Use a list for mutability, initialized to a very small number
        max_sum = [float('-inf')]

        def max_gain(node: TreeNode) -> int:
            """
            Returns the maximum gain from a path starting at `node` and going down.
            Updates the global `max_sum` along the way.
            """
            if not node:
                return 0

            # Recursively get max gain from children. 
            # Use max(0, ...) to discard negative paths.
            left_gain = max(0, max_gain(node.left))
            right_gain = max(0, max_gain(node.right))
            
            # 1. Calculate the max path with the current node as the "pivot".
            # This is a candidate for the final answer.
            current_max_path = node.val + left_gain + right_gain
            
            # Update the global maximum if needed.
            max_sum[0] = max(max_sum[0], current_max_path)
            
            # 2. Return the max gain this node can contribute to its parent.
            # A path can't go both left and right and then up to the parent.
            return node.val + max(left_gain, right_gain)

        max_gain(root)
        return max_sum[0]

Concept 5: Synthesis and Interview Perspectives

The three problems we've covered—height, diameter, and max path sum—are not just standalone puzzles. They represent a family of problems solved by a similar recursive pattern. Recognizing this pattern is what separates a good candidate from a great one.

The Unifying Pattern: Post-Order Traversal with Side Effects

At their core, all three solutions use a post-order traversal (left -> right -> node). In each recursive call, you gather results from your children before processing the current node.

The key variation is in what the function does at the node step:

• Height: The simplest case. It only performs one job: return 1 + max(left_result, right_result).
• Diameter & Max Path Sum: These are more advanced. The function has a dual responsibility:
  1. Update Global Answer: It uses both left_result and right_result to compute a "path through the current node" and checks if this is a new global maximum.
  2. Return Value for Parent: It returns a value computed using max(left_result, right_result) because a path continuing upwards cannot use both children.

Understanding this dual-purpose function design is crucial. When an interviewer presents a novel tree problem, you should be thinking: "What information do I need from my children?" and "What information does my parent need from me?" and "Is there a global answer I need to update along the way?"

Conclusion

Congratulations on working through some challenging but fundamental tree algorithms. You've moved beyond simple traversals to computing complex properties of trees, a skill essential for tackling advanced algorithm and system design problems.

Key Takeaways:

• Height is Fundamental: Calculating tree height is a basic post-order recursion and a building block for other problems.
• Diameter's Insight: The longest path might not involve the root. The solution requires checking the diameter at every node, which can be optimized into a single DFS pass.
• Max Path Sum's Nuance: This problem adds the complexity of node values and negative weights, requiring you to selectively ignore paths with negative "gain".
• The Dual-Purpose DFS Pattern: The key to solving diameter and max path sum efficiently is a recursive function that updates a global answer while returning a local value for its parent. This is a powerful and reusable pattern.

Preview of the Next Lesson

We've focused heavily on the recursive nature of trees. Our next lesson will introduce a data structure that combines the best of trees with priority-based ordering: the binary heap. We will learn how to implement a binary heap (priority queue) and apply it to problems like finding the 'Kth' largest element. This will be your first step into priority queues, a cornerstone of many efficient algorithms.