C Program Find k-th smallest element in BST

Given root of binary search tree and K as input, find K-th smallest element in BST.

For example, in the following BST, if k = 3, then output should be 10, and if k = 5, then output should be 14.

Method 1: Using Inorder Traversal.

Inorder traversal of BST retrieves elements of tree in the sorted order. The inorder traversal uses stack to store to be explored nodes of tree (threaded tree avoids stack and recursion for traversal, see this post). The idea is to keep track of popped elements which participate in the order statics. Hypothetical algorithm is provided below,

Time complexity: O(n) where n is total nodes in tree..

Algorithm:

/* initialization */
pCrawl = root
set initial stack element as NULL (sentinal)

/* traverse upto left extreme */
while(pCrawl is valid )
   stack.push(pCrawl)
   pCrawl = pCrawl.left

/* process other nodes */
while( pCrawl = stack.pop() is valid )
   stop if sufficient number of elements are popped.
   if( pCrawl.right is valid )
      pCrawl = pCrawl.right
      while( pCrawl is valid )
         stack.push(pCrawl)
         pCrawl = pCrawl.left

Implementation:

[pastacode lang=”c” manual=”%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%23define%20ARRAY_SIZE(arr)%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%0A%20%0A%2F*%20just%20add%20elements%20to%20test%20*%2F%0A%2F*%20NOTE%3A%20A%20sorted%20array%20results%20in%20skewed%20tree%20*%2F%0Aint%20ele%5B%5D%20%3D%20%7B%2020%2C%208%2C%2022%2C%204%2C%2012%2C%2010%2C%2014%20%7D%3B%0A%20%0A%2F*%20same%20alias%20*%2F%0Atypedef%20struct%20node_t%20node_t%3B%0A%20%0A%2F*%20Binary%20tree%20node%20*%2F%0Astruct%20node_t%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%0A%20%20%20%20node_t*%20left%3B%0A%20%20%20%20node_t*%20right%3B%0A%7D%3B%0A%20%0A%2F*%20simple%20stack%20that%20stores%20node%20addresses%20*%2F%0Atypedef%20struct%20stack_t%20stack_t%3B%0A%20%0A%2F*%20initial%20element%20always%20NULL%2C%20uses%20as%20sentinal%20*%2F%0Astruct%20stack_t%0A%7B%0A%20%20%20%20node_t*%20%20base%5BARRAY_SIZE(ele)%20%2B%201%5D%3B%0A%20%20%20%20int%20%20%20%20%20%20stackIndex%3B%0A%7D%3B%0A%20%0A%2F*%20pop%20operation%20of%20stack%20*%2F%0Anode_t%20*pop(stack_t%20*st)%0A%7B%0A%20%20%20%20node_t%20*ret%20%3D%20NULL%3B%0A%20%0A%20%20%20%20if(%20st%20%26%26%20st-%3EstackIndex%20%3E%200%20)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20ret%20%3D%20st-%3Ebase%5Bst-%3EstackIndex%5D%3B%0A%20%20%20%20%20%20%20%20st-%3EstackIndex–%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20ret%3B%0A%7D%0A%20%0A%2F*%20push%20operation%20of%20stack%20*%2F%0Avoid%20push(stack_t%20*st%2C%20node_t%20*node)%0A%7B%0A%20%20%20%20if(%20st%20)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20st-%3EstackIndex%2B%2B%3B%0A%20%20%20%20%20%20%20%20st-%3Ebase%5Bst-%3EstackIndex%5D%20%3D%20node%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Iterative%20insertion%0A%20%20%20Recursion%20is%20least%20preferred%20unless%20we%20gain%20something%0A*%2F%0Anode_t%20*insert_node(node_t%20*root%2C%20node_t*%20node)%0A%7B%0A%20%20%20%20%2F*%20A%20crawling%20pointer%20*%2F%0A%20%20%20%20node_t%20*pTraverse%20%3D%20root%3B%0A%20%20%20%20node_t%20*currentParent%20%3D%20root%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20till%20appropriate%20node%0A%20%20%20%20while(pTraverse)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20currentParent%20%3D%20pTraverse%3B%0A%20%0A%20%20%20%20%20%20%20%20if(%20node-%3Edata%20%3C%20pTraverse-%3Edata%20)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20left%20subtree%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20pTraverse%20%3D%20pTraverse-%3Eleft%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20right%20subtree%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20pTraverse%20%3D%20pTraverse-%3Eright%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20If%20the%20tree%20is%20empty%2C%20make%20it%20as%20root%20node%20*%2F%0A%20%20%20%20if(%20!root%20)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20root%20%3D%20node%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%20if(%20node-%3Edata%20%3C%20currentParent-%3Edata%20)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Insert%20on%20left%20side%20*%2F%0A%20%20%20%20%20%20%20%20currentParent-%3Eleft%20%3D%20node%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Insert%20on%20right%20side%20*%2F%0A%20%20%20%20%20%20%20%20currentParent-%3Eright%20%3D%20node%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20root%3B%0A%7D%0A%20%0A%2F*%20Elements%20are%20in%20an%20array.%20The%20function%20builds%20binary%20tree%20*%2F%0Anode_t*%20binary_search_tree(node_t%20*root%2C%20int%20keys%5B%5D%2C%20int%20const%20size)%0A%7B%0A%20%20%20%20int%20iterator%3B%0A%20%20%20%20node_t%20*new_node%20%3D%20NULL%3B%0A%20%0A%20%20%20%20for(iterator%20%3D%200%3B%20iterator%20%3C%20size%3B%20iterator%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20new_node%20%3D%20(node_t%20*)malloc(%20sizeof(node_t)%20)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20initialize%20*%2F%0A%20%20%20%20%20%20%20%20new_node-%3Edata%20%20%20%3D%20keys%5Biterator%5D%3B%0A%20%20%20%20%20%20%20%20new_node-%3Eleft%20%20%20%3D%20NULL%3B%0A%20%20%20%20%20%20%20%20new_node-%3Eright%20%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20insert%20into%20BST%20*%2F%0A%20%20%20%20%20%20%20%20root%20%3D%20insert_node(root%2C%20new_node)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20root%3B%0A%7D%0A%20%0Anode_t%20*k_smallest_element_inorder(stack_t%20*stack%2C%20node_t%20*root%2C%20int%20k)%0A%7B%0A%20%20%20%20stack_t%20*st%20%3D%20stack%3B%0A%20%20%20%20node_t%20*pCrawl%20%3D%20root%3B%0A%20%0A%20%20%20%20%2F*%20move%20to%20left%20extremen%20(minimum)%20*%2F%0A%20%20%20%20while(%20pCrawl%20)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20push(st%2C%20pCrawl)%3B%0A%20%20%20%20%20%20%20%20pCrawl%20%3D%20pCrawl-%3Eleft%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20pop%20off%20stack%20and%20process%20each%20node%20*%2F%0A%20%20%20%20while(%20pCrawl%20%3D%20pop(st)%20)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20each%20pop%20operation%20emits%20one%20element%0A%20%20%20%20%20%20%20%20%20%20%20in%20the%20order%0A%20%20%20%20%20%20%20%20*%2F%0A%20%20%20%20%20%20%20%20if(%20!–k%20)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20loop%20testing%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20st-%3EstackIndex%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20there%20is%20right%20subtree%20*%2F%0A%20%20%20%20%20%20%20%20if(%20pCrawl-%3Eright%20)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20push%20the%20left%20subtree%20of%20right%20subtree%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20pCrawl%20%3D%20pCrawl-%3Eright%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20while(%20pCrawl%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20push(st%2C%20pCrawl)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pCrawl%20%3D%20pCrawl-%3Eleft%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20pop%20off%20stack%20and%20repeat%20*%2F%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20node%20having%20k-th%20element%20or%20NULL%20node%20*%2F%0A%20%20%20%20return%20pCrawl%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0Aint%20main(void)%0A%7B%0A%20%20%20%20node_t*%20root%20%3D%20NULL%3B%0A%20%20%20%20stack_t%20stack%20%3D%20%7B%20%7B0%7D%2C%200%20%7D%3B%0A%20%20%20%20node_t%20*kNode%20%3D%20NULL%3B%0A%20%0A%20%20%20%20int%20k%20%3D%205%3B%0A%20%0A%20%20%20%20%2F*%20Creating%20the%20tree%20given%20in%20the%20above%20diagram%20*%2F%0A%20%20%20%20root%20%3D%20binary_search_tree(root%2C%20ele%2C%20ARRAY_SIZE(ele))%3B%0A%20%0A%20%20%20%20kNode%20%3D%20k_smallest_element_inorder(%26stack%2C%20root%2C%20k)%3B%0A%20%0A%20%20%20%20if(%20kNode%20)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22kth%20smallest%20elment%20for%20k%20%3D%20%25d%20is%20%25d%22%2C%20k%2C%20kNode-%3Edata)%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22There%20is%20no%20such%20element%22)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20getchar()%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C Programming” highlight=”” provider=”manual”/] [ad type=”banner”]

Method 2: Augmented  Tree Data Structure.

The idea is to maintain rank of each node. We can keep track of elements in a subtree of any node while building the tree. Since we need K-th smallest element, we can maintain number of elements of left subtree in every node.

Assume that the root is having N nodes in its left subtree. If K = N + 1, root is K-th node. If K < N, we will continue our search (recursion) for the Kth smallest element in the left subtree of root. If K > N + 1, we continue our search in the right subtree for the (K – N – 1)-th smallest element. Note that we need the count of elements in left subtree only.

Time complexity: O(h) where h is height of tree.

Algorithm:

start:
if K = root.leftElement + 1
   root node is the K th node.
   goto stop
else if K > root.leftElements
   K = K - (root.leftElements + 1)
   root = root.right
   goto start
else
   root = root.left
   goto srart

stop:

Implementation:

[pastacode lang=”c” manual=”%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%23define%20ARRAY_SIZE(arr)%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%0A%20%0Atypedef%20struct%20node_t%20node_t%3B%0A%20%0A%2F*%20Binary%20tree%20node%20*%2F%0Astruct%20node_t%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20int%20lCount%3B%0A%20%0A%20%20%20%20node_t*%20left%3B%0A%20%20%20%20node_t*%20right%3B%0A%7D%3B%0A%20%0A%2F*%20Iterative%20insertion%0A%20%20%20Recursion%20is%20least%20preferred%20unless%20we%20gain%20something%0A*%2F%0Anode_t%20*insert_node(node_t%20*root%2C%20node_t*%20node)%0A%7B%0A%20%20%20%20%2F*%20A%20crawling%20pointer%20*%2F%0A%20%20%20%20node_t%20*pTraverse%20%3D%20root%3B%0A%20%20%20%20node_t%20*currentParent%20%3D%20root%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20till%20appropriate%20node%0A%20%20%20%20while(pTraverse)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20currentParent%20%3D%20pTraverse%3B%0A%20%0A%20%20%20%20%20%20%20%20if(%20node-%3Edata%20%3C%20pTraverse-%3Edata%20)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20We%20are%20branching%20to%20left%20subtree%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20increment%20node%20count%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20pTraverse-%3ElCount%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20left%20subtree%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20pTraverse%20%3D%20pTraverse-%3Eleft%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20right%20subtree%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20pTraverse%20%3D%20pTraverse-%3Eright%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20If%20the%20tree%20is%20empty%2C%20make%20it%20as%20root%20node%20*%2F%0A%20%20%20%20if(%20!root%20)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20root%20%3D%20node%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%20if(%20node-%3Edata%20%3C%20currentParent-%3Edata%20)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Insert%20on%20left%20side%20*%2F%0A%20%20%20%20%20%20%20%20currentParent-%3Eleft%20%3D%20node%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Insert%20on%20right%20side%20*%2F%0A%20%20%20%20%20%20%20%20currentParent-%3Eright%20%3D%20node%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20root%3B%0A%7D%0A%20%0A%2F*%20Elements%20are%20in%20an%20array.%20The%20function%20builds%20binary%20tree%20*%2F%0Anode_t*%20binary_search_tree(node_t%20*root%2C%20int%20keys%5B%5D%2C%20int%20const%20size)%0A%7B%0A%20%20%20%20int%20iterator%3B%0A%20%20%20%20node_t%20*new_node%20%3D%20NULL%3B%0A%20%0A%20%20%20%20for(iterator%20%3D%200%3B%20iterator%20%3C%20size%3B%20iterator%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20new_node%20%3D%20(node_t%20*)malloc(%20sizeof(node_t)%20)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20initialize%20*%2F%0A%20%20%20%20%20%20%20%20new_node-%3Edata%20%20%20%3D%20keys%5Biterator%5D%3B%0A%20%20%20%20%20%20%20%20new_node-%3ElCount%20%3D%200%3B%0A%20%20%20%20%20%20%20%20new_node-%3Eleft%20%20%20%3D%20NULL%3B%0A%20%20%20%20%20%20%20%20new_node-%3Eright%20%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20insert%20into%20BST%20*%2F%0A%20%20%20%20%20%20%20%20root%20%3D%20insert_node(root%2C%20new_node)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20root%3B%0A%7D%0A%20%0Aint%20k_smallest_element(node_t%20*root%2C%20int%20k)%0A%7B%0A%20%20%20%20int%20ret%20%3D%20-1%3B%0A%20%0A%20%20%20%20if(%20root%20)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20A%20crawling%20pointer%20*%2F%0A%20%20%20%20%20%20%20%20node_t%20*pTraverse%20%3D%20root%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Go%20to%20k-th%20smallest%20*%2F%0A%20%20%20%20%20%20%20%20while(pTraverse)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if(%20(pTraverse-%3ElCount%20%2B%201)%20%3D%3D%20k%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ret%20%3D%20pTraverse-%3Edata%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20if(%20k%20%3E%20pTraverse-%3ElCount%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20%20There%20are%20less%20nodes%20on%20left%20subtree%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Go%20to%20right%20subtree%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20k%20%3D%20k%20-%20(pTraverse-%3ElCount%20%2B%201)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pTraverse%20%3D%20pTraverse-%3Eright%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20The%20node%20is%20on%20left%20subtree%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pTraverse%20%3D%20pTraverse-%3Eleft%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20ret%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0Aint%20main(void)%0A%7B%0A%20%20%20%20%2F*%20just%20add%20elements%20to%20test%20*%2F%0A%20%20%20%20%2F*%20NOTE%3A%20A%20sorted%20array%20results%20in%20skewed%20tree%20*%2F%0A%20%20%20%20int%20ele%5B%5D%20%3D%20%7B%2020%2C%208%2C%2022%2C%204%2C%2012%2C%2010%2C%2014%20%7D%3B%0A%20%20%20%20int%20i%3B%0A%20%20%20%20node_t*%20root%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%2F*%20Creating%20the%20tree%20given%20in%20the%20above%20diagram%20*%2F%0A%20%20%20%20root%20%3D%20binary_search_tree(root%2C%20ele%2C%20ARRAY_SIZE(ele))%3B%0A%20%0A%20%20%20%20%2F*%20%20It%20should%20print%20the%20sorted%20array%20*%2F%0A%20%20%20%20for(i%20%3D%201%3B%20i%20%3C%3D%20ARRAY_SIZE(ele)%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%5Cn%20kth%20smallest%20elment%20for%20k%20%3D%20%25d%20is%20%25d%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i%2C%20k_smallest_element(root%2C%20i))%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20getchar()%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C Programming” highlight=”” provider=”manual”/] [ad type=”banner”]