LeetCode #700 — Search in a Binary Search Tree

Find more useful articles at www.davidseek.com

LeetCode’s challenge of the day on June 15, 2020 (#700) asks us to search a Binary Search Tree and return the node where node.val equals the target value.

To understand why the search in a Binary Search Tree (BST) is so highly efficient, we first need to understand the characteristics of it. A BST consists of nodes that each contain either one, two, or zero children. A node that contains zero children is called a Leaf.

Each node’s left child’s value is smaller than the node’s value, and the right node’s value is larger than the node’s value. The nodes on the left are smaller than the nodes on the right.

This means that if we’re searching for target: Int = 70 on a BST with root.value = 50, we know that the range of the right side of the tree is range(50, Int.max) and therefore we can eliminate the whole left side of the tree. Once we dig further into the tree, we can eliminate huge chunks until we find the node or leaf that is 70, or, when we've found that the value doesn't exist.