Find the value of maximum diameter sum in a binary tree.(Assume tree is complete binary tree and and every leaf node is at the same depth from root of the tree).
The first element in the input is the root element of the tree. Considering index of root element is 1 in the following problem, left child of i'th element in the input is the (2i)th element and right child of ith element is (2i+1)th element.
Input:
1
7
2 4 5 8 4 3 6
Output:
22
Explanation:
Path followed to get the maximum diameter sum in this case is
8 (leaf) > 4 > 2 > 5 > 3 (leaf node)
Binary Tree largest Sum


Dynamic programming in O(n)
left[node] = max sum of the left subtree right[node] = max sum of the right subtree left[node] = max(left[left_child], right[left_child]) + value[node] right[node] = max(left[right_child], right[right_child]) + value[node] now for every node, you can combine these arrays and pick the max sum

I'm not sure if this is correct but max diameter of root is max diameter of left plus max diameter of right where diameter sum is max(left, right, left + right) + current
var tree = [2,4,5,8,4,3,6]; var result = (function getMaxDiameterSum(tree, nodeIndex) { if (nodeIndex < 0  nodeIndex >= tree.length) { return 0; }else { var leftSum = getMaxDiameterSum(tree, nodeIndex * 2 + 1); var rightSum = getMaxDiameterSum(tree, nodeIndex * 2 + 2); var current = tree[nodeIndex]; return Math.max(leftSum + rightSum, leftSum, rightSum) + current; } })(tree, 0); console.log('maxSum : ' + result); //outputs 22

public int getHeight(Node root) { if(root == null) return 0; return Math.max(root.data+getHeight(root.left), root.data+getHeight(root.right)); } public int getDiameter(Node root) { if(root!=null) { int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); int leftDiameter = root.data+getDiameter(root.left); int rightDiameter = root.data+getDiameter(root.right); return Math.max(leftHeight + rightHeight, Math.max(leftDiameter, rightDiameter)); } return 0; } class Node { int data; Node left; Node right; public Node(int data) { this.data = data; } }