Kth Smallest Element in a BST
Credit to leetcode.com, this is a fun problem that with some understanding of the data structure (Binary Search Trees) can be solved relatively straightforward. Here it is:
Given a binary search tree, write a function
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
The key insight is that if you traverse an BST using an in-order method, the elements of the tree will be, as the name implies, in-order, that is, they will be already sorted. Remember the 3 basic traversal orders:
Pre-Order:
Given a binary search tree, write a function
kthSmallest to find the kth smallest element in it.Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
The key insight is that if you traverse an BST using an in-order method, the elements of the tree will be, as the name implies, in-order, that is, they will be already sorted. Remember the 3 basic traversal orders:
Pre-Order:
- Process current node
- Process left node
- Process right node
Post-Order:
- Process the left node
- Process the right node
- Process the current node
In-Order:
- Process the left node
- Process the current node
- Process the right node
So for this problem we'll traverse the tree in-order keeping a counter whenever we process the current node. The moment the counter gets to "k", we have found our element. Some minor checks to quit processing once we have found the solution (although that may not be necessary if we put some thought in it). Hope you enjoy!!!
public class Solution
{
public int KthSmallest(TreeNode root, int k)
{
int retVal = -1;
int currentIndex = 0;
KthSmallestInternal(root, ref currentIndex, k, ref retVal);
return retVal;
}
{
public int KthSmallest(TreeNode root, int k)
{
int retVal = -1;
int currentIndex = 0;
KthSmallestInternal(root, ref currentIndex, k, ref retVal);
return retVal;
}
private bool KthSmallestInternal(TreeNode root, ref int currentIndex, int k, ref int retVal)
{
if (root == null) return false;
if (KthSmallestInternal(root.left, ref currentIndex, k, ref retVal)) return true;
currentIndex++;
if (currentIndex == k)
{
retVal = root.val;
return true;
}
if (KthSmallestInternal(root.right, ref currentIndex, k, ref retVal)) return true;
return false;
}
}
{
if (root == null) return false;
if (KthSmallestInternal(root.left, ref currentIndex, k, ref retVal)) return true;
currentIndex++;
if (currentIndex == k)
{
retVal = root.val;
return true;
}
if (KthSmallestInternal(root.right, ref currentIndex, k, ref retVal)) return true;
return false;
}
}
Marcelo
Comments
Very concise and classical solution! In practice though, it can be slightly improved by using an explicit stack instead of implicit function invocation stack, since its limit is easier to control and less information would have to be stored on it. The version with explicit stack is usually called "imperative" and is a fun exercise :)
Reply DeletePost a Comment
[γγ¬γΌγ ]