Count smaller elements on right side in a given Array.

eg : [4,12,5,6,1,34,3,2]
o/p  [3,5, 3,3,0, 2,1,0]


ex2: {8, 3, 10, 1, 6, 14, 4, 7, 13}
o/p: {5, 1, 4,  0, 1, 3,  0, 0, 0}


Approach:
Example array: A: [4,12,5,6,1,34,3,2]
1. Start creating BST from the end of the array.


tree node is like:
class Node {
Integer data;
Integer left_count;
Integer counter;
Node left;
Node right;

public Node(Integer data) {
this.data = data;
this.left_count = 1;
this.counter = 0;
this.left = null; this.right = null;
}
}


2. every tree node has left_count (size of left subtree + 1) and counter (number of smaller elements on the right side.)


3. Recursion looks like this:
public static Node insertIntoBST(Node node, int value, int leftSum) {
if (null == node) { return new Node(value); }
if (value <= node.data) {
++node.left_count;
node.left = insertIntoBST(node.left, value,leftSum);
if (node.left.left == null && node.left.right == null)
node.left.counter = leftSum;
} else {
node.right = insertIntoBST(node.right, value, node.left_count+leftSum);
if (node.right.right == null && node.right.left == null)
node.right.counter = node.left_count+node.counter;
}
return node;
}

4. Lets trace the above code with example:
A: [4,12,5,6,1,34,3,2]


start inserting from the end of the array A.
So ..
step1: insert (2) - its the root node.
       2 (1,0) -> 1 is left_count and 0 is counter.
  

step2: insert (3) - it will go to right of 2
  2 (1,0)
   3(1,1)


step3: insert (34) - it will go to right of 3
2 (1,0)
     3(1,1)
        34(1,2)
step4: insert (1) - it will go to the left of 2.
2(2,0)
1(1,0) 3(1,1)
                  `34(1,2)


step5: insert (6) - it will go to the left of 34.
2(2,0)
1(1,0) 3(1,1)
                  34(1,2)
        6(1,3)

step6: insert (5) - it will go to the left of 6.
2(2,0)
1(1,0) 3(1,1)
          34(1,2)
    6(2,3)
5(1,3)

step7: insert (12) - it will go to the right of 12.
2(2,0)
1(1,0) 3(1,1)
34(1,2)
6(2,3)
5(1,3) 12(1,5)

step8: insert (4) - it will go to the left of 5.
2(2,0)
1(1,0) 3(1,1)
                34(1,2)
       6(3,3)
         5(2,3) 12(1,5)
     4(1,3)

4 has counter 3 because from root we take right so leftsum is now 2, again we take right from 3, so leftsum+=1 = 3, and from 34 we keep left till we insert it has left child of 5.
We are done!


Code input/ouput:
eg : [4,12,5,6,1,34,3,2]
o/p  [3,5, 3,3,0, 2,1,0]
Printing data and count of smaller elements to the right: 
1::0
2::0
3::1
4::3
5::3
6::3
12::5
34::2


ex2: {8, 3, 10, 1, 6, 14, 4, 7, 13}
o/p: {5, 1, 4,  0, 1, 3,  0, 0, 0}
Printing data and count of smaller elements to the right: 
1::0
3::1
4::0
6::1
7::0
8::5
10::4
13::0
14::3

Time complexity: O(nlogn)

Nth largest node in a BST

Find the Nth largest node in a BST.


Example BST:

Code input/output:


inorder: 

1 3 4 6 7 8 10 13 14 
Size of BST: 9
1 largest node: 1
2 largest node: 3
3 largest node: 4
4 largest node: 6
5 largest node: 7
6 largest node: 8
7 largest node: 10
8 largest node: 13
9 largest node: 14

Find the closest value to K in BST

Given (i) a non-empty binary search tree with double values (e.g. 3.5) in each node and (ii) a key value K. Write a method to find the closest value to K.


Code input/output:
printing inorder of BST: 
3.3 3.49 3.51 3.52 3.55 3.56 3.57 3.59 3.62 3.65 
Closest to 3.559: 3.56


Approach:

Full Code:

print 2 BSTs in ascending order.

Give two binary search trees, print the numbers of both together in ascending order.


Code output:
Building first BST with values:
13 37 91 88 7 16 54 
Building second BST with values:
1 40 45 14 8 22 50 
printing 2 BSTs in ascending order: 
1 7 8 13 14 16 22 37 40 45 50 54 88 91 


Let "n" be the size of the first BST and "m" be the size of second BST.
Time complexity: O(n+m).
space complexity: O(1).

Binary Tree Operations.

Code for following problems:


1. Given a binary tree, count the number of nodes in the tree.
2. Given a binary tree, compute its "maxDepth" -- the number of nodes along the longest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0.
3. Given a non-empty binary search tree (an ordered binary tree), return the minimum data value found in that tree. Note that it is not necessary to search the entire tree. A maxValue() function is structurally very similar to this function.
4. Given a binary search tree (aka an "ordered binary tree"), iterate over the nodes to print them out in increasing order.
5. Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Return false if no such path can be found.
6. Given a binary tree, print out all of its root-to-leaf paths, one per line.
7. Change a tree so that the roles of the left and right pointers are swapped at every node.
8. Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way.
9. Suppose you are building an N node binary search tree with the values 1..N. How many structurally different
binary search trees are there that store those values? Write a recursive function that, given the number of distinct values, computes the number of structurally unique binary search trees that store those values. For example, countTrees(4) should return 14, since there are 14 structurally unique binary search trees that store 1, 2, 3, and 4. The base case is easy, and the recursion is short but dense. Your code should not construct any actual trees; it's just a
counting problem.
10. Write an isBST() function that returns true if a tree is a binary search tree
and false otherwise.

Code: