{"id":27276,"date":"2018-01-20T20:38:15","date_gmt":"2018-01-20T15:08:15","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27276"},"modified":"2018-01-20T20:38:15","modified_gmt":"2018-01-20T15:08:15","slug":"find-k-th-smallest-element-bst","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/find-k-th-smallest-element-bst\/","title":{"rendered":"C Program Find k-th smallest element in BST"},"content":{"rendered":"<p>Given root of binary search tree and K as input, find K-th smallest element in BST.<span id=\"more-10379\"><\/span><\/p>\n<p>For example, in the following BST, if k = 3, then output should be 10, and if k = 5, then output should be 14.<\/p>\n<p><strong>Method 1:\u00a0Using Inorder Traversal.<\/strong><\/p>\n<p>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.\u00a0Hypothetical\u00a0algorithm is provided below,<\/p>\n<p>Time complexity: O(n) where n is total nodes in tree..<\/p>\n<p><strong>Algorithm:<\/strong><\/p>\n<pre>\/* initialization *\/\r\npCrawl = root\r\nset initial stack element as NULL (sentinal)\r\n\r\n\/* traverse upto left extreme *\/\r\nwhile(pCrawl is valid )\r\n   stack.push(pCrawl)\r\n   pCrawl = pCrawl.left\r\n\r\n\/* process other nodes *\/\r\nwhile( pCrawl = stack.pop()\u00a0is valid )\r\n   stop if sufficient number of elements are popped.\r\n   if( pCrawl.right is valid )\r\n      pCrawl = pCrawl.right\r\n      while( pCrawl is valid\u00a0)\r\n         stack.push(pCrawl)\r\n         pCrawl = pCrawl.left<\/pre>\n<p><strong>Implementation:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%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\u2013%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!\u2013k%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\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<p><strong>Method 2:\u00a0Augmented \u00a0Tree Data Structure.<\/strong><\/p>\n<p>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.<\/p>\n<p>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 \u2013 N \u2013 1)-th smallest element. Note that we need the count of elements in left subtree only.<\/p>\n<p>Time complexity: O(h) where h is height of tree.<\/p>\n<p><strong>Algorithm:<\/strong><\/p>\n<pre>start:\r\nif K = root.leftElement + 1\r\n   root node is the K th node.\r\n   goto stop\r\nelse if K > root.leftElements\r\n   K = K - (root.leftElements + 1)\r\n   root = root.right\r\n   goto start\r\nelse\r\n   root = root.left\r\n   goto srart\r\n\r\nstop:<\/pre>\n<p><strong>Implementation:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%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\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>C Program Find k-th smallest element in BST &#8211; Binary Search Tree &#8211; Given root of binary search tree and K as input<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80126,69866,1],"tags":[81338,81341,81336,81339,81340,81334,81337,81331,81335,81332,81333,81330],"class_list":["post-27276","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree","category-c-programming","category-coding","tag-algorithm-to-find-pair-of-numbers-whose-sum-is-equal-to-k","tag-c-program-find-k-th-smallest-element-in-bst","tag-find-all-triplets-in-an-array-whose-product-is-a-given-number","tag-find-kth-smallest-and-kth-largest-element-in-bst","tag-find-kth-smallest-element-in-binary-search-tree","tag-find-the-second-largest-element-in-a-binary-search-tree","tag-given-an-array-and-a-number-k","tag-kth-largest-element-in-bst-java","tag-kth-smallest-element-in-a-array","tag-kth-smallest-element-in-a-bst-c","tag-kth-smallest-element-in-a-bst-recursive","tag-kth-smallest-element-in-bst-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27276","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27276"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27276\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27276"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27276"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27276"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}