CareerCup

maintain a max heap with pair<height, val>, keep popping and adding val till height is of max value.

To calculate sum of all leaves in a Tree i use modified traverse function. The function is recursive, first it calculates the sum of leaves in left subTree of a node, then the leaves of right subTree, and then returns sum of left + right. To identify a leaf node it checks if its leftChild and rightChild are null. If they are null it returns a value of current node. The code is in java. To make code simpler i use only Node class without tree.

public class SumLeafExample{
    
    public static class Node{
        private int key;
        private Node left;
        private Node right;
        
        public Node(int key)
        {
            this.key = key;
            this.left = null;
            this.right = null;
        }
        
        public void insert(int key)
        {
            insert(key, this);
        }
        
        private void insert(int key, Node localRoot)
        {
            if(key < localRoot.key)
            {
                if(localRoot.left != null)
                {
                    insert(key, localRoot.left);
                }else
                {
                    localRoot.left = new Node(key);
                }
            }else
            {
                if(localRoot.right != null)
                {
                    insert(key, localRoot.right);
                }else
                {
                    localRoot.right = new Node(key);
                }
            }
        }
        
        public int leafSum()
        {
            return leafSum(this);
        }
        
        private int leafSum(Node localRoot)
        {
            if(localRoot == null)return 0;
            if(localRoot.left == null && localRoot.right == null)
            {
                return localRoot.key;
            }else
            {
                int leftSum = leafSum(localRoot.left);
                int rightSum = leafSum(localRoot.right);
                return leftSum + rightSum;
            }
        }
    }

     public static void main(String []args){
        Node treeRoot = new Node(20);
        treeRoot.insert(10);
        treeRoot.insert(30);
        treeRoot.insert(18);
        treeRoot.insert(29);
        treeRoot.insert(45);
        
        System.out.println(treeRoot.leafSum());
        //18 + 29 + 45 = 92
     }
}