Find kth smallest element in a binary search tree in Optimum way

103

81

I need to find the kth smallest element in the binary search tree without using any static/global variable. How to achieve it efficiently? The solution that I have in my mind is doing the operation in O(n), the worst case since I am planning to do an inorder traversal of the entire tree. But deep down I feel that I am not using the BST property here. Is my assumptive solution correct or is there a better one available ?

bragboy

Posted 2010-02-24T20:18:05.183

Reputation: 23 487

1If you do a search on "Order Statistics" you will find what you need. – RAL – 2010-02-24T20:41:27.383

5Is the tree balanced? – kennytm – 2010-02-24T20:21:43.793

Its not. But if it were balanced, is there an optimum way? – bragboy – 2010-02-24T20:27:26.147

I sort of feel most of the answers below, while correct are cheating in that they are using a global variable of some sort (whether it's a reference to an integer, or a variable that gets decremented and returned). If absolutely none of those are allowed, I would use recursion without any references being passed in. – Henley Chiu – 2013-08-15T02:10:17.607

Answers

159

Here's just an outline of the idea:

In a BST, the left subtree of node T contains only elements smaller than the value stored in T. If k is smaller than the number of elements in the left subtree, the kth smallest element must belong to the left subtree. Otherwise, if k is larger, then the kth smallest element is in the right subtree.

We can augment the BST to have each node in it store the number of elements in its left subtree (assume that the left subtree of a given node includes that node). With this piece of information, it is simple to traverse the tree by repeatedly asking for the number of elements in the left subtree, to decide whether to do recurse into the left or right subtree.

Now, suppose we are at node T:

  1. If k == num_elements(left subtree of T), then the answer we're looking for is the value in node T.
  2. If k > num_elements(left subtree of T), then obviously we can ignore the left subtree, because those elements will also be smaller than the kth smallest. So, we reduce the problem to finding the k - num_elements(left subtree of T) smallest element of the right subtree.
  3. If k < num_elements(left subtree of T), then the kth smallest is somewhere in the left subtree, so we reduce the problem to finding the kth smallest element in the left subtree.

Complexity analysis:

This takes O(depth of node) time, which is O(log n) in the worst case on a balanced BST, or O(log n) on average for a random BST.

A BST requires O(n) storage, and it takes another O(n) to store the information about the number of elements. All BST operations take O(depth of node) time, and it takes O(depth of node) extra time to maintain the "number of elements" information for insertion, deletion or rotation of nodes. Therefore, storing information about the number of elements in the left subtree keeps the space and time complexity of a BST.

IVlad

Posted 2010-02-24T20:18:05.183

Reputation: 36 937

@RobertS.Barnes, so that would make an inorder traversal have the same order complexity? I.e., traverse inorder until you reach k. – TheOne – 2012-08-08T00:18:30.400

56To find the Nth smallest item, you only need to store the size of the left sub-tree. You'd use the size of the right sub-tree iif you also wanted to be able to find the Nth largest item. Actually, you can make that less expensive though: store the total size of the tree in the root, and the size of the left sub-tree. When you need to size of the right sub-tree, you can subtract the size of the left from the total size. – Jerry Coffin – 2010-02-24T20:33:36.247

@Jerry Coffin: true, nice observation :). – IVlad – 2010-02-24T20:36:10.357

I don't understand something. You say "k>T". k is a position like first smallest, 2nd smallest and so on. T is the value of a node right? Why compare them? And if T is also the order of a node(this is not clear to me sorry) how do I find it? – Para – 2010-06-06T15:54:11.470

@Para - I used T to mean the number of elements in node T's left subtree (this is a bit unclear, yes, I'll edit). You find it when building the tree: once you insert a node (if you do it recursively it's easier), after you return from the recursive call on the left subtree, increment the count in the current node. Let me know if it's still not clear. – IVlad – 2010-06-06T16:32:18.580

What about the case with duplicate values? Question din't say you can assume uniqueness. – Nitin Garg – 2014-02-21T16:55:14.447

35Such an augmented BST is called an 'order statistics tree'. – Daniel – 2010-08-13T17:34:57.180

1

@Nitin Garg: a BST by definition doesn't have duplicate values -see http://en.wikipedia.org/wiki/Binary_search_tree

– nevets1219 – 2014-05-20T07:15:42.790

9@Ivlad: in step 2: I think "k - num_elements" should be "k - num_elements -1", since you've to include root element too. – understack – 2010-09-13T05:13:44.053

@understack - not if you assume the root to be part of the subtree. – IVlad – 2010-09-13T08:48:51.150

k == num_elements(left subtree of T) .. this should be k == num_elements(left subtree of T) +1. – Anil Vishnoi – 2010-09-25T06:57:01.603

@RobertS.Barnes If your tree does not store "the number of elements" info on the nodes, then you have to traverse the entire left subtree to check the order, so time can be worse than O(n), indeed Θ(n^2) in the worst case (on a very left-skewed tree). But of course this algorithm is only useful when you have that info (the sizes), and it only takes O(n) extra memory and O(1) extra time to maintain them, so a good deal if you need to do many rank queries on your tree. – Alan Tam – 2015-06-21T21:22:18.237

@IVlad amazing algorithm! You got me thinking. Python3 solution posted at https://github.com/harishvc/challenges/blob/master/binary-search-tree-smallestK.py

– harishvc – 2015-09-10T01:35:09.060

15If the tree doesn't contain a field containing the "number of elements in its left and right subtree" then the method will end up being BigO( n ) as you will need to walk the right or left subtree at each node in order to calculate the k index of the current node. – Robert S. Barnes – 2011-01-29T16:26:26.230

@AlanTam could you explain how it would ever be worse than O(n)? We have an ordered tree, so we will at a maximum have to look at each node in the tree once to find the kth smallest element which is O(n). – FrontSide – 2018-11-14T21:04:07.253

@FrontSide nothing is worse than O(n). The time required to locate a node using this algorithm is merely O(depth of node), which is merely O(log n) as long as the tree is properly balanced. – Alan Tam – 2018-11-15T22:44:56.863

@AlanTam That's what I thought. Thanks for clarifying. I must have misinterpreted your comment above. – FrontSide – 2018-11-16T10:31:14.160

62

A simpler solution would be to do an inorder traversal and keep track of the element currently to be printed (without printing it). When we reach k, print the element and skip rest of tree traversal.

void findK(Node* p, int* k) {
  if(!p || k < 0) return;
  findK(p->left, k);
  --k;
  if(k == 0) { 
    print p->data;
    return;  
  } 
  findK(p->right, k); 
}

prasadvk

Posted 2010-02-24T20:18:05.183

Reputation: 1 073

1

+1: The idea is in the right direction, but some loose ends may need to be tightened; see http://stackoverflow.com/a/23069077/278326

– Arun – 2014-04-14T19:55:29.230

I like this solution, since BST is already ordered, a traversal should be enough. – Merlin – 2015-06-11T15:43:16.187

3If n is close to the total number of nodes in this tree, your algorithm will take O(n) time to finish, which is bad for the selected answer-O(log n) – Spark8006 – 2015-07-02T14:58:34.980

12

public int ReturnKthSmallestElement1(int k)
    {
        Node node = Root;

        int count = k;

        int sizeOfLeftSubtree = 0;

        while(node != null)
        {

            sizeOfLeftSubtree = node.SizeOfLeftSubtree();

            if (sizeOfLeftSubtree + 1 == count)
                return node.Value;
            else if (sizeOfLeftSubtree < count)
            {
                node = node.Right;
                count -= sizeOfLeftSubtree+1;
            }
            else
            {
                node = node.Left;
            }
        }

        return -1;
    }

this is my implementation in C# based on the algorithm above just thought I'd post it so people can understand better it works for me

thank you IVlad

Para

Posted 2010-02-24T20:18:05.183

Reputation: 868

10

A simpler solution would be to do an inorder traversal and keep track of the element currently to be printed with a counter k. When we reach k, print the element. The runtime is O(n). Remember the function return type can not be void, it has to return its updated value of k after each recursive call. A better solution to this would be an augmented BST with a sorted position value at each node.

public static int kthSmallest (Node pivot, int k){
    if(pivot == null )
        return k;   
    k = kthSmallest(pivot.left, k);
    k--;
    if(k == 0){
        System.out.println(pivot.value);
    }
    k = kthSmallest(pivot.right, k);
    return k;
}

Sumit Balani

Posted 2010-02-24T20:18:05.183

Reputation: 109

I guess your solution is better in terms of space complexity, compared with the augmented BST. – zach – 2017-02-07T07:36:10.543

The search doesn't stop even after the k-th smallest element is found. – Vineeth Chitteti – 2018-11-29T12:23:14.077

9

//add a java version without recursion

public static <T> void find(TreeNode<T> node, int num){
    Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();

    TreeNode<T> current = node;
    int tmp = num;

    while(stack.size() > 0 || current!=null){
        if(current!= null){
            stack.add(current);
            current = current.getLeft();
        }else{
            current = stack.pop();
            tmp--;

            if(tmp == 0){
                System.out.println(current.getValue());
                return;
            }

            current = current.getRight();
        }
    }
}

Jiaji Li

Posted 2010-02-24T20:18:05.183

Reputation: 1 000

I like this solution and the corresponding recursive one. Honestly, most of the answers to this question are too confusing/complex to read. – Henley Chiu – 2013-08-15T02:11:33.550

I love this solution! Clear and great! – Rugal – 2015-09-25T19:21:12.943

This solution is traversing the tree 'in-order' and decreasing a counter after visiting the node, to later stop when the counter gets equals to zero. The worst case is then of order O(n). Not the most optimal comparing with @IVlad's recursive solutions whose worst case takes O(log n) – Jorge P. – 2017-02-03T01:59:11.177

7

You can use iterative inorder traversal: http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal with a simple check for kth element after poping a node out of the stack.

Binh Nguyen

Posted 2010-02-24T20:18:05.183

Reputation: 71

4

Recursive In-order Walk with a counter

Time Complexity: O( N ), N is the number of nodes
Space Complexity: O( 1 ), excluding the function call stack

The idea is similar to @prasadvk solution, but it has some shortcomings (see notes below), so I am posting this as a separate answer.

// Private Helper Macro
#define testAndReturn( k, counter, result )                         \
    do { if( (counter == k) && (result == -1) ) {                   \
        result = pn->key_;                                          \
        return;                                                     \
    } } while( 0 )

// Private Helper Function
static void findKthSmallest(
    BstNode const * pn, int const k, int & counter, int & result ) {

    if( ! pn ) return;

    findKthSmallest( pn->left_, k, counter, result );
    testAndReturn( k, counter, result );

    counter += 1;
    testAndReturn( k, counter, result );

    findKthSmallest( pn->right_, k, counter, result );
    testAndReturn( k, counter, result );
}

// Public API function
void findKthSmallest( Bst const * pt, int const k ) {
    int counter = 0;
    int result = -1;        // -1 := not found
    findKthSmallest( pt->root_, k, counter, result );
    printf("%d-th element: element = %d\n", k, result );
}

Notes (and differences from @prasadvk's solution):

  1. if( counter == k ) test is required at three places: (a) after left-subtree, (b) after root, and (c) after right subtree. This is to ensure that kth element is detected for all locations, i.e. irrespective of the subtree it is located.

  2. if( result == -1 ) test required to ensure only the result element is printed, otherwise all the elements starting from the kth smallest up to the root are printed.

Arun

Posted 2010-02-24T20:18:05.183

Reputation: 12 952

Time complexity for this solution is O(k + d), where d is max depth of the tree. Therefore it uses a global variable counter but it's illegal for this question. – Valentin Shergin – 2014-12-16T16:50:20.983

Hi Arun, can you please explain with an example. I am not understand this particularly your first point. – Andy897 – 2015-01-05T16:48:14.480

4

Given just a plain binary search tree, about all you can do is start from the smallest, and traverse upward to find the right node.

If you're going to do this very often, you can add an attribute to each node signifying how many nodes are in its left sub-tree. Using that, you can descend the tree directly to the correct node.

Jerry Coffin

Posted 2010-02-24T20:18:05.183

Reputation: 380 820

3

For not balanced searching tree, it takes O(n).

For balanced searching tree, it takes O(k + log n) in the worst case but just O(k) in Amortized sense.

Having and managing the extra integer for every node: the size of the sub-tree gives O(log n) time complexity. Such balanced searching tree is usually called RankTree.

In general, there are solutions (based not on tree).

Regards.

Slava

Posted 2010-02-24T20:18:05.183

Reputation: 679

1

This works well: status : is the array which holds whether element is found. k : is kth element to be found. count : keeps track of number of nodes traversed during the tree traversal.

int kth(struct tree* node, int* status, int k, int count)
{
    if (!node) return count;
    count = kth(node->lft, status, k, count);  
    if( status[1] ) return status[0];
    if (count == k) { 
        status[0] = node->val;
        status[1] = 1;
        return status[0];
    }
    count = kth(node->rgt, status, k, count+1);
    if( status[1] ) return status[0];
    return count;
}

pranjal

Posted 2010-02-24T20:18:05.183

Reputation: 421

1

Well here is my 2 cents...

int numBSTnodes(const Node* pNode){
     if(pNode == NULL) return 0;
     return (numBSTnodes(pNode->left)+numBSTnodes(pNode->right)+1);
}


//This function will find Kth smallest element
Node* findKthSmallestBSTelement(Node* root, int k){
     Node* pTrav = root;
     while(k > 0){
         int numNodes = numBSTnodes(pTrav->left);
         if(numNodes >= k){
              pTrav = pTrav->left;
         }
         else{
              //subtract left tree nodes and root count from 'k'
              k -= (numBSTnodes(pTrav->left) + 1);
              if(k == 0) return pTrav;
              pTrav = pTrav->right;
        }

        return NULL;
 }

Manish Shukla

Posted 2010-02-24T20:18:05.183

Reputation: 430

1

While this is definitely not the optimal solution to the problem, it is another potential solution which I thought some people might find interesting:

/**
 * Treat the bst as a sorted list in descending order and find the element 
 * in position k.
 *
 * Time complexity BigO ( n^2 )
 *
 * 2n + sum( 1 * n/2 + 2 * n/4 + ... ( 2^n-1) * n/n ) = 
 * 2n + sigma a=1 to n ( (2^(a-1)) * n / 2^a ) = 2n + n(n-1)/4
 *
 * @param t The root of the binary search tree.
 * @param k The position of the element to find.
 * @return The value of the element at position k.
 */
public static int kElement2( Node t, int k ) {
    int treeSize = sizeOfTree( t );

    return kElement2( t, k, treeSize, 0 ).intValue();
}

/**
 * Find the value at position k in the bst by doing an in-order traversal 
 * of the tree and mapping the ascending order index to the descending order 
 * index.
 *
 *
 * @param t Root of the bst to search in.
 * @param k Index of the element being searched for.
 * @param treeSize Size of the entire bst.
 * @param count The number of node already visited.
 * @return Either the value of the kth node, or Double.POSITIVE_INFINITY if 
 *         not found in this sub-tree.
 */
private static Double kElement2( Node t, int k, int treeSize, int count ) {
    // Double.POSITIVE_INFINITY is a marker value indicating that the kth 
    // element wasn't found in this sub-tree.
    if ( t == null )
        return Double.POSITIVE_INFINITY;

    Double kea = kElement2( t.getLeftSon(), k, treeSize, count );

    if ( kea != Double.POSITIVE_INFINITY )
        return kea;

    // The index of the current node.
    count += 1 + sizeOfTree( t.getLeftSon() );

    // Given any index from the ascending in order traversal of the bst, 
    // treeSize + 1 - index gives the
    // corresponding index in the descending order list.
    if ( ( treeSize + 1 - count ) == k )
        return (double)t.getNumber();

    return kElement2( t.getRightSon(), k, treeSize, count );
}

Robert S. Barnes

Posted 2010-02-24T20:18:05.183

Reputation: 27 138

1

signature:

Node * find(Node* tree, int *n, int k);

call as:

*n = 0;
kthNode = find(root, n, k);

definition:

Node * find ( Node * tree, int *n, int k)
{
   Node *temp = NULL;

   if (tree->left && *n<k)
      temp = find(tree->left, n, k);

   *n++;

   if(*n==k)
      temp = root;

   if (tree->right && *n<k)
      temp = find(tree->right, n, k);

   return temp;
}

Aim

Posted 2010-02-24T20:18:05.183

Reputation: 11

0

The Linux Kernel has an excellent augmented red-black tree data structure that supports rank-based operations in O(log n) in linux/lib/rbtree.c.

A very crude Java port can also be found at http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java, together with RbRoot.java and RbNode.java. The n'th element can be obtained by calling RbNode.nth(RbNode node, int n), passing in the root of the tree.

Daniel

Posted 2010-02-24T20:18:05.183

Reputation: 26

0

Here's a concise version in C# that returns the k-th smallest element, but requires passing k in as a ref argument (it's the same approach as @prasadvk):

Node FindSmall(Node root, ref int k)
{
    if (root == null || k < 1)
        return null;

    Node node = FindSmall(root.LeftChild, ref k);
    if (node != null)
        return node;

    if (--k == 0)
        return node ?? root;
    return FindSmall(root.RightChild, ref k);
}

It's O(log n) to find the smallest node, and then O(k) to traverse to k-th node, so it's O(k + log n).

Erhhung

Posted 2010-02-24T20:18:05.183

Reputation: 780

how about the java version? – Henley Chiu – 2013-08-14T21:02:12.833

0

http://www.geeksforgeeks.org/archives/10379

this is the exact answer to this question:-

1.using inorder traversal on O(n) time 2.using Augmented tree in k+log n time

Shivendra

Posted 2010-02-24T20:18:05.183

Reputation: 965

0

I couldn't find a better algorithm..so decided to write one :) Correct me if this is wrong.

class KthLargestBST{
protected static int findKthSmallest(BSTNode root,int k){//user calls this function
    int [] result=findKthSmallest(root,k,0);//I call another function inside
    return result[1];
}
private static int[] findKthSmallest(BSTNode root,int k,int count){//returns result[]2 array containing count in rval[0] and desired element in rval[1] position.
    if(root==null){
        int[]  i=new int[2];
        i[0]=-1;
        i[1]=-1;
        return i;
    }else{
        int rval[]=new int[2];
        int temp[]=new int[2];
        rval=findKthSmallest(root.leftChild,k,count);
        if(rval[0]!=-1){
            count=rval[0];
        }
        count++;
        if(count==k){
            rval[1]=root.data;
        }
        temp=findKthSmallest(root.rightChild,k,(count));
        if(temp[0]!=-1){
            count=temp[0];
        }
        if(temp[1]!=-1){
            rval[1]=temp[1];
        }
        rval[0]=count;
        return rval;
    }
}
public static void main(String args[]){
    BinarySearchTree bst=new BinarySearchTree();
    bst.insert(6);
    bst.insert(8);
    bst.insert(7);
    bst.insert(4);
    bst.insert(3);
    bst.insert(4);
    bst.insert(1);
    bst.insert(12);
    bst.insert(18);
    bst.insert(15);
    bst.insert(16);
    bst.inOrderTraversal();
    System.out.println();
    System.out.println(findKthSmallest(bst.root,11));
}

}

laxman

Posted 2010-02-24T20:18:05.183

Reputation: 1

0

Here is the java code,

max(Node root, int k) - to find kth largest

min(Node root, int k) - to find kth Smallest

static int count(Node root){
    if(root == null)
        return 0;
    else
        return count(root.left) + count(root.right) +1;
}
static int max(Node root, int k) {
    if(root == null)
        return -1;
    int right= count(root.right);

    if(k == right+1)
        return root.data;
    else if(right < k)
        return max(root.left, k-right-1);
    else return max(root.right, k);
}

static int min(Node root, int k) {
    if (root==null)
        return -1;

    int left= count(root.left);
    if(k == left+1)
        return root.data;
    else if (left < k)
        return min(root.right, k-left-1);
    else
        return min(root.left, k);
}

code_2_peep

Posted 2010-02-24T20:18:05.183

Reputation: 15

0

this would work too. just call the function with maxNode in the tree

def k_largest(self, node , k): if k < 0 : return None
if k == 0: return node else: k -=1 return self.k_largest(self.predecessor(node), k)

user2229805

Posted 2010-02-24T20:18:05.183

Reputation: 1

0

I think this is better than the accepted answer because it doesn't need to modify the original tree node to store the number of it's children nodes.

We just need to use the in-order traversal to count the smallest node from the left to right, stop searching once the count equals to K.

private static int count = 0;
public static void printKthSmallestNode(Node node, int k){
    if(node == null){
        return;
    }

    if( node.getLeftNode() != null ){
        printKthSmallestNode(node.getLeftNode(), k);
    }

    count ++ ;
    if(count <= k )
        System.out.println(node.getValue() + ", count=" + count + ", k=" + k);

    if(count < k  && node.getRightNode() != null)
        printKthSmallestNode(node.getRightNode(), k);
}

jinshui

Posted 2010-02-24T20:18:05.183

Reputation: 40

0

This is what I though and it works. It will run in o(log n )

public static int FindkThSmallestElemet(Node root, int k)
    {
        int count = 0;
        Node current = root;

        while (current != null)
        {
            count++;
            current = current.left;
        }
        current = root;

        while (current != null)
        {
            if (count == k)
                return current.data;
            else
            {
                current = current.left;
                count--;
            }
        }

        return -1;


    } // end of function FindkThSmallestElemet

Learner

Posted 2010-02-24T20:18:05.183

Reputation: 1 270

1i don't think this solution will work. What if the Kth smallest is in the right sub tree of the tree node ? – Anil Vishnoi – 2010-09-25T06:54:41.000

0

IVlad solution using an order statistics tree is the most efficient. But if you can not use an order statistics tree and are stuck with a regular old BST then the best approach is to do an In Order Traversal (as pointed out by prasadvk). But his solution is inadequate if you want to return the kth smallest element and not just simply print out the value. Also, since his solution is recursive, there is the danger of stack overflow. Therefore, I wrote a java solution that returns the kth smallest node and uses a stack to do the In Order Traversal. The run time is O(n) while the space complexity is O(h) where h is the max height of the tree.

// The 0th element is defined to be the smallest element in the tree.
public Node find_kth_element(Node root , int k) {

    if (root == null || k < 0) return null;

    Deque<Node> stack = new ArrayDeque<Node>();
    stack.push(root);

    while (!stack.isEmpty()) {

        Node curr = stack.peek();

        if (curr.left != null) {

            stack.push(curr.left);
            continue;
        }

        if (k == 0) return curr;
        stack.pop();
        --k;

        if (curr.right != null) {

            stack.push(curr.right);

        }

    }

    return null;
}

Haider

Posted 2010-02-24T20:18:05.183

Reputation: 173

0

Best approach is already there.But I'd like to add a simple Code for that

int kthsmallest(treenode *q,int k){
int n = size(q->left) + 1;
if(n==k){
    return q->val;
}
if(n > k){
    return kthsmallest(q->left,k);
}
if(n < k){
    return kthsmallest(q->right,k - n);
}

}

int size(treenode *q){
if(q==NULL){
    return 0;
}
else{
    return ( size(q->left) + size(q->right) + 1 );
}}

PrashantKumarNirmal

Posted 2010-02-24T20:18:05.183

Reputation: 26

0

Using auxiliary Result class to track if node is found and current k.

public class KthSmallestElementWithAux {

public int kthsmallest(TreeNode a, int k) {
    TreeNode ans = kthsmallestRec(a, k).node;
    if (ans != null) {
        return ans.val;
    } else {
        return -1;
    }
}

private Result kthsmallestRec(TreeNode a, int k) {
    //Leaf node, do nothing and return
    if (a == null) {
        return new Result(k, null);
    }

    //Search left first
    Result leftSearch = kthsmallestRec(a.left, k);

    //We are done, no need to check right.
    if (leftSearch.node != null) {
        return leftSearch;
    }

    //Consider number of nodes found to the left
    k = leftSearch.k;

    //Check if current root is the solution before going right
    k--;
    if (k == 0) {
        return new Result(k - 1, a);
    }

    //Check right
    Result rightBalanced = kthsmallestRec(a.right, k);

    //Consider all nodes found to the right
    k = rightBalanced.k;

    if (rightBalanced.node != null) {
        return rightBalanced;
    }

    //No node found, recursion will continue at the higher level
    return new Result(k, null);

}

private class Result {
    private final int k;
    private final TreeNode node;

    Result(int max, TreeNode node) {
        this.k = max;
        this.node = node;
    }
}
}

Alex Fedulov

Posted 2010-02-24T20:18:05.183

Reputation: 718

0

Well we can simply use the in order traversal and push the visited element onto a stack. pop k number of times, to get the answer.

we can also stop after k elements

kartheek babu

Posted 2010-02-24T20:18:05.183

Reputation: 11

1this is not an optimum solution – bragboy – 2011-02-12T11:49:58.037

0

 public int printInorder(Node node, int k) 
    { 
        if (node == null || k <= 0) //Stop traversing once you found the k-th smallest element
            return k; 

        /* first recur on left child */
        k = printInorder(node.left, k); 

        k--;
        if(k == 0) {  
            System.out.print(node.key);
        }

        /* now recur on right child */
        return printInorder(node.right, k);
    } 

This java recursive algorithm, stops the recursion once the k-th smallest element is found.

Vineeth Chitteti

Posted 2010-02-24T20:18:05.183

Reputation: 575

0

Solution for complete BST case :-

Node kSmallest(Node root, int k) {
  int i = root.size(); // 2^height - 1, single node is height = 1;
  Node result = root;
  while (i - 1 > k) {
    i = (i-1)/2;  // size of left subtree
    if (k < i) {
      result = result.left;
    } else {
      result = result.right;
      k -= i;
    }  
  }
  return i-1==k ? result: null;
}

gvijay

Posted 2010-02-24T20:18:05.183

Reputation: 1 279

-1

i wrote a neat function to calculate the kth smallest element. I uses in-order traversal and stops when the it reaches the kth smallest element.

void btree::kthSmallest(node* temp, int& k){
if( temp!= NULL)   {
 kthSmallest(temp->left,k);       
 if(k >0)
 {
     if(k==1)
    {
      cout<<temp->value<<endl;
      return;
    }

    k--;
 }

 kthSmallest(temp->right,k);  }}

Tarunjit Singh

Posted 2010-02-24T20:18:05.183

Reputation: 1

No metrics provided as to why this is optimal. In both large and small cases – Woot4Moo – 2012-10-21T15:09:51.700

-1

int RecPrintKSmallest(Node_ptr head,int k){
  if(head!=NULL){
    k=RecPrintKSmallest(head->left,k);
    if(k>0){
      printf("%c ",head->Node_key.key);
      k--;
    }
    k=RecPrintKSmallest(head->right,k);
  }
  return k;
}

Ebrahim saada

Posted 2010-02-24T20:18:05.183

Reputation: 9

2Please always accompany code with some level of description as to what it does and how it helps solve the issue. – Ren – 2013-01-18T14:20:43.817

-1

public TreeNode findKthElement(TreeNode root, int k){
    if((k==numberElement(root.left)+1)){
        return root;
    }
    else if(k>numberElement(root.left)+1){
        findKthElement(root.right,k-numberElement(root.left)-1);
    }
    else{
        findKthElement(root.left, k);
    }
}

public int numberElement(TreeNode node){
    if(node==null){
        return 0;
    }
    else{
        return numberElement(node.left) + numberElement(node.right) + 1;
    }
}

Amazon I'm coming

Posted 2010-02-24T20:18:05.183

Reputation: 1

-1

public static Node kth(Node n, int k){
    Stack<Node> s=new Stack<Node>();
    int countPopped=0;
    while(!s.isEmpty()||n!=null){
      if(n!=null){
        s.push(n);
        n=n.left;
      }else{
        node=s.pop();
        countPopped++;
        if(countPopped==k){
            return node;
        }
        node=node.right;

      }
  }

}

Ryan

Posted 2010-02-24T20:18:05.183

Reputation: 2 419

-5

For a binary search tree, an inorder traversal will return elements ... in order.

Just do an inorder traversal and stop after traversing k elements.

O(1) for constant values of k.

Anon.

Posted 2010-02-24T20:18:05.183

Reputation: 42 909

@Anon. Thanks. But that is something that I am already aware of which is O(n) complex. My question is whether it has a better solution – bragboy – 2010-02-24T20:22:33.490

Meh, better call it O(k). I can also say OP's solution O(1) for constant values of N. – kennytm – 2010-02-24T20:23:39.577

3Saying that's "O(1) for constant values of k" is kind of cheating. I can say any algorithm is O(1) like that... – IVlad – 2010-02-24T20:23:40.447

This is O(1) for constant values of k, regardless of the size of the tree. If k varies, it's O(k), but still independent of the tree size. – Anon. – 2010-02-24T20:23:42.613

Well, yeah we should not be carried away what value is inside big O. It merely signifies the 'rate' at which the function grows. – bragboy – 2010-02-24T20:26:40.283

Why consider k a constant anyway? If it's a constant you can just precompute the result and of course it's O(1). And if k varies, it varies between 1 and the number of nodes in the tree, so it's not really independent of the tree size, therefore it's O(N). – IVlad – 2010-02-24T20:31:25.967

@|\/|ad: You will notice that even if k is constant, the size of the dataset is likely not. – Anon. – 2010-02-24T20:33:52.407

4please...how could it be independent of the tree size? Try finding the smallest element... is that O(1)? So how could finding the k'th smallest possibly be O(1)? – RAL – 2010-02-24T20:37:26.563

@Anon: Yes, which makes it O(N) to precompute the result and O(1) to answer a query using an inorder traversal. Anyway, my point is that assuming k constant is making an unfounded assumption, as the question does not state that. – IVlad – 2010-02-24T20:38:52.240

+1 to Robert's comment. Even finding min (k=1) is O(log n) in balanced tree. (and -1 to answer). – None – 2010-02-24T21:15:27.973

-1 because the answer is misleading (it's NOT O(1), it's O(N) for BST and O(log N) for balanced tree). – kgadek – 2011-09-01T07:45:20.460