[!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: The length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
Intuition
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.
Strategy:
Use DFS to calculate Height.
Update a global max variable with L + R at each node.
Return max(L, R) + 1 to the parent (standard height calculation).
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
Go
```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.
Intuition
This is the same as “Diameter”, but instead of Height = Max(L, R) + 1, we carry the MaxSum = Max(L, R) + Node.Val.
Catch: If a branch sum is negative, ignore it (treat as 0). Adding a negative path reduces your total.
Solutions
Java
Go
```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
}
```