# Dynamic Programming on Trees

D

## Problems

1. Diameter of a Binary Tree
2. Maximum path sum from any node to any node
3. Maximum path sum from leaf to leaf
4. Diameter of N-array tree

### 1. Diameter of a Binary Tree

https://leetcode.com/problems/diameter-of-binary-tree/submissions/

``````class Solution {
public int diameterOfBinaryTree(TreeNode root) {
return getMaxHeightAndDiameter(root)[1];
}

/**
*   returns int[] 0th index-> maxHeight, 1st index-> max diameter
*/
public int[] getMaxHeightAndDiameter(TreeNode node) {
if (node == null) {
return new int[]{0, 0};
}
int[] leftSubTreeInfo = getMaxHeightAndDiameter(node.left);
int[] rightSubTreeInfo = getMaxHeightAndDiameter(node.right);
int[] response = new int[2];
response[0] = leftSubTreeInfo[0] > rightSubTreeInfo[0] ? leftSubTreeInfo[0] : rightSubTreeInfo[0];
response[0]++;
response[1]  = leftSubTreeInfo[0] + rightSubTreeInfo[0];
if (response[1] < leftSubTreeInfo[1]) {
response[1] = leftSubTreeInfo[1];
}
if (response[1] < rightSubTreeInfo[1]) {
response[1] = rightSubTreeInfo[1];
}
return response;
}
}
``````

### 2. Maximum path sum from any node to any node

https://leetcode.com/problems/binary-tree-maximum-path-sum/

``````class Solution {

int maxPathSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
getMaxHeight(root);
return maxPathSum;
}

private int getMaxHeight(TreeNode node) {
if (node == null) {
return 0;
}
int maxLeftPathSum = getMaxHeight(node.left);
int maxRightPathSum = getMaxHeight(node.right);
int temp = Math.max(node.val, node.val + Math.max(maxLeftPathSum, maxRightPathSum));
int currentPathSum = Math.max(node.val + maxLeftPathSum + maxRightPathSum, temp );
maxPathSum = Math.max(maxPathSum, currentPathSum);
return temp;
}

}
``````

### 3. Maximum path sum from leaf to leaf

Published in:
Originally Published On : Aug 01, 2021