Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

		  3
		/    \
	   /      \
	  1        4
	    \     /  
	     \   /    
          2

1
2

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

                  5
                /    \
               /      \
              3        6
             /  \     
            /    \    
           2     4       
          /
         /
        1

1
2

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

Solution

Method 1 - Inorder Traversal Recursive

Code

 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

public int findKthSmallest(TreeNode root, int k) {
	// counter tracks visited nodes
	// `AtomicInteger` is used as`Integer` is passed by value in Java
	// OR use some wrapper class
	AtomicInteger counter = new AtomicInteger(0);
	TreeNode kthNode = helper(root, k, counter);
	return  kthNode == null? -1: kthNode.val;
}
public TreeNode helper(TreeNode root,int k,AtomicInteger counter) {
	if (root == null) {
		return null;
	}

	TreeNode left = helper(root.left, k, counter);

	// if k'th smallest node is found
	if (left != null) {
		return left;
	}

	// if the root is k'th smallest node
	if (counter.incrementAndGet() == k) {
		return root;
	}

	return helper(root.right, k, counter);
}

Method 2 - Inorder Traversal Iterative 🏆

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public int getNthIterative(TreeNode root, int k) {
	if (root == null) {
		return -1;
	}
	Stack<TreeNode> stack = new Stack<>();
	TreeNode curr = root;

	while (!stack.isEmpty() || curr != null) {
		if (curr != null) {
			stack.push(curr);
			curr = curr.left;
		} else {
			TreeNode node = stack.pop();
			k--;
			if (k == 0) {
				return node.val;
			}
			curr = node.right;
		}
	}
	return -1;
}