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; } }

For this problem, you can exploit the data structure's layout to avoid recursion and run in O(n) time. You must traverse all internal nodes, so sum their values. The internal nodes have index i where 0 <= i < (n / 2). Then for each pair of leaf nodes, add the max value to the sum. The pairs of leaf nodes are adjacent to each other.
#include <cstdlib> int max(int x, int y) { if (x > y) return x; return y; } // heap is a complete binary tree with every leaf at the same depth int getMaxSum(const int* const root, int size) { if (NULL == root) { return 0; } // Need the sum of all the internal nodes. int sum = 0; int i = 0; for (; i < size / 2; ++i) { sum += root[i]; } // Then the max of each node pair. for (; i < size; i += 2) { sum += max(root[i], root[i + 1]); } return sum; } void main() { int heap[] = { 2, 4, 5, 8, 4, 3, 6 }; auto maxSum = getMaxSum(heap, sizeof(heap) / sizeof(int)); }

static int calcMaxDia ( int[] tree , int index ) { if(index > tree.length 1) return 0; int maxLeftBranch = calcMaxDia(tree,index*2); int maxRightBranch = calcMaxDia(tree,index*2 + 1); int dia = maxLeftBranch + maxRightBranch + tree[index]; if(dia > maxDia) maxDia = dia; return Math.max(maxLeftBranch,maxRightBranch)+tree[index]; }

@abhi96gupta said in Binary Tree largest Sum:
maximum diameter sum in a binary tree
Can you define max diameter sum?