Jubin Soni - Portfolio & Blog

1. Introduction & Motivation

In the hierarchy of computer science data structures, few are as foundational or as versatile as the Binary Tree. Unlike linear structures like arrays or linked lists, Binary Trees allow us to represent hierarchical data—think of the folder structure on your hard drive, the Document Object Model (DOM) in your web browser, or the decision-making logic in high-frequency trading algorithms.

Learning to master trees is a rite of passage for every developer. It moves your problem-solving paradigm from simple iteration to complex recursion. Binary Trees solve the fundamental problem of balancing search efficiency with dynamic data management. For instance, in a well-balanced Binary Search Tree (BST), we can search, insert, or delete elements in $O(\log N)$ time, a massive improvement over the $O(N)$ time required for arrays.

In this article, you will learn the core properties of Binary Trees, explore different traversal strategies, and deep-dive into one of the most challenging tree-based interview questions: Binary Tree Maximum Path Sum. By the end, you'll have a robust mental model for tackling tree problems using DFS and recursive state management.

2. Core Concept & Theory

What is a Binary Tree?

A Binary Tree is a non-linear data structure where each node has at most two children, typically referred to as the left child and the right child.

Key Terminology

Root: The topmost node of the tree.
Leaf: A node with no children.
Height: The number of edges on the longest path from the root to a leaf.
Subtree: A tree consisting of a node and all its descendants.

When to Use Binary Trees

Binary Trees are ideal when your data is hierarchical or when you need to maintain a sorted dataset that changes frequently. However, they are NOT ideal when your data is strictly sequential or if you need constant-time ($O(1)$) access to elements by index, in which case a Hash Map or Array is superior.

Types of Traversals

To solve problems on trees, we must visit every node. There are four primary ways to do this:

Pre-order (Root-Left-Right): Used for creating a copy of the tree.
In-order (Left-Root-Right): In a BST, this returns values in sorted order.
Post-order (Left-Right-Root): Used for deleting trees or computing values from the bottom up (e.g., height).
Level-order (BFS): Visits nodes level by level using a queue.

Visual Representation

3. Problem Statement

Problem: Binary Tree Maximum Path Sum (LeetCode #124)

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Constraints:

The number of nodes in the tree is in the range $[1, 3 \times 10^4]$.
$-1000 \le Node.val \le 1000$

Example 1:

Input: root = [1, 2, 3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of $2 + 1 + 3 = 6$.

Example 2:

Input: root = [-10, 9, 20, null, null, 15, 7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of $15 + 20 + 7 = 42$.

4. Approach 1: Brute Force / Naive Solution

Intuition

The path sum can start and end anywhere. A naive approach would be to recognize that for every node in the tree, it could potentially be the "highest point" (the apex) of the maximum path. If a node is the apex, the path would consist of the node itself, plus the maximum possible path extending into its left subtree and the maximum possible path extending into its right subtree.

In a brute force approach, we could write a helper function getMaxGain(node) that calculates the maximum single-direction path starting from that node. Then, for every single node in the tree, we calculate node.val + getMaxGain(node.left) + getMaxGain(node.right).

Code Solution (Python)

python

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_sum = float('-inf')

        def get_max_gain(node):
            if not node: return 0
            # Recursively find the max gain from left and right children
            # We use max(0, ...) to ignore paths with negative sums
            left = max(0, get_max_gain(node.left))
            right = max(0, get_max_gain(node.right))
            return node.val + max(left, right)

        def traverse_all_nodes(node):
            if not node: return
            
            # For the current node, calculate the max path if it's the root of the path
            left_gain = max(0, get_max_gain(node.left))
            right_gain = max(0, get_max_gain(node.right))
            current_path_sum = node.val + left_gain + right_gain
            
            # Update global max
            self.max_sum = max(self.max_sum, current_path_sum)
            
            # Visit other nodes
            traverse_all_nodes(node.left)
            traverse_all_nodes(node.right)

        traverse_all_nodes(root)
        return self.max_sum

Complexity Analysis

Time Complexity: $O(N^2)$ in the worst case (a skewed tree). For every node $N$, we perform another traversal of its subtrees.
Space Complexity: $O(H)$ where $H$ is the height of the tree, due to the recursion stack.

Limitations

This approach is inefficient because it recomputes the "gain" for the same nodes multiple times. If we are at the root, we compute gains for its children. When we move to the children, we re-calculate those same gains.

5. Approach 2: Optimized Solution (Post-Order DFS)

Intuition

We can optimize the brute force by combining the two traversals. As we perform a single post-order traversal (visiting children first, then the parent), we can calculate the gain of each subtree and update the global maximum simultaneously.

Key Insight: At any node, we need to decide two things:

What is the maximum path sum that passes through this node and turns back down? (This is node.val + left_gain + right_gain). We use this to update our global maximum.
What is the maximum contribution this node can offer to its parent? (This is node.val + max(left_gain, right_gain)). This is what we return to the recursive caller.

Visual Walkthrough

Code Solution (Python)

python

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        # Initialize global maximum with a very small number
        self.max_path = float('-inf')

        def post_order_dfs(node):
            if not node:
                return 0
            
            # 1. Calculate max path sum starting from left and right children
            # If the sum is negative, we 'reset' it to 0 (ignore that branch)
            left_gain = max(post_order_dfs(node.left), 0)
            right_gain = max(post_order_dfs(node.right), 0)
            
            # 2. The price of the 'new' path would be node.val + left_gain + right_gain
            # This represents a path that 'peaks' at the current node
            current_max_path = node.val + left_gain + right_gain
            
            # 3. Update the global maximum if the current path is better
            self.max_path = max(self.max_path, current_max_path)
            
            # 4. Return the max gain the node can contribute to its parent
            # The parent can only pick ONE branch (left or right) to continue the path
            return node.val + max(left_gain, right_gain)

        post_order_dfs(root)
        return self.max_path

Complexity Analysis

Time Complexity: $O(N)$, where $N$ is the number of nodes. We visit each node exactly once.
Space Complexity: $O(H)$, where $H$ is the tree height. In the worst case (skewed tree), $H = N$. In a balanced tree, $H = \log N$.

6. Approach 3: Most Optimal / Advanced Solution (Iterative DFS)

While the recursive solution is typically accepted, in production environments with massive trees, recursion can lead to a StackOverflowError. An iterative approach using a stack simulates the recursion process manually.

Intuition

To mimic post-order traversal iteratively, we use a stack to keep track of nodes. We also need a way to know if we have already processed a node's children. We can use a hash map to store the returned "gain" values for each node.

Code Solution (Python)

python

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        
        max_path = float('-inf')
        # Map to store the max gain contribution of each node
        gains = {None: 0}
        
        # Use a stack for iterative post-order traversal
        stack = [(root, False)]
        
        while stack:
            node, visited = stack.pop()
            if not node: continue
            
            if visited:
                # Process the node after children are visited
                left_gain = max(gains[node.left], 0)
                right_gain = max(gains[node.right], 0)
                
                # Update global maximum
                max_path = max(max_path, node.val + left_gain + right_gain)
                
                # Store gain for parent to use
                gains[node] = node.val + max(left_gain, right_gain)
            else:
                # Standard iterative post-order: push node back, then children
                stack.append((node, True))
                stack.append((node.right, False))
                stack.append((node.left, False))
                
        return max_path

Complexity Analysis

Time Complexity: $O(N)$ - each node is pushed and popped from the stack twice.
Space Complexity: $O(N)$ - to store the gains dictionary and the stack.

7. Complexity Comparison Table

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute Force	$O(N^2)$	$O(H)$	Conceptually simple	Redundant calculations, very slow
Recursive DFS	$O(N)$	$O(H)$	Extremely clean, easy to read	Risk of Stack Overflow on deep trees
Iterative DFS	$O(N)$	$O(N)$	Safe for very deep trees	More complex code, higher constant space

8. Common Pitfalls & Edge Cases

Ignoring Negative Nodes: A common mistake is not initializing max_path to -inf. If all nodes are negative (e.g., [-3]), the answer should be -3, not 0.
Not ignoring negative branches: If a child's gain is negative, it's better to not include it at all. This is why we use max(gain, 0).
Returning the 'Peak' to Parent: In recursion, remember that you can only return the contribution of one branch to the parent. You cannot return node.val + left_gain + right_gain because a path cannot split and then rejoin.
Null Roots: Always check if the root is None at the start of your algorithm.

9. Practice Problem (Homework)

Practice Problem: Path Sum III (LeetCode #437)

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum. The path does not need to start at the root or end at a leaf, but it must go downwards.

Hint: This is a combination of Tree traversal and the "Prefix Sum" technique often used in arrays. Try using a Hash Map to store the frequencies of all prefix sums encountered so far in the current DFS path.

10. Related Problems & Further Practice

Lowest Common Ancestor of a Binary Tree (LeetCode #236) - Essential for understanding tree structure.
Binary Tree Zigzag Level Order Traversal (LeetCode #103) - Practice for BFS and deque usage.
Serialize and Deserialize Binary Tree (LeetCode #297) - Advanced hard problem on tree representation.
Diameter of Binary Tree (LeetCode #543) - A simpler version of the Maximum Path Sum logic.

Mastering Binary Trees: A Comprehensive Guide to Maximum Path Sum and Beyond

1. Introduction & Motivation

2. Core Concept & Theory

What is a Binary Tree?

Key Terminology

When to Use Binary Trees

Types of Traversals

Visual Representation

3. Problem Statement

Constraints:

Example 1:

Example 2:

4. Approach 1: Brute Force / Naive Solution

Intuition

Code Solution (Python)

Complexity Analysis

Limitations

5. Approach 2: Optimized Solution (Post-Order DFS)

Intuition

Visual Walkthrough

Code Solution (Python)

Complexity Analysis

6. Approach 3: Most Optimal / Advanced Solution (Iterative DFS)

Intuition

Code Solution (Python)

Complexity Analysis

7. Complexity Comparison Table

8. Common Pitfalls & Edge Cases

9. Practice Problem (Homework)

10. Related Problems & Further Practice

Further Reading & Resources