1.if we use simple divide and conquer technique(without using extra space)
we first need to count no. of leaf in left subtree,then no. of leaf in right subtree+compare them to find minimum.
T(n)=2T(n/2)+1----->O(n)
but we need to compute this for every node.
so, cost at 0 th level=O(n)
cost at 1st level=n/2+n/2=O(n)
cost at 2nd level=n/4+n/4+n/4+n/4=O(n)\
we have total of logn levels (because tree is balanced) and cost at every level is O(n).
Hence total cost is=n*logn=O(nlogn)
2.if we use extra memory to store no of leaf at left subtree and at right subtree for every node
we don't need to go to last level for every node.
1.compute for every leaf node.
2.then use those values to compute at all nodes at (h-1) level till root.
so, time complexity of this method is equal to O(n),since we are calculating value for each node and doing only one comparison.
space complexity is also O(n),since we are using extra memory for every node.
since question is asking about worst case time complexity,so we have O(nlogn) .