Find K nodes in BST that are closest to a value key (Part II).

Question: There is a BST while each node has distinct values, then for a given value key, find out K nodes in this BST such that their values are closest to key.

Solution:

It is provided in previous blog Find K nodes in BST that are closest to a value key (Part I) an O(log(n)) approach to find out such K nodes, however previously is was assumed that each node in BST has “Parent” pointer, what if this pointer is unavailable? Furthermore, some one may argue that in order to find out is next larger node or next smaller node, one sometimes needs to back track through the entire tree path, and which takes O(log(n)) time and therefore not efficient.

Hence, this blog provide an O(log(n)) approach without the help of the “Parent” pointers. It uses extra addition space to store a stack, which stores all the parent nodes when travelling at a given node. An auxiliary reading about how to use stack to iteratively traverse the BST can be found in http://www.leetcode.com/2010/04/binary-search-tree-in-order-traversal.html.

The algorithm can go as following:

1) Start from the root node to find out the node (denoted as the closestNode) whose value is closest to key, store all the passed middle-level nodes in a stack where stack.peek() is the closeNode. In this case, the return value should be a stack instead of a single node.
2) Generate two functions the nextLargerNodeInBSTIterative() and nextSmallerNodeInBSTIterative(), by the help of the stack and based on closestNode find its next larger node, denoted as nextLarger, and find its next smaller node, denoted as nextSmaller.
3) Compare nextSmaller to nextLarger by their difference to key, and update them appropriately until K nodes are selected.

Step 1) costs O(log(n)), with space complexity O(log(n)).
Step 3) In the worse case, it takes O(log(n)) to find its next larger node or its next smaller node, however, each node in BST is check at most once. Therefore the time complexity should be max{O(log(n)), O(K)} = O(log(n)).

Overall, its an O(log(n)) approach.

//main function, for step 3)
public static List findKClosestNodeInBSTIterative(Tree root, int key, int k)
{
    List list = new List();
    Stack stack = findTreeWithKeyNearestToTheKeyIterative(root, key);
    Tree closestNode = stack.Pop();
    k--;
    list.Add(closestNode);
    Stack stackForSmaller = new Stack(), stackForGreater = new Stack(), temp = new Stack();
    //copy the current stack to two stacks
	//so they can be used in findnext functions.
	while (stack.Count > 0)
        temp.Push(stack.Pop());
    while (temp.Count > 0)
   {
        Tree tempTree = temp.Pop();
        stackForSmaller.Push(tempTree);
        stackForGreater.Push(tempTree);
    }
    Tree nextlarger = nextLargerNodeInBSTIterative(closestNode,stackForGreater);
    Tree nextSmaller = nextSmallerNodeInBSTIterative(closestNode,stackForSmaller);
    while (k > 0)
    {
        if (nextlarger == null && nextSmaller == null)
            throw new StackOverflowException();
        else if (nextlarger != null && nextSmaller != null)
        {
            if (Math.Abs(nextlarger.node - key) >= Math.Abs(nextSmaller.node - key))
            {
                list.Add(nextSmaller);
                k--;
                nextSmaller = nextSmallerNodeInBSTIterative(nextSmaller, stackForSmaller);
            }
            else
            {
                list.Add(nextlarger);
                k--;
                nextlarger = nextLargerNodeInBSTIterative(nextlarger, stackForGreater);
            }
        }
        else if (nextlarger != null)
        {
            list.Add(nextlarger);
            k--;
            nextlarger = nextLargerNodeInBSTIterative(nextlarger, stackForGreater);
        }
        else
        {
            list.Add(nextSmaller);
            k--;
            nextSmaller = nextSmallerNodeInBSTIterative(nextSmaller, stackForSmaller);
        }
    }
    return list;
}

 public static Stack findTreeWithKeyNearestToTheKeyIterative(Tree root, int key)
{
    Stack stack = new Stack();
    Tree desiredRoot = root;
    int diff = Math.Abs(root.node - key);
    while (root != null)
    {
        stack.Push(root);
        if (diff > Math.Abs(root.node - key))
        {
            diff = Math.Abs(root.node - key);
            desiredRoot = root;
        }
        if (root.node > key)
            root = root.leftChild;
        else if (root.node < key)
            root = root.rightChild;
        else
            return stack;
    }
    while (stack.Peek() != desiredRoot)
        stack.Pop();
    return stack;
}

//step 2) find its next larger node
 public static Tree nextLargerNodeInBSTIterative(Tree current, Stackstack)
{
    if (current.rightChild != null)
    {
        Tree nextTree = current.rightChild;
        while (nextTree.leftChild != null)
        {
            stack.Push(nextTree);
            nextTree = nextTree.leftChild;
        }
        return nextTree;
    }
    else
    {
        if (stack.Count > 0)
        {
            Tree tempTree = stack.Pop();
            while (tempTree != null)
            {
                if (tempTree.node > current.node)
                    break;
                else
                    tempTree = stack.Count > 0 ? stack.Pop() : null;
            }
            return tempTree;
        }
        else
            return null;
    }
}
//step 2) find its next smaller node
public static Tree nextSmallerNodeInBSTIterative(Tree current, Stack stack)
{
    if (current.leftChild != null)
    {
        Tree nextTree = current.leftChild;
        while (nextTree.rightChild != null)
        {
            stack.Push(nextTree);
            nextTree = nextTree.rightChild;
        }
        return nextTree;
    }
    else
    {
        if (stack.Count > 0)
        {
            Tree tempTree = stack.Pop();
            while (tempTree != null)
            {
                if (tempTree.node < current.node)
                   break;
                else
                   tempTree = stack.Count>0?stack.Pop():null;
            }
            return tempTree;
        }
        else
            return null;
    }
}