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

Question

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

User · Answer

int RecPrintKSmallest Node ptr head int k     if head  NULL       k RecPrintKSmallest head- gt left k       if k gt 0         printf   c   head- gt Node key key         k--            k RecPrintKSmallest head- gt right k         return k

User · Answer

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   amp  amp   result    -1                                  result   pn- gt key                                                      return                                                                while  0       Private Helper Function static void findKthSmallest      BstNode const   pn  int const k  int  amp  counter  int  amp  result          if    pn   return       findKthSmallest  pn- gt left   k  counter  result        testAndReturn  k  counter  result         counter    1      testAndReturn  k  counter  result         findKthSmallest  pn- gt 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- gt root   k  counter  result        printf   d-th element  element    d n   k  result        Notes  and differences from  prasadvk s solution     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  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

User · Answer

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

User · Answer

public static Node kth Node n  int k       Stack lt Node gt  s new Stack lt Node gt         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

User · Answer

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  lt  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

User · Answer

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

User · Answer

public int printInorder Node node  int k                  if  node    null    k  lt   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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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  lt   k           System out println node getValue        count     count      k     k        if count  lt  k   amp  amp  node getRightNode      null          printKthSmallestNode node getRightNode    k

User · Answer

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  lt  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

User · Answer

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- gt left  amp  amp   n lt k        temp   find tree- gt left  n  k        n        if  n  k        temp   root      if  tree- gt right  amp  amp   n lt k        temp   find tree- gt right  n  k       return temp

User · Answer

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

User · Answer

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

User · Answer

add a java version without recursion  public static  lt T gt  void find TreeNode lt T gt  node  int num       Stack lt TreeNode lt T gt  gt  stack   new Stack lt TreeNode lt T gt  gt          TreeNode lt T gt  current   node      int tmp   num       while stack size    gt  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

User · Answer

public TreeNode findKthElement TreeNode root  int k       if  k  numberElement root left  1            return root            else if k gt 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

User · Answer

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  lt  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  lt  k          return min root right  k-left-1       else         return min root left  k

User · Answer

Python Solution  Time Complexity   O n  Space Complexity   O 1   Idea is to use Morris Inorder Traversal   class Solution object   def inorderTraversal self  current   k        while current is not None       This Means we have reached Right Most Node i e end of LDR traversal          if current left is not None     If Left Exists traverse Left First             pre   current left    Goal is to find the node which will be just before the current node i e predecessor of current node  let s say current is D in LDR goal is to find L here             while pre right is not None and pre right    current     Find predecesor here                 pre   pre right             if pre right is None     In this case predecessor is found   now link this predecessor to current so that there is a path and current is not lost                 pre right   current                 current   current left             else                     This means we have traverse all nodes left to current so in LDR traversal of L is done                 k -  1                 if k    0                       return current val                 pre right   None        Remove the link tree restored to original here                  current   current right         else                 In LDR  LD traversal is done move to R              k -  1             if k    0                   return current val             current   current right      return 0  def kthSmallest self  root  k       return self inorderTraversal  root   k

User · Answer

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    If k    num elements left subtree of T   then the answer we re looking for is the value in node T  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   If k  lt  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

User · Answer

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

User · Answer

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

User · Answer

Well here is my 2 cents     int numBSTnodes const Node  pNode        if pNode    NULL  return 0       return  numBSTnodes pNode- gt left  numBSTnodes pNode- gt right  1         This function will find Kth smallest element Node  findKthSmallestBSTelement Node  root  int k        Node  pTrav   root       while k  gt  0            int numNodes   numBSTnodes pTrav- gt left            if numNodes  gt   k                 pTrav   pTrav- gt left                      else                  subtract left tree nodes and root count from  k                k -   numBSTnodes pTrav- gt left    1                 if k    0  return pTrav                pTrav   pTrav- gt right                     return NULL

User · Answer

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- gt lft  status  k  count         if  status 1    return status 0       if  count    k             status 0    node- gt val          status 1    1          return status 0             count   kth node- gt rgt  status  k  count 1       if  status 1    return status 0       return count

User · Answer

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  gt  k        i    i-1  2      size of left subtree     if  k  lt  i          result   result left        else         result   result right        k -  i                return i-1  k   result  null

User · Answer

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

User · Answer

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 amp  k   if  temp   NULL       kthSmallest temp- gt left k           if k  gt 0          if k  1              cout lt  lt temp- gt value lt  lt endl        return             k--       kthSmallest temp- gt right k

User · Answer

this would work too  just call the function with maxNode in the tree  def k largest self  node   k           if k  lt  0               return None         if k    0              return node         else              k - 1             return self k largest self predecessor node   k

User · Answer

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- gt left    1  if n  k       return q- gt val    if n  gt  k       return kthsmallest q- gt left k     if n  lt  k       return kthsmallest q- gt right k - n          int size treenode  q   if q  NULL       return 0    else      return   size q- gt left    size q- gt right    1

User · Answer

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  lt  0  return    findK p- gt left  k     --k    if k    0         print p- gt data      return           findK p- gt right  k

User · Answer

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

User · Answer

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

[algorithm] Find kth smallest element in a binary search tree in Optimum way

Examples related to algorithm

Examples related to data-structures

Examples related to binary-tree

Examples related to binary-search