Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree

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).

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:

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.

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.

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.

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.

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.

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.

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.

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:

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

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.

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.

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

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.

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.

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

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.

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.

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.