Kth Smallest Element in BST in DSA Java - Build from Scratch

Kth Smallest Element in BST

📖 Scenario: You are working with a simple phone book application that stores contacts in a special tree called a Binary Search Tree (BST). Each contact has a unique number. You want to find the contact with the kth smallest number quickly.

🎯 Goal: Build a Java program that creates a BST with given numbers, sets a value for k, finds the kth smallest number in the BST, and prints it.

📋 What You'll Learn

Create a BST by inserting nodes with exact values: 5, 3, 7, 2, 4, 6, 8

Create a variable k with the value 3

Implement a method kthSmallest to find the kth smallest element in the BST

Print the kth smallest element

💡 Why This Matters

🌍 Real World

Finding the kth smallest element in a BST is useful in databases and search engines where sorted data retrieval is needed efficiently.

💼 Career

Understanding BST operations and traversal techniques is important for software engineering roles involving data structures and algorithms.

1

Create the BST with given nodes

Create a class TreeNode with an integer val, and left and right child nodes. Then create a class BST with a method insert to add nodes. In the main method, create a BST object called tree and insert nodes with values 5, 3, 7, 2, 4, 6, and 8 in this order.

DSA Java

// Define TreeNode class
// Define BST class with insert method
// In main, create BST and insert nodes
// Your code here

Hint

Start by defining the TreeNode class with value and child nodes. Then create the BST class with an insert method that adds nodes correctly. Finally, in main, create the tree and insert the exact values given.

2

Set the value of k

In the main method, create an integer variable called k and set it to 3.

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
        left = right = null;
    }
}

class BST {
    TreeNode root;

    void insert(int val) {
        root = insertRec(root, val);
    }

    TreeNode insertRec(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
            return root;
        }
        if (val  root.val) {
            root.right = insertRec(root.right, val);
        }
        return root;
    }
}

public class Main {
    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(5);
        tree.insert(3);
        tree.insert(7);
        tree.insert(2);
        tree.insert(4);
        tree.insert(6);
        tree.insert(8);
        
        // Create an integer variable k and set it to 3
        // Your code here
    }
}

Hint

Just add int k = 3; inside the main method after inserting nodes.

3

Implement the kthSmallest method

In the BST class, implement a method int kthSmallest(TreeNode root, int k) that returns the kth smallest element in the BST using an inorder traversal. Use a helper method or variables as needed.

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
        left = right = null;
    }
}

class BST {
    TreeNode root;

    void insert(int val) {
        root = insertRec(root, val);
    }

    TreeNode insertRec(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
            return root;
        }
        if (val  root.val) {
            root.right = insertRec(root.right, val);
        }
        return root;
    }

    // Implement kthSmallest method here
    // Your code here
}

public class Main {
    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(5);
        tree.insert(3);
        tree.insert(7);
        tree.insert(2);
        tree.insert(4);
        tree.insert(6);
        tree.insert(8);
        
        int k = 3;
    }
}

Hint

Use an inorder traversal to visit nodes in ascending order. Keep a count of visited nodes. When count equals k, save the node's value as the result.

4

Print the kth smallest element

In the main method, call kthSmallest on the tree object with tree.root and k, store the result in an integer variable answer, and print answer.

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
        left = right = null;
    }
}

class BST {
    TreeNode root;

    void insert(int val) {
        root = insertRec(root, val);
    }

    TreeNode insertRec(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
            return root;
        }
        if (val  root.val) {
            root.right = insertRec(root.right, val);
        }
        return root;
    }

    private int count = 0;
    private int result = -1;

    int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }

    void inorder(TreeNode node, int k) {
        if (node == null) return;
        inorder(node.left, k);
        count++;
        if (count == k) {
            result = node.val;
            return;
        }
        inorder(node.right, k);
    }
}

public class Main {
    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(5);
        tree.insert(3);
        tree.insert(7);
        tree.insert(2);
        tree.insert(4);
        tree.insert(6);
        tree.insert(8);
        
        int k = 3;
        
        // Call kthSmallest and print the result
        // Your code here
    }
}

Hint

Call tree.kthSmallest(tree.root, k), save it in answer, then print answer.

Practice

1. What does the term kth smallest element in a BST mean?

easy

A. The element with the kth highest frequency in the BST

B. The element that appears in the kth position when BST elements are sorted in ascending order

C. The element at the kth level of the BST

D. The element with the kth largest value in the BST

Solution

1. Step 1: Understand BST property

   A Binary Search Tree (BST) stores elements so that left child is smaller and right child is larger.

2. Step 2: Define kth smallest element

   The kth smallest element is the one that appears in the sorted order at position k.

3. Final Answer:

   The element that appears in the kth position when BST elements are sorted in ascending order -> Option B

4. Quick Check:

   kth smallest = kth in ascending order [OK]

Hint: Think of inorder traversal to get sorted order [OK]

Common Mistakes:

• Confusing kth smallest with kth largest
• Thinking kth smallest means kth level node
• Mixing frequency with element order

2. Which of the following Java method signatures correctly represents a function to find the kth smallest element in a BST?

easy

A. public int kthSmallest(TreeNode root, int k)

B. public void kthSmallest(TreeNode root, int k)

C. public TreeNode kthSmallest(int k, TreeNode root)

D. public int kthSmallest(int k)

Solution

1. Step 1: Check method parameters and return type

   The method should accept the BST root and integer k, and return the kth smallest element as int.

2. Step 2: Match signature with correct order

   public int kthSmallest(TreeNode root, int k) matches: returns int, parameters (TreeNode root, int k).

3. Final Answer:

   public int kthSmallest(TreeNode root, int k) -> Option A

4. Quick Check:

   Return type int and parameters (root, k) [OK]

Hint: Return the element value, input root and k [OK]

Common Mistakes:

• Using void return type instead of int
• Swapping parameter order incorrectly
• Missing root parameter

3. What will be the output of the following code snippet to find the 3rd smallest element in the BST?

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int v) { val = v; }
}

public class Solution {
  int count = 0;
  int result = -1;
  public int kthSmallest(TreeNode root, int k) {
    inorder(root, k);
    return result;
  }
  private void inorder(TreeNode node, int k) {
    if (node == null) return;
    inorder(node.left, k);
    count++;
    if (count == k) {
      result = node.val;
      return;
    }
    inorder(node.right, k);
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(5);
    root.left = new TreeNode(3);
    root.right = new TreeNode(6);
    root.left.left = new TreeNode(2);
    root.left.right = new TreeNode(4);
    root.left.left.left = new TreeNode(1);
    Solution sol = new Solution();
    System.out.println(sol.kthSmallest(root, 3));
  }
}

medium

A. 5

B. 2

C. 4

D. 3

Solution

1. Step 1: Perform inorder traversal to get sorted elements

   Inorder traversal order: 1, 2, 3, 4, 5, 6.

2. Step 2: Identify the 3rd element in sorted order

   The 3rd smallest element is 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Sorted BST elements = [1,2,3,4,5,6], 3rd = 3 [OK]

Hint: Inorder traversal gives sorted order; pick kth element [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Off-by-one error in counting
• Returning node instead of node value

4. Identify the bug in the following code that attempts to find the kth smallest element in a BST:

public int kthSmallest(TreeNode root, int k) {
  int count = 0;
  int result = -1;
  inorder(root, k, count, result);
  return result;
}

private void inorder(TreeNode node, int k, int count, int result) {
  if (node == null) return;
  inorder(node.left, k, count, result);
  count++;
  if (count == k) {
    result = node.val;
    return;
  }
  inorder(node.right, k, count, result);
}

medium

A. Primitive variables count and result are passed by value, so changes don't persist

B. The inorder traversal is missing the base case

C. The method should return void instead of int

D. The count variable should be reset to zero inside inorder

Solution

1. Step 1: Understand Java parameter passing

   Primitive types like int are passed by value, so changes inside methods don't affect original variables.

2. Step 2: Identify impact on count and result

   Since count and result are passed by value, their updates inside inorder do not persist outside, causing incorrect result.

3. Final Answer:

   Primitive variables count and result are passed by value, so changes don't persist -> Option A

4. Quick Check:

   Primitive int passed by value, no update outside method [OK]

Hint: Use class fields or wrappers to persist count and result [OK]

Common Mistakes:

• Assuming primitives are passed by reference
• Not using class variables or arrays for count/result
• Ignoring base case in recursion

5. Given a BST where nodes can have duplicate values, how would you modify the standard kth smallest element algorithm to correctly find the kth smallest unique element?

hard

A. Count all nodes including duplicates normally during inorder traversal

B. Use preorder traversal instead of inorder traversal

C. Use inorder traversal and skip duplicates by comparing current node value with previous visited value

D. Store all values in a list and sort it to find kth unique element

Solution

1. Step 1: Understand duplicates in BST

   Duplicates appear as repeated values; inorder traversal lists them in sorted order including duplicates.

2. Step 2: Modify traversal to skip duplicates

   Track previous visited value; only increment count when current value differs to count unique elements.

3. Step 3: Find kth unique element

   Increment count only for unique values; when count == k, return current node value.

4. Final Answer:

   Use inorder traversal and skip duplicates by comparing current node value with previous visited value -> Option C

5. Quick Check:

   Skip duplicates by comparing with previous value during inorder [OK]

Hint: Track previous value to count unique elements only [OK]

Common Mistakes:

• Counting duplicates as separate elements
• Using preorder traversal which is not sorted
• Sorting all values outside traversal (inefficient)