Hard Tree Problems

[!NOTE] This module explores the core principles of Tree Practice Problems, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

These problems require a shift in thinking: you often need to calculate one thing (e.g., height) to compute the answer (e.g., diameter), but return something else up the recursion stack.

1. Diameter of Binary Tree

Problem: Given the root of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them.

Examples:

Input: root = [1,2,3,4,5] -> Output: 3 (Path: 4->2->1->3 or 5->2->1->3)
Input: root = [1,2] -> Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100

Edge Cases & Clarifying Questions

Q: Can the tree be a single node? A: Yes. The diameter is 0 because there are 0 edges.
Q: Does the longest path have to pass through the root? A: No. It could be completely contained within the left or right subtree.
Edge Case: Skewed tree (all left or all right children). The diameter is simply the depth minus 1.

Intuition (The “Genesis”)

Brute Force Approach: For every node in the tree, calculate the maximum depth of its left and right subtrees. The diameter passing through that node would be depth(left) + depth(right). Doing this for all nodes takes O(N2) time because depth() is called repeatedly.

Optimized Approach (Post-order Traversal): We can optimize this to O(N) by calculating the diameter while computing the height. For any node N, the longest path passing through N is Height(Left) + Height(Right). The global “Diameter” is the maximum of this value found at any node in the tree.

Pattern explicitly: Post-order Traversal (Bottom-Up DFS). We need information from the children (heights) to compute the current node’s diameter, and then we return the current node’s height to its parent.

Common Pitfalls:

Confusing nodes vs edges. The problem asks for the number of edges, which is nodes - 1. Summing Height(Left) + Height(Right) directly gives the number of edges if height is defined as the number of nodes in the longest path.
Forgetting to update the global maximum during the recursive calls.

Interactive Analysis

Visualize the path calculation. The “Diameter” passing through the highlighted node is the sum of its left and right heights.

Tree Ready.

Max Diameter: 0

Solutions

Java

class Solution {
  int maxDiameter = 0;

  public int diameterOfBinaryTree(TreeNode root) {
    height(root);
    return maxDiameter;
  }

  private int height(TreeNode node) {
    if (node == null) return 0;

    int left = height(node.left);
    int right = height(node.right);

    // Update global max (edges = L + R)
    maxDiameter = Math.max(maxDiameter, left + right);

    // Return height to parent
    return Math.max(left, right) + 1;
  }
}

Go

func diameterOfBinaryTree(root *TreeNode) int {
  maxD := 0
  var height func(*TreeNode) int
  height = func(node *TreeNode) int {
    if node == nil { return 0 }
    left := height(node.Left)
    right := height(node.Right)

    if left + right > maxD {
      maxD = left + right
    }

    if left > right {
      return left + 1
    }
    return right + 1
  }
  height(root)
  return maxD
}

2. Binary Tree Maximum Path Sum

Problem: Find the maximum path sum between any two nodes. The path must follow connections. Nodes can be negative. 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. The path does not need to pass through the root.

Examples:

Input: root = [1,2,3] -> Output: 6 (Path is 2 -> 1 -> 3)
Input: root = [-10,9,20,null,null,15,7] -> Output: 42 (Path is 15 -> 20 -> 7)

Constraints:

The number of nodes in the tree is in the range [1, 3 * 104].
-1000 <= Node.val <= 1000

Edge Cases & Clarifying Questions

Q: Can all nodes be negative? A: Yes. In that case, the maximum path sum will be the single node with the largest (closest to zero) negative value. We cannot return an empty path (sum of 0).
Q: Do we have to include at least one node? A: Yes. A path sum requires at least one node.
Edge Case: Single node tree. Output is just the node’s value.

Intuition (The “Genesis”)

Brute Force Approach: Calculate the path sum starting from every node in the tree and finding the maximum path going down to leaves. Doing this across all possible combinations results in an O(N2) time complexity.

Optimized Approach (Post-order Traversal): This is structurally identical to the “Diameter” problem. But instead of Height = Max(Left, Right) + 1, we compute MaxSum = Max(LeftGain, RightGain) + Node.Val. The Catch: If a branch sum is negative, ignore it (treat as 0). Adding a negative path reduces your total sum. So LeftGain = max(0, dfs(left)).

Pattern explicitly: Post-order Traversal (Bottom-Up DFS). At each node, we check the max sum of the path passing through it and update the global max. We then return the max path sum that can be extended from this node up to its parent.

Common Pitfalls:

Confusing what to return. You can only return a single straight path up to the parent (node.val + max(left, right)). You cannot return node.val + left + right because a path cannot branch in two directions at the same node.
Initializing the global maximum to 0 instead of negative infinity, which fails if all nodes are negative.

Interactive Analysis

Visualize how negative nodes affect path choices. A branch with a negative sum is pruned (treated as 0).

Tree Ready.

Max Path Sum: -∞

Solutions

Java

class Solution {
  int maxSum = Integer.MIN_VALUE;

  public int maxPathSum(TreeNode root) {
    gain(root);
    return maxSum;
  }

  private int gain(TreeNode node) {
    if (node == null) return 0;

    // If gain is negative, ignore the branch (0)
    int leftGain = Math.max(gain(node.left), 0);
    int rightGain = Math.max(gain(node.right), 0);

    // Path through current root
    int currentPathSum = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, currentPathSum);

    // Return max gain one path up
    return node.val + Math.max(leftGain, rightGain);
  }
}

Go

func maxPathSum(root *TreeNode) int {
  maxS := -1000000000 // Min Int
  var gain func(*TreeNode) int
  gain = func(node *TreeNode) int {
    if node == nil { return 0 }

    left := max(gain(node.Left), 0)
    right := max(gain(node.Right), 0)

    currentPath := node.Val + left + right
    if currentPath > maxS {
      maxS = currentPath
    }

    return node.Val + max(left, right)
  }
  gain(root)
  return maxS
}

func max(a, b int) int {
  if a > b { return a }
  return b
}

Complexity

Strategy	Time	Space	Notes
DFS	O(N)	O(H)	Visit every node once. Space is recursion depth.