randomtech

Problem Statement:     Given a tree, task is to find out the path with maximum sum of the elements along the path.  The path can be anywhere in the tree and need not go along the root and the nodes shouldn't be skipped in the path. Example 1: Input: [1,2,3] 1 / \ 2 3 Output: 6 Example 2: Input: [-10,9,20,null,null,15,7]   -10    / \   9   20     /  \     15   7 Output: 42  Approach to the solution:   Approach here is simple, first traverse the tree in post order manner. Keep track of maximum values of left and right. Keep track of maximum values of left side and right side. Compare and keep track of maximum values between maximum side max and sub tree. Keep track of global maximum sum of the path in one variable Compare global maximum sum with the sum which got from the above process. Return that maximum sum. This maximum sum is the maximum path of the sum ...

  Problem Statement: Given a binary search tree. Program should return Kth Smallest element in the binary search tree. Suppose if the binary tree is represented as: 3,1,4,null, 2 Then 1st smallest element is 1, second smallest element is 2 and 3rd smallest element is 3.   Solution with Explanation: The binary tree consists of elements in sorted order. The easiest way of finding solution is insert the elements in the priority queue and then  pop out k-1 elements, then top element of the priority queue is the kth smallest element of the tree. Optimized solution is doing in-order traversal and keeping track of the count of number of elements visited.  After visiting the left most element of the binary tree, increase the count to 1 and traverse back in in-order manner and increase the count. Whenever the count is reached to k return that element. Complexity Explanation: As the traversal is in-order, each node is visited only once. The traversal continues till the Kth el...