k-th Smallest in BST

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Find kth smallest element in BST. In-order traversal (left-root-right) yields sorted order.

Algorithm

1In-order traversal with counter. When counter reaches k: return current node value.

Common Pitfalls

•Same as LC 230. Iterative in-order with stack or Morris traversal for O(1) space.

k-th Smallest in BST.java

Java

// Approach: In-order traversal (left-root-right) yields sorted order. Return the k-th element visited.
// Time: O(n) Space: O(h)
import java.util.*;

class Node {
    int data;
    Node left, right;

    public Node(int d) {
        data = d;
        left = right = null;
    }
}

class Solution {
    // Return the Kth smallest element in the given BST
    public int kthSmallest(Node root, int k) {
        ArrayList<Integer> arr = new ArrayList<>();
        solve(root, arr);
        if (k <= arr.size()) {
            for (int i = 0; i < arr.size(); i++) {
                if (i == k - 1)
                    return arr.get(i);
            }
        }

        return -1;
    }

    public void solve(Node root, ArrayList<Integer> arr) {
        if (root == null)
            return;

        solve(root.left, arr);
        arr.add(root.data);
        solve(root.right, arr);
    }
}

Was this solution helpful?