230. Kth Smallest Element in a BST

Problem Description

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.

Intuition

Binary Tree

In BST, all nodes in the left subtree are smaller than the root. So if the left subtree has L nodes, the root is the (L+1)th smallest. We can use this to decide whether to go left, return current, or go right.
inorder

In BST, an inorder traversal visits nodes in sorted order, so the kth node visited is the kth smallest element.

Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// BST
int kthSmallest(TreeNode* root, int k) {
	while (root != nullptr) {
		int leftCount = countTreeNode(root->left);
		
		if (k == leftCount + 1) {
			return root->val;
		} else if (k <= leftCount) {
			root = root->left;
		} else {
			k = k - leftCount - 1;
			root = root->right;
		}
	}
	return -1;
}

int countTreeNode(TreeNode* root) {
	if (root == nullptr) return 0;
	return countTreeNode(root->left) + countTreeNode(root->right) + 1;
}


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

// left mid right
void inorder(TreeNode* root, int& k, int& count, int& result){
	if(root == nullptr){
	return;
	}
	inorder(root->left, k, count, result);
	if (++count == k) {
		result = root->val;
		return;
	}
	inorder(root->right, k, count, result);
}