Kth Smallest Element in a BST Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Citadel eBay Facebook Google LinkedIn Microsoft Oracle Uber VMwareViews 3546

Problem Statement

Kth Smallest Element in a BST Leetcode Solution – Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Examples:

Kth Smallest Element in a BST Leetcode Solution

Input:

 root = [3,1,4,null,2], k = 1

Output:

 1

 

Kth Smallest Element in a BST Leetcode Solution

Input:

 root = [5,3,6,2,4,null,null,1], k = 3

Output:

 3

Explanation:

The 3rd smallest number in the given BST is 3, so we output 3.

Approach

  • The binary tree consists of elements in sorted order.
  • The easiest way of finding the solution is to insert the elements in the priority queue and then pop out k-1 elements, then the top element of the priority queue is the kth smallest element of the tree.
  • The optimized solution is doing in-order traversal and keeping track of the count of the number of elements visited.
  •  After visiting the leftmost element of the binary tree, increase the count to 1 and traverse back in an in-order manner and increase the count.
  • Whenever the count is reached to k return that element.

Idea:

The idea is to traverse the BST in an inorder fashion, as the inorder traversal of BST is sorted in increasing order we can maintain a count, whenever that count becomes equal to k, we have found our Kth smallest element so we return it.

To traverse the BST in an inorder traversal, we can use a stack. Firstly we traverse to the leftmost node inserting each node into the stack until we find a null, then one by one pop elements from the stack and go to the right of that popped node.

Code For Kth Smallest Element In BST

C++ Code

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        
        stack<TreeNode*> st;
        // stack to store the node pointers.
        
        while(true){
            
            while(root!=NULL){
                st.push(root);
                root = root->left;
            }
            // traversing to the leftmost of a node and inserting it into stack.
            root = st.top();
            st.pop();
            k--;
            if(k==0){
                // if its Kth smallest then return it.
                return root->val;
            }
            
            root = root->right;
            //move to the next largest node which is at the right in BST.
        }
        
    }
};

Java Code

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        LinkedList<TreeNode> st = new LinkedList<>();
        // stack to store the node pointers.
        
        while(true){
            
            while(root!=null){
                st.push(root);
                root = root.left;
            }
            // traversing to the leftmost of a node and inserting it into stack.
            root = st.pop();
            k--;
            if(k==0){
                // if its Kth smallest then return it.
                return root.val;
            }
            
            root = root.right;
            //move to the next largest node which is at the right in BST.
        }
    }
}

Complexity Analysis For Kth Smallest Element in a BST Leetcode Solution

Time Complexity

Time complexity is O(H+k), where H is the height of the tree, Since before popping out elements from the stack we are going to the leaf node, and then we start to pop elements, so the overall time complexity is O(logn) for going till the leaf node, and additional O(k) time for finding the Kth smallest element. The overall time complexity is O(logn + k) for the balanced tree and O(N + k) for the Skewed tree.

Space Complexity

We are using an external space i.e stack, which at any time would not have the number of elements greater than the height of the tree,  So the overall space complexity is O(H).

 

Translate »