And, welcome to another tutorial on GeeksforGeeks. In this video we are going to understand the
program which Find the closest element in Binary Search Tree
FIrst, let us take an example Now, let us see the approach.
Next, let us see the algorithm. Let us also have a sample tree to test our
algorithm. Let us assume that we have to find the closest
element to 12. So, we pass the root node that is 5 and 12 to k to the maxDiff
function. Next, we take a min_diff variable and initialize
to int_max and a min_diff_key variable initialized to -1
Next, we call the maxDiffUtil function with root,k, min_diff and min_diff_key
passed as parameters. Since ptr is not null, we check if ptr->key
is equal to k. As it is false, we check if min_diff>abs(5-12). The absolute difference
is 7 and since min_diff is greater than 7, the if condition gets satisfied and we
set min_diff to 7 and min_diff_key to ptr. Next, we check if k is less than ptr->key.
As it is false, we go to the else part and pass the right child of 5 that is 13
Since ptr is not null and ptr->key is not equal to k, we update min_diff. Since
7>abs(ptr-key), the if condition gets satisfied and we set min_diff to abs(ptr-key)
and min_diff_key to ptr. Now, we check if k is less than ptr. As it
is true, we pass the left child of 13 which is NULL. So, ptr will now point to null.
Since ptr is null, we return to the previous call.
Execution for node 13 is also over and we return to execution for node 5.
Execution for node 5 is also over and we have the min_diff_key as 13 which is our
answer. With this we finish execution for this program. Now, let us have a look at
the time complexity of the program. This code will run in O(n) complexity.Here
n are the number of nodes in our tree. With this we come to an end of this tutorial.
For any doubts or suggestions please leave them in the comment section below.
Thanks for watching!