LeetCode Meditations: Kth Smallest Element in a BST
Let's start with the description for Kth Smallest Element in a BST:
Given the
rootof a binary search tree, and an integerk, return thekthsmallest value (1-indexed) of all the values of the nodes in the tree.
For example:
Input: root = [3, 1, 4, null, 2], k = 1
Output: 1
Input: root = [3, 1, 4, null, 2], k = 1
Output: 1
Or:
Input: root = [5, 3, 6, 2, 4, null, null, 1], k = 3
Output: 3
Input: root = [5, 3, 6, 2, 4, null, null, 1], k = 3
Output: 3
This problem naturally lends itself to a neat recursive solution using a neat traversal algorithm.
Remember inorder traversal that gives us the values in a binary search tree in order? Exactly.
Here, we can use it to build a stack called values, and get the kth item (1-indexed of course, as the problem description states):
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val === undefined ? 0 : val)
* this.left = (left === undefined ? null : left)
* this.right = (right === undefined ? null : right)
* }
* }
*/
function kthSmallest(root: TreeNode | null, k: number): number {
let values = [];
function inorderWalk(node: TreeNode | null) {
if (node === null || values.length === k) {
return;
}
inorderWalk(node.left);
values.push(node.val);
inorderWalk(node.right);
}
inorderWalk(root);
return values[k - 1];
}
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val === undefined ? 0 : val)
* this.left = (left === undefined ? null : left)
* this.right = (right === undefined ? null : right)
* }
* }
*/
function kthSmallest(root: TreeNode | null, k: number): number {
let values = [];
function inorderWalk(node: TreeNode | null) {
if (node === null || values.length === k) {
return;
}
inorderWalk(node.left);
values.push(node.val);
inorderWalk(node.right);
}
inorderWalk(root);
return values[k - 1];
}
Time and space complexity
The time complexity is going to be because we traverse the whole tree and visit each node once. The space complexity is also as we keep a stack that holds all the nodes.
That was a simple and elegant solution, but let's now take a breath and look at another solution that uses an iterative version of the inorder traversal:
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val === undefined ? 0 : val)
* this.left = (left === undefined ? null : left)
* this.right = (right === undefined ? null : right)
* }
* }
*/
function kthSmallest(root: TreeNode | null, k: number): number {
let stack = [];
let currentNode = root;
while (k > 0) {
while (currentNode !== null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
k--;
if (k === 0) {
return currentNode.val;
}
currentNode = currentNode.right;
}
}
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val === undefined ? 0 : val)
* this.left = (left === undefined ? null : left)
* this.right = (right === undefined ? null : right)
* }
* }
*/
function kthSmallest(root: TreeNode | null, k: number): number {
let stack = [];
let currentNode = root;
while (k > 0) {
while (currentNode !== null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
k--;
if (k === 0) {
return currentNode.val;
}
currentNode = currentNode.right;
}
}
Here, we go as deep as we can in the left subtree, adding the nodes to our stack as we go. Once we reach a node that doesn't have a left child, we pop from the stack. Each time we do so, we'll be getting the values in sorted order.
Once we pop the kth time, we'll return the value of the current node and be done with it. Otherwise, we'll go to the right subtree.
Time and space complexity
The time complexity is because in the worst case where k is , we'll end up visiting each node. The space complexity will be —where is the height of the tree—because in the worst case, we'll store all the nodes from the root to the deepest leaf node.
The next problem is called Construct Binary Tree from Preorder and Inorder Traversal. Yet another mouthful title, but we'll survive. Until then, happy coding.