Description

A BST is a tree where the left < node < right. You are able to find values inside of it similar to with the Binary Search Exact
?

Reach for when

You need to find a value in a sorted binary tree

Runtime

balanced: O(log(n))
unbalanced: O(n)

Visualization

Pseudocode

BST(node, target):
	if node is target:
		return node
	if node has no children:
		return null
	
	if node is > target:
		BST(node.left)
	else:
		BST(node.right)

Code

def search(node, target):
	if not node:                             # ran off the tree → not found
		return None
	if node.val == target:
		return node
	if target < node.val:
		return search(node.left, target)     # target smaller → go left
	else:
		return search(node.right, target)    # target larger → go right