Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree
Tags: binarysearchtree, algorithms, javascript, codenewbie
Published: 2020-05-20 17:07:21

Today's algorithm is about binary search trees and traversing through them. Given a binary search tree, find the kth smallest element in that tree.

For example, let's say you're given this tree, and told to find the second smallest element (input - root = [3, 1, 4, null, 2], k = 2):
```
    3
  /   \
 1     4
  \
   2
```
The expected output would be 2, because the second smallest element in this tree is 2. (The Leetcode problem can be found [here](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)).

To tackle this problem, I'm going to build a sorted array, and return the element in the index representing the kth smallest number. To build a sorted array, I'll use depth first search, which means I will go all the way down one branch of a tree until I reach a null node, and then I'll go all the way down any other branches.

Because I think depth first search and recursion can be difficult to understand, and reading comments in code doesn't always explain it, I'll walk through the code first, and then I'll use an example to explain each element of it.

## Quick Refresher on Binary Search Trees
For a definition on binary search trees, I like the one provided by [Geeks For Geeks](https://www.geeksforgeeks.org/binary-search-tree-data-structure/):
> Binary Search Tree is a node-based binary tree data structure which has the following properties:
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.

## The Code
In the Leetcode problem, you're given a definition of a binary tree node, which has the properties of 'val', 'left', and 'right'. If a node does not have anything to the left or right of it, then they are 'null'.

The function `kthSmallest` is given a root, which represents the BST, and k, which is kth smallest number we're looking for. We can start out by initializing an empty array which will hold the sorted nodes. We also can include the final return statement. If we're looking for the second smallest element in the array `[1, 2, 3, 4]`, we would return 2, which is at the 1st index. So, we know that we want to return the element in the sorted array at the k-1 index.

```javascript
function kthSmallest(root, k) {
    let sortedArr = []
    //...
    return sortedArr[k-1]
};
```

Now, in this problem we will be calling a function from inside the function, using recursion to return values as needed. The first thing we can do is initialize the depth first search function, which will take in a node.

```javascript
function kthSmallest(root, k) {
    let sortedArr = []
    function dfs(node) {
        //...
    }
    //...
    return sortedArr[k-1]
};
```

Now, the definition of a binary tree is that the further left you go, the smaller the number you'll find. You can keep going left until there aren't any nodes remaining. That means that we can start our `dfs` function with an if statement--if the node you're checking is null, then return--you've gone too far.

```javascript
function kthSmallest(root, k) {
    let sortedArr = []
    function dfs(node) {
        if (!node) return
        //...
    }
    //...
    return sortedArr[k-1]
};
```
Now, we have a stopping point: going too far to the left. So, the next line in depth first search should be a recursive call to check the node to the left of the current node, using the property `.left`.

```javascript
function kthSmallest(root, k) {
    let sortedArr = []
    function dfs(node) {
        if (!node) return
        dfs(node.left)
        //...
    }
    //...
    return sortedArr[k-1]
};
```

At this point, if the left nodes have been checked, and we've hit the end of that branch, we can safely say that the left-most node we've found is the smallest number in the tree, so we can add its value to the sorted array.

```javascript
function kthSmallest(root, k) {
    let sortedArr = []
    function dfs(node) {
        if (!node) return
        dfs(node.left)
        sortedArr.push(node.val)
        //...
    }
    //...
    return sortedArr[k-1]
};
```

Since we've checked the left nodes, we now can move down to check the right nodes (which, by definition, are going to be larger). So, we can make another recursive call to the depth first search function with `node.right`.

```javascript
function kthSmallest(root, k) {
    let sortedArr = []
    function dfs(node) {
        if (!node) return
        dfs(node.left)
        sortedArr.push(node.val)
        dfs(node.right)
    }
    //...
    return sortedArr[k-1]
};
```

The final thing we have to do is call the dfs function with the given root. We can do this right after we declare the function.

```javascript
function kthSmallest(root, k) {
    let sortedArr = []
    function dfs(node) {
        if (!node) return
        dfs(node.left)
        sortedArr.push(node.val)
        dfs(node.right)
    }
    dfs(root)
    return sortedArr[k-1]
};
```

## An Explanation

If you're like me, the logic behind DFS's is a little confusing just by looking at the code, which is why I like to walk through an example.

If the given root were `[3, 1, 4, null, 2]`, the tree would look like this:

![binary search tree](https://dev-to-uploads.s3.amazonaws.com/i/o5g55ikk1sqjt877a4lh.png)


With depth first search, the way we're going to traverse the tree will follow this path:

![depth first search path through a binary search tree](https://dev-to-uploads.s3.amazonaws.com/i/lh41wrz8yt3uwgmdetwe.png)


The first thing we'll check is the root node, 3. It is a node, so we can skip that line. The next line is to call dfs on node.left, which means we'll check the left node of 1.

![calling dfs on 3, and then dfs on 1](https://dev-to-uploads.s3.amazonaws.com/i/kk1dska5wv1c5rmsxu51.png)

Now we'll check the node 1. It is a node, so we'll skip that line. We now will call dfs on the left of 1, which is null. Since that is not a node, we will return.

![there's nothing to the left of 1, so we can return that](https://dev-to-uploads.s3.amazonaws.com/i/o5jzj5v5kt34lbm1zvt3.png)


We're now brought back to checking 1. We can push 1 to the sorted array. 

![can push 1 to the sorted array](https://dev-to-uploads.s3.amazonaws.com/i/25i062s0esa79cfw1n2t.png)


We can now move on to checking the right node of 1, which is 2. 2 is a node, so we'll skip that line. We can now check the left of 2, which is null. Null is not a node, so we will return.

![calling dfs on 2 -- nothing to the left](https://dev-to-uploads.s3.amazonaws.com/i/3far4ehotgli0047had3.png)


We now can push 2 to the sorted array. We'll now check the right node of 2, which is null. Since null is not a node, we can return.

![can push 2 to the sorted array, and there's nothing to the right](https://dev-to-uploads.s3.amazonaws.com/i/q2as1ddlgks0dz7msl6d.png)


We're now done checking everything to the left of 3, which means we can push 3 to the sorted array.

![pushing 3 to the sorted array](https://dev-to-uploads.s3.amazonaws.com/i/thjyvz7e25ywww19k5cw.png)


Now we'll start by checking things to the right of three, beginning with 4. Since 4 is a node, we'll skip that line. We'll call the function on the left node of 4, which is null, so that will just return.

![calling dfs on 4, and there's nothing to the left](https://dev-to-uploads.s3.amazonaws.com/i/nikbs1qcxjh577zwunux.png)


Since there was nothing to the left of 4, we can just push 4 to the sorted array. Now, we can check the right of 4. There isn't a node to the right of 4, so that'll return.

![pushing 4 to the sorted array, and there's nothing to the right](https://dev-to-uploads.s3.amazonaws.com/i/0goicnzfkossnb6foxsd.png)

We're now officially done checking the tree, and we're left with a sorted array of [1, 2, 3, 4]. If we were asked to find the 1st smallest number in this array, we would look at the index of k-1, which is 0, so we can return 1.

--

That's it! There are a number of approaches to this problem, so please leave a comment of another method you'd take to solve this problem, and let me know if you have any questions.