Binary Tree largest Sum


  • 3
    A

    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)


  • 1
    C

    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
    

  • 0
    T

    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
    

  • 0
    I

    @tnuttty

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.