Published on

# kthSmallestInBST

Authors
• Name
Moch Lutfi
@kaptenupi

## Problem

Note: Your solution should have only one BST traversal and O(1) extra space complexity, since this is what you will be asked to accomplish in an interview.

A tree is considered a binary search tree (BST) if for each of its nodes the following is true:

1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. Both the left and the right subtrees must also be binary search trees.

Given a binary search tree t, find the $k^{th}$ smallest element in it.

Note that $k^{th}$ smallest element means $k^{th}$ element in increasing order. See examples for better understanding.

Example

• For

_21t = {_21 "value": 3,_21 "left": {_21 "value": 1,_21 "left": null,_21 "right": null_21 },_21 "right": {_21 "value": 5,_21 "left": {_21 "value": 4,_21 "left": null,_21 "right": null_21 },_21 "right": {_21 "value": 6,_21 "left": null,_21 "right": null_21 }_21 }_21}

and k = 4, the output should be
solution(t, k) = 5.

Here is what t looks like:

_5 3_5 / \_51 5_5 / \_5 4 6

The values of t are [1, 3, 4, 5, 6], and the $4^{th}$ smallest is 5.

• For

_17t = {_17 "value": 1,_17 "left": {_17 "value": -1,_17 "left": {_17 "value": -2,_17 "left": null,_17 "right": null_17 },_17 "right": {_17 "value": 0,_17 "left": null,_17 "right": null_17 }_17 },_17 "right": null_17}

and k = 1, the output should be
solution(t, k) = -2.

Here is what t looks like:

_5 1_5 /_5 -1_5 / \_5-2 0

The values of t are [-2, -1, 0, 1], and the $1^{st}$ smallest is -2.

## Solution

DFS or BFS? BFS starts visiting nodes from root while DFS starts visiting nodes from leaves. So if our problem is to search something that is more likely to closer to root, we would prefer BFS. And if the target node is close to a leaf, we would prefer DFS.

We can use inOrder traversal because the goals is finding $k^{th}$ value from sorted data.

1. Create an empty slice as stack
2. Initialize current node as root
3. If current is NULL and stack is not empty then
• Push the current node to S and set current = current->left until current is NULL
• Pop the top item from stack.
• Reduce k by 1 and return current value if k==0
• Set current = popped_item->right
• Go to step 3.
4. If current is NULL and stack is empty then we are done.
solution.go
_20func solution(t *Tree, k int) int {_20 stack:=[]*Tree{}_20 current:=t_20_20 for current!=nil || len(stack)>0{_20 for current!=nil{_20 stack = append(stack, current)_20 current = current.Left_20 }_20 current = stack[len(stack)-1]_20 stack = stack[:len(stack)-1]_20 k--_20 if k==0{_20 return current.Value.(int)_20 }_20 current = current.Right_20 }_20 _20 return -1_20}