Table of Contents

## Problem Statement

“K’th Largest element in BST using constant extra space” states that you are given a binary search tree and you need to find the kth largest element in it. So if we arrange the elements of the binary search tree in descending order then we need to return the kth number from the sequence.

## Example

k=4

3

Explanation: If the elements are arranged in the descending order, the sequence is [6, 5, 4, 3, 2, 1]. Now the fourth largest element is the element at the fourth index that is 3.

## Approach to find K’th Largest element in BST using constant extra space

### Naive approach

We can solve this problem by first storing the inorder traversal and then finding the n-k+1 element in the sequence will result in the answer to the problem. But this approach will have O(N) space complexity. We also discussed a more efficient solution where we did a reverse inorder traversal and kept a count for the number of nodes. While counting the nodes we were also checking if we node count is equal to k. If the node count is equal to k, we return the node. Else, in the end, we return a message that the kth largest node is not found.

### Efficient Approach

In the previous approach, we used reverse inorder traversal which required O(H) space for recursion. We can do the same thing as we did with the inorder traversal. As we reversed the inorder traversal. We will use Morris traversal for doing the inorder traversal in O(1) space. but instead of simply doing this we will do the reverse in-order traversal using Morris Traversal.

Morris Traversal is used on the binary threaded tree, the binary threaded tree is nothing but a binary tree having an extra thread. This makes it easier to perform traversal on the tree. Reverse Morris Traversal is just Morris Traversal but in a reverse manner. In normal morris traversal, we would have first moved to left subtree and then to right subtree. But here first we move to right subtree and then to left subtree. This way can perform the traversal in descending order. And then we return the kth element from the start. That is we keep a count and when the count is equal to k we return that element.

## Code

### C++ code to find K’th Largest element in BST using constant extra space

#include <bits/stdc++.h> using namespace std; struct node{ int data; node *left; node *right; } ; node* create(int data){ node * tmp = new node(); tmp->data = data; tmp->left = tmp->right = NULL; return tmp; } // normally insert the node in BST node* insert(node* root, int x) { if (root == NULL) return create(x); if(x<root->data) root->left = insert(root->left, x); else if(x>root->data) root->right = insert(root->right, x); return root; } node* findKthLargest(node* root, int k) { node *cur = root; node* kLargest = NULL; int cnt = 0; while(cur != NULL){ // if right subtree is NULL, then move to left subtree if(cur->right == NULL){ // if current node is kth largest if(cnt == k-1) kLargest = cur; cnt++; // move to the left subtree cur = cur->left; } else{ // to find successor of current node node* successor = cur->right; while(successor->left != NULL && successor->left != cur) successor = successor->left; if(successor->left == NULL){ // set current node as left child of successor as it doesn't have left child successor->left = cur; cur = cur->right; } else{ // remove threads to restore the original tree successor->left = NULL; if(cnt == k-1) kLargest = cur; cnt++; cur = cur->left; } } } return kLargest; } int main() { node *root = NULL; int n;cin>>n; for(int i=0;i<n;i++){ int element;cin>>element; root = insert(root, element); } int k;cin>>k; node* res = findKthLargest(root, k); if(res == NULL) cout<<"No kth largest found"; else cout<<"Kth largest element is "<<res->data; }

6 3 2 1 5 4 6 4

Kth largest element is 3

### Java code to find K’th Largest element in BST using constant extra space

import java.util.*; import java.lang.*; import java.io.*; class node{ int data; node left; node right; } class Tree{ static node root; static int count; static node create(int data){ node tmp = new node(); tmp.data = data; tmp.left = null; tmp.right = null; return tmp; } static node insert(node root, int x) { if (root == null) return create(x); if(x<root.data) root.left = insert(root.left, x); else if(x>root.data) root.right = insert(root.right, x); return root; } static node findKthLargest(node root, int k) { node cur = root; node kLargest = null; int cnt = 0; while(cur != null){ // if right subtree is NULL, then move to left subtree if(cur.right == null){ // if current node is kth largest if(cnt == k-1) kLargest = cur; cnt++; // move to the left subtree cur = cur.left; } else{ // to find successor of current node node successor = cur.right; while(successor.left != null && successor.left != cur) successor = successor.left; if(successor.left == null){ // set current node as left child of successor as it doesn't have left child successor.left = cur; cur = cur.right; } else{ // remove threads to restore the original tree successor.left = null; if(cnt == k-1) kLargest = cur; cnt++; cur = cur.left; } } } return kLargest; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for(int i=0;i<n;i++){ int element = sc.nextInt(); root = insert(root, element); } int k = sc.nextInt(); count = 0; node res = findKthLargest(root, k); if(res == null) System.out.println("No kth largest found"); else System.out.println("Kth largest element is "+res.data); } }

6 3 2 1 5 4 6 4

Kth largest element is 3

## Complexity Analysis

### Time Complexity

**O(N)**, because we have once traversed over all the elements of the tree. The time complexity is linear i.e. O(N).

### Space Complexity

**O(1)**, because we have used morris traversal instead of doing the traversal recursively.