loading...
Cover image for Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree

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

alisabaj profile image Alisa Bajramovic Updated on ・6 min read

Algorithm of the Day (35 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 33 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript

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:

binary search tree

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

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

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

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

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.

calling dfs on 2 -- nothing to the left

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

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

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

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

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.

Algorithm of the Day (35 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 33 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript

Posted on May 20 by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide