Posts Kth Smallest Element in a BST
Post
Cancel

Kth Smallest Element in a BST

PROBLEM DESCRIPTION

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.

Leetcode

SOLUTION

APPROACH 1

Store the inorder traversal in a list and return (k-1)th element from the list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {

    public int kthSmallest(TreeNode root, int k) {
        return inorder(root, new ArrayList<>()).get(k-1);
    }

    public List<Integer> inorder(TreeNode root, List<Integer> list){

        if(root == null)
            return list;

        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);

        return list;

    }

}

APPROACH 2 (Optimized)

We don’t need to traversal the entire list necessarily. Once we reach the Kth element, we should be returning it. This will be O(k) time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {

    public int kthsmallest(TreeNode A, int B) {

        //To store the value of K
        int[] k = new int[1];
        k[0] = B;

        TreeNode n = solve(A, k);

        //In case K is more than the number of nodes
        if(n != null)
            return n.val;
        return -1;

    }

    public TreeNode solve(TreeNode root, int[] k){

        if(root == null) return null;

         // We do an inorder traversal here.
        TreeNode left = solve(root.left, k);
        if (k[0] == 0)
            return left;    // left subtree has k or more elements.
        k[0]--;
        if(k[0] == 0){
            return root; // root is the kth element.
        }
        return solve(root.right, k);  // answer lies in the right node.
    }
}
This post is licensed under CC BY 4.0 by the author.