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.