Hello friends!

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!