K'th Largest Element in BST when modification to BST is not allowed - GeeksforGeeks
Given a Binary Search Tree (BST) and a positive integer k, find the k'th largest element in the Binary Search Tree.
O(h+k)
Find k-th smallest element in BST (Order Statistics in BST)
Read full article from K'th Largest Element in BST when modification to BST is not allowed - GeeksforGeeks
Given a Binary Search Tree (BST) and a positive integer k, find the k'th largest element in the Binary Search Tree.
O(h+k)
Time complexity: The code first traverses down to the rightmost node which takes O(h) time, then traverses k elements in O(k) time. Therefore overall time complexity is O(h + k).
The idea is to do reverse inorder traversal of BST. The reverse inorder traversal traverses all nodes in decreasing order. While doing the traversal, we keep track of count of nodes visited so far. When the count becomes equal to k, we stop the traversal and print the key.
// A function to find k'th largest element in a given tree.void kthLargestUtil(Node *root, int k, int &c){ // Base cases, the second condition is important to // avoid unnecessary recursive calls if (root == NULL || c >= k) return; // Follow reverse inorder traversal so that the // largest element is visited first kthLargestUtil(root->right, k, c); // Increment count of visited nodes c++; // If c becomes k now, then this is the k'th largest if (c == k) { cout << "K'th largest element is " << root->key << endl; return; } // Recur for left subtree kthLargestUtil(root->left, k, c);}// Function to find k'th largest elementvoid kthLargest(Node *root, int k){ // Initialize count of nodes visited as 0 int c = 0; // Note that c is passed by reference kthLargestUtil(root, k, c);}
Method 1: Using Inorder Traversal.
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
node_t *k_smallest_element_inorder(stack_t *stack, node_t *root, int k){ stack_t *st = stack; node_t *pCrawl = root; /* move to left extremen (minimum) */ while( pCrawl ) { push(st, pCrawl); pCrawl = pCrawl->left; } /* pop off stack and process each node */ while( pCrawl = pop(st) ) { /* each pop operation emits one element in the order */ if( !--k ) { /* loop testing */ st->stackIndex = 0; break; } /* there is right subtree */ if( pCrawl->right ) { /* push the left subtree of right subtree */ pCrawl = pCrawl->right; while( pCrawl ) { push(st, pCrawl); pCrawl = pCrawl->left; } /* pop off stack and repeat */ } } /* node having k-th element or NULL node */ return pCrawl;}
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.
int k_smallest_element(node_t *root, int k){ int ret = -1; if( root ) { /* A crawling pointer */ node_t *pTraverse = root; /* Go to k-th smallest */ while(pTraverse) { if( (pTraverse->lCount + 1) == k ) { ret = pTraverse->data; break; } else if( k > pTraverse->lCount ) { /* There are less nodes on left subtree Go to right subtree */ k = k - (pTraverse->lCount + 1); pTraverse = pTraverse->right; } else { /* The node is on left subtree */ pTraverse = pTraverse->left; } } } return ret;}