Find Closest Value in BST - algoexpert.io

findClosestValueInBST1.py

"""
https://www.algoexpert.io/questions/Find%20Closest%20Value%20In%20BST

Average: Theta(logn) time | Theta(logn) space 
Worst: O(n) time | O(n) space

This solution takes up O(n) space because of recursion.

float('inf') is used to set a unbounded upper value for comparison
"""

def findClosestValueInBst(root, target):
    return findClosestValueInBstHelper(root, target, float('inf'))

def findClosestValueInBstHelper(subtree, target, closest):
	if subtree is None:
		return closest

	# if the current tree value is closer to the target than the current
	# recorded closest (it's absolute value difference is smaller or equal)
	# then set new closeset
	if abs(target - subtree.value) <= abs(target - closest):
		closest = subtree.value

	# if the current tree node value is greater than the target, we
	# need to go to a smaller value, so traverse to the left subtree
	if subtree.value > target:
		return findClosestValueInBstHelper(subtree.left, target, closest)

	# if the current tree node value is less than the target, we
	# need to go to a larget value, so traverse to the right subtree
	elif subtree.value < target:
		return findClosestValueInBstHelper(subtree.right, target, closest)

	else:
		return closest

findClosestValueInBST2.py

"""
https://www.algoexpert.io/questions/Find%20Closest%20Value%20In%20BST

Average: Theta(logn) time | Theta(1) space 
Worst: O(n) time | O(1) space

This solution uses O(1) space because it doesn't use recursion

float('inf') is used to set a unbounded upper value for comparison
the input "node" is the root of the tree
"""

def findClosestValueInBst(node, target):
	closest = float('inf')
	while node is not None:
		if abs(target - node.value) < abs(target - closest):
			closest = node.value
		if node.value > target:
			node = node.left
		elif node.value < target:
			node = node.right
		else:
			break
	return closest