CareerCup

People doing inorder traversal won't get the job. Imaging a perfectly balanced tree of a million nodes...

Answer is simple: Implement predecessor and successor.

Cost will be O(log n) for balanced trees for find the 3rd closest.

For generic k, this will be O(k log n), but for larger k, this will become O(n) (amortized successor cost is O(1) actually).

The optimized solution is to maintain a max heap of size 3 later extend it to 'k'. Where max is the difference between the element and the value. The time complexity will be:

O(N) tree traversal + O(k) heap creation + O(logk) hepify = ~O(N).

Comments are welcomed.

- maintain a 3 element sorted queue.
- as the BST is traversed (O(n)), if the difference is less than the max element, push the new one at the proper place in the queue (const time operation)
- at the end, the largest element in the queue is the solution.
- total cost is O(n)

Simple Solution:

1. Start Root -> Right in the In-Order, Find the Kth Value. -- K1
2. Go to Root->Left
3. Start Traversing in 'In-Order Reverse' (Right - Root- Left), Find the Kth Value -- K2
4. Answer : K1 > K2 ? K2 : K1

bst does not seem to make the soultion more efficient

There is no need to traverse whole BST.
Simple solution:
1. make a circular queue of size k that will hold the tree node type pointers.
2. Now search the value in the BST which will be in time O(log n) complexity.
3. While searching the value in tree just enque parents in the circular queue.
4. When u find the node at that time u'll have a queue that is holding upto kth parent.
5. Now compare values of the following nodes from the queue {kth, child of kth-1, child of child of kth-2, and so on upto the node we were searching}
6. U'll find the value of kth closest no.

Integer[] closest = new Integer[3]; // initialized with null  
void find_3rd_closest(Node current , int K){

	Node succ = Successor(current);
	Node pred = Predecessor(current);
	
	insert(closest , current.val , K);
	if (succ != null)
		insert(closest , succ.val , K);
	if (pred != null)
		insert(closest , pred.val , K);
		
	if (succ != null && pred != null)
		if (Math.abs(pred.val - K) < Math.abs(succ.val - K))
			find_3rd_closest(pred , K);
		else
			find_3rd_closest(succ , K);
	else if (pred != null)
		find_3rd_closest(pred , K);
	else if (succ != null)
		find_3rd_closest(succ , K);
	else
		return;
}

void insert(int[] closest , int val, int K){
	for (int i = 0 ; i < closest.length ; i++){
		if (Math.abs(K - val) < Math.abs(K - closest[i])){
			for (int j = i ; i < closest.length - 1 ; i++){
				int temp = closest[i+1];
				closest[i+1] = closest[i];
				closest[i] = temp;
			}
			closest[i] = succ.value;
		}
	}
}

Node Successor(Node current){
	if (current.rightChild == null)
		return null;
	current = current.rightChild;
	while (current.leftChild != null)
		current = current.leftChild;
	return current;
}

Node Predecessor(Node current){
	if (current.leftChild == null)
		return null;
	current = current.leftChild;
	while (current.rigthChild != null)
		current = current.rightChild;
	return current;
}