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

  • 0
    O

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

  • 0
    K
    This post is deleted!

  • 0
    K
     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];
          
      }

Log in to reply
 

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