Hello!

Today we will look at how to find the nearest value in BST. The input is given a binary tree and a number, and you need to find the closest number to the given one. For example, we have a tree:

    6
   / \
  4  10
 / \   \
2   5   23

And the number 13. You need to find the number that is closest to 13 in the tree. To do this, we need another number (the closest value), which has a high value such as infinity.

We start with the root, in this case, it has a value of 6. From the goal (number 13) module subtract 6 and get 7. Repeat the same with a current nearest value which is equal to infinity, |infinity - 13| = infinity. We compare two numbers 7 and infinity, 7 is less so the new nearest number will be 6. Next, we use the attributes of the binary tree. Since the number 13 is greater than the root 6 we can completely discard the left side of the tree. And it will remain only

    10
      \
       23

And the nearest number is 6. Do the same with the next element of the tree which is equal to 10. By the module, I subtract from the 10 values ​​that we are looking for. | 10 - 13 | = 3. And compares it with the current nearest number (13-6 = 7). 3 is less than 7. Hence, the new nearest number is 10.

The last element of a tree remained. Again, I subtract the value from the tree with goal number | 23 - 10 | = 13. And compare with the current nearest number (13-10 = 3). 13 is more than 3, so the nearest number remains 10. There are no more elements in the tree and therefore the closest number to 13 is 10.

An example of a solution to golang

package main

import (
	"fmt"
	"math"
)

type Tree struct {
	root *Node
}

type Node struct {
	key   int
	left  *Node
	right *Node
}

func main() {
	tree := Tree{
		&Node{
			key: 5,
			left: &Node{
				key: 4,
			},
			right: &Node{
				key: 10,
			},
		},
	}

	findClosestValue(tree, 3)
}
func findClosestValue(tree Tree, target int) {
	fmt.Println(findClosestValueHelper(tree.root, target, math.MaxInt32))
}

func findClosestValueHelper(node *Node, target int, closest int) int {
	if node == nil {
		return closest
	} else {
		if math.Abs(float64(target)-float64(closest)) > math.Abs(float64(target)-float64(node.key)) {
			closest = node.key
		}
		if target < node.key {
			return findClosestValueHelper(node.left, target, closest)
		} else if target > node.key {
			return findClosestValueHelper(node.right, target, closest)
		}
	}
	return closest
}