SDE - 2

Binary Search can be used in this problem.
Steps :
1) Use Binary search to get index of the first occurrence of x in the given array. Let the index of the first occurrence be i. 
2) Use Binary search to get index of the last occurrence of x in the given array. Let the index of the last occurrence be j. 
3) Return (j – i + 1);
Time Complexity: O(Logn)

One approach would be to traverse the tree and for every traversed node X :
1) Find maximum sum from leaf to root in left subtree of X 
2) Find maximum sum from leaf to root in right subtree of X. 
3) Add the above two calculated values and X->data and compare the sum with the maximum value obtained so far and update the maximum value. 
4) Return the maximum value.

The time complexity of above solution is O(n2)

This question can also be solved in a single traversal of binary tree. The idea is to maintain two values in recursive calls : 
1) Maximum root to leaf path sum for the subtree rooted under current node. 
2) The maximum path sum between leaves (desired output).

For every visited node X, we find the maximum root to leaf sum in left and right subtrees of X. We add the two values with X->data, and compare the sum with maximum path sum found so far.