TIC
The Interns Company

Kth Smallest Element in a BST

MediumAcceptance: 65.7%
TreeDepth-First SearchBinary Search TreeBinary Tree

Problem Statement

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.

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4

Input Format:

  • The root of a binary search tree
  • An integer k

Output Format:

  • Return the kth smallest element in the BST

Examples:

Example 1:

Input:

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

Output:

1

Explanation:

The tree is: 3 / \ 1 4 \ 2 The 1st smallest element is 1.

Example 2:

Input:

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

Output:

3

Explanation:

The tree is: 5 / \ 3 6 / \ 2 4 / 1 The 3rd smallest element is 3.

Solutions

Recursive In-Order Traversal

Time: O(n) where n is the number of nodes in the tree
Space: O(h) where h is the height of the tree (due to recursion stack)

Use recursive in-order traversal to visit nodes in ascending order. The kth node visited will be the kth smallest element.

Iterative In-Order Traversal

Time: O(h + k) where h is the height of the tree and k is the input parameter
Space: O(h) where h is the height of the tree

Use an iterative approach with a stack to perform in-order traversal. Stop when the kth element is found to avoid unnecessary traversal.

Follow-Up: Optimized Solution with BST Property

Time: O(h) where h is the height of the tree
Space: O(h) for recursion stack

An optimized solution that maintains a count of nodes in the left subtree to avoid unnecessary traversals. This is useful when the tree structure doesn't change but the function is called multiple times.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Start in-order traversal at root node 3
  2. Recursively traverse to the left: node 1
  3. Node 1 has no left child, so process node 1 and add to result: [1]
  4. Move to the right child of node 1: node 2
  5. Node 2 has no left child, so process node 2 and add to result: [1, 2]
  6. Return to node 3 and process it: [1, 2, 3]
  7. Move to the right child of node 3: node 4
  8. Node 4 has no left child, so process node 4 and add to result: [1, 2, 3, 4]
  9. Complete in-order traversal result: [1, 2, 3, 4]
  10. Return the kth (1st) element: 1

Hints

Hint 1
Think about the properties of a Binary Search Tree (BST). In a BST, elements are ordered.
Hint 2
An in-order traversal of a BST gives nodes in ascending order.
Hint 3
Can you perform an in-order traversal and find the kth element visited?

Video Tutorial

Kth Smallest Element in a BST - In-Order Traversal

YouTube•Learn the Kth Smallest Element in a BST solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the in-order traversal of a BST to find the kth smallest element.

Key visualization elements:

  • current node
  • visited nodes
  • stack state
  • kth element found

Similar Questions

Validate Binary Search Tree

Medium

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

Asked By

AmazonMicrosoftFacebookGoogleUberBloomberg

Implementation Notes

This problem tests understanding of Binary Search Tree properties and tree traversal algorithms. The key insight is that an in-order traversal of a BST visits nodes in ascending order.