Kth Smallest Element in a Binary Search Tree

Given a binary search tree,

find the kth smallest element in it.

For example,

For the below tree:

source: leetcode.com

If k = 3,

Then the kth (3rd) smallest element is 3.

If k = 2,

Then the output is 2.

Try out the solution here:

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Solution:

Hint :

Use inorder traversal.

Explanation:

Approach 1 – Recursive Inorder traversal with additional data structure

Inorder traversal traverses a tree from the left and then the root and the right.

The direction goes like this:

Left -> Root -> Right.

So if you represent a binary search tree in inorder , the elements will be naturally arranged in sorted order.

Let’s make us of this property to solve our problem.

Represent the given BST in inorder form.

Then pick the k th element from the start.

To do this , let’s first store the element values as we do inorder in a list.

Once the traversal is complete , the list will contain all the elements of the BST in sorted order.

We can then pick up the kth element from the list.

Here is the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    
    List<Integer> o = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        
        
        inorder(root);
        
        
        return o.get(k-1);
    }
    
    public void inorder(TreeNode node){
        
        if(node == null) return;
        
        inorder(node.left);
      
        
        o.add(node.val);

        
        inorder(node.right);
    }
}

As you see , we create a global list to store all the elements in the BST .

For the traversal , we write a recursive function.

The base condition of this function is to return if the node is null (we have reached a leaf of the tree).

Otherwise you first do a recursive call on the left node of the root node.

And then you add the current node to the list (by this time we would have reached the left most leaf of the tree because of the previous recursive call on the left node).

And then you do a recursive call on the right node of the root node.

Time complexity:

Since we traverse through all the nodes time complexity is O(n)

Space complexity:

We use an extra data structure (list) to store the nodes.

We also have stack memory for the recursive calls.

So space complexity is O(2n) which is equal to O(n)

Approach 2 – Recursive Inorder Traversal without additional data structure

In this approach we are going to follow a similar algorithm as approach 1.

The only difference is we are not going to use the list data structure to store the elements.

We will keep a global counter in this approach.

And then increment this counter , once we reach the leftmost bottom most leaf of the tree (smallest element).

Once the counter matches the given k value we return the node.

Here is the modified recursive call without the extra space complexity other than the recursive stack memory:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    
    
    
    int count = 0;
    public int kthSmallest(TreeNode root, int k) {
        
        
       TreeNode node =  inorder(root,k);
        
        return node.val;
       
    }
    
    public TreeNode inorder(TreeNode node,int k){
        
        if(node == null) return null;
        
        TreeNode left = inorder(node.left,k);
        
        if(left != null) return left;
      
 
        count++;
        
        if(count == k) return node;
        
        
       return inorder(node.right,k);
    }
}

Time complexity:

We don’t traverse through all the nodes in this case.

We first reach the bottom most left most leaf of the tree which represents the height of the tree H.

And then we keep moving till we find the kth element. During this move too , we will move along the height of the tree .

So time complexity is O(H + k)

Space complexity:

We don’t use the extra list data structure.

Still there is memory required for the recursive call.

The recursive call happens for all the nodes along the left path till we reach the bottom left leaf of the tree.

And then for the k nodes till we find out the kth smallest element. We might also branch out a bit while finding the k nodes.

These k nodes will be less than or equal to H in the worst case .

Also we keep popping nodes while finding these k nodes.

So we can ignore them during space complexity

So space complexity is also O(H)

Approach 3 – Using Stack

Instead of recursion we can also use a stack to simulate the recursion.

In this case you push the nodes to the stack until you reach the left bottom of the tree.

Then you pop the topmost node , consider that node for the output.

And then you move right and repeat the above steps.

Here is the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    
    
    public int kthSmallest(TreeNode root, int k) {
    
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        
   
        while(true){
        
        while(root != null){
            
            stack.push(root);
            
            root = root.left;
        }
        
            
            root = stack.pop();
        k--;
            
        
        
        if(k==0) return root.val;
        
        
        root = root.right;
        }
        
        
        
        
        
    }
}

As you see we keep pushing the left nodes of the tree until we reach the bottom left leaf.

Then we pop the top node (initially this represents the smallest).

Every time we pop the top node we decrement k value.

So when k reaches zero it means you have considered k small values and you can return the current node value.

After popping the top node each time you branch right and continue the above steps.

Time complexity:

Since we push elements till we reach the left bottom of the tree (which represents the height of the tree H) ,

And we pop k elements , the time complexity is O( H + k)

Space complexity:

Space complexity is O(H) as the previous approach.

That’s it!


Posted

in

, ,

by

Comments

Leave a Reply

Discover more from The Full Stack Developer

Subscribe now to keep reading and get access to the full archive.

Continue reading