Finding The Closest Value in a Binary Search Tree (BST)
This week let us take a step up and learn about the Binary Search Tree, also known as the BST in abbreviation. If you haven’t read up on binary search and how to setup a binary search tree yet, I highly suggest you to get familiar with that first before continuing on. You can also checkout my blog post about binary search .
When you think of a tree, you usually thing from bottom to top. A tree’s root start from the bottom. Just like a real tree, our binary tree starts from the root, but instead of the the bottom, we start from the top because as programmers we work from top down. A binary tree is made up of nodes, and unless it is the ending node of a tree, each node has three things:
- A value
- A left node to go left of our current node, its owns value, a left and a right.
- A right node to go right of our current node, its owns value, a left and a right.
The important thing about it being binary is that we only have two paths (left or right) from each node. One thing about a binary tree is that it is very similar to binary search in that when you go down one path, you eliminate half of tree (or array).
Our problem from AlgoExpert:
Write a function that takes in a Binary Search Tree (BST) and a target integer value and returns the closest value to that target value contained in the BST. You can assume that there will only be one closest value.
Each BST node has an integer value, a left child node, and a right child node. A node is said to be a valid BST node if and only if it satisfies the BST property: its value is strictly greater than the values of every node to its left; its value is less than or equal to the values of every node to its right; and its children nodes are either valid BST nodes themselves or None / null
Since this is a small BST, we could easily go through the whole tree and see which value is closet to our target (12). But trees are not usually this small. If you have to open a root file on your computer, you will most likely go layers and folders deep to find it. This is the exact concept for the tree. Let us see how we can solve this problem.
Before we start from our first node, do you see something that jumps out right away? Is there a pattern for each layer/level or the tree? Thats right each layer or level is sorted from left to right. So, we will start by assigning our root node to a variable called currentNode. We are doing this because even though it is our starting point, the currentNode will change when move through the tree.
We also want to set our closest value or the value we are going to return, because we are here looking for the closest value to Infinity. We use Infinity because it is a number, but any number is smaller than Infinity so it will reassign on our first loop.
Our solution:
The time complexity is O(log(n)) and our space complexity is 0(1) since we are only returning one value.
