Software Developer

This can be solved using recursion. 
Steps :
(1) Call Mirror for left-subtree i.e., Mirror(left-subtree)
(2) Call Mirror for right-subtree i.e., Mirror(right-subtree)
(3) Swap left and right subtrees.
temp = left->subtree
left->subtree = right->subtree
right->subtree = temp

Worst-case Time complexity is O(n) 
Auxiliary space complexity : O(h) where h is the height of the tree.

The direct approach to solve this problem is to run two for loops and for every subarray check if it is the maximum sum possible. 
Time complexity : O(N^2), Where N is the size of the array.
Space complexity : O(1)
The efficient approach is to use Kadane's algorithm. It calculates the maximum sum subarray ending at a particular index by using the maximum sum subarray ending at the previous position. 
Steps : 
Declare two variables : currSum which stores maximum sum ending here and maxSum which stores maximum sum so far.
Initialize currSum = 0 and maxSum = INT_MIN.
Now, traverse the array and add the value of the current element to currSum and check : 
1. If currSum > maxSum, update maxSum equals to currSum.
2. If currSum < 0, make currSum equal to zero.
Finally, print the value of maxSum.

The simple approach is to start from the root and do an inorder traversal of the tree. For each node N, check whether the subtree rooted with N is BST or not. If BST, then return size of the subtree rooted with N. Else, recur down the left and right subtrees, and return the maximum of values returned by left and right subtrees.

Time Complexity : The worst-case time complexity of this method will be O(n^2). Consider a skewed tree for worst case analysis.
 

In the above approach, we traverse the tree in top-down manner and do BST test for every node. If we traverse the tree in bottom-up manner, then we can pass information about subtrees to the parent. The passed information can be used by the parent to do BST test (for parent node) only in constant time (or O(1) time). A left subtree need to tell the parent whether it is BST or not and also needs to pass maximum value in it. So that we can compare the maximum value with the parent’s data to check the BST property. Similarly, the right subtree need to pass the minimum value up the tree. The subtrees need to pass the following information up the tree for the finding the largest BST. 

1) Whether the subtree itself is BST or not (In the following code, is_bst_ref is used for this purpose).
 

2) If the subtree is left subtree of its parent, then maximum value in it. And if it is right subtree then minimum value in it. 
 

3) Size of this subtree if this subtree is BST (In the following code, return value of largestBSTtil() is used for this purpose).
 

Time Complexity : O(n) where n is the number of nodes in the given Binary Tree.

When we observe the binary sequence from 0 to 2n – 1 (n is # of bits), right most bits (least significant) vary rapidly than left most bits. The idea is to find right most string of 1’s in x, and shift the pattern to right extreme, except the left most bit in the pattern. Shift the left most bit in the pattern (omitted bit) to left part of x by one position.