Trees

BST Search

Search a binary search tree for one present and one absent value.

Algorithm

Basic Implementation

basic.kt 
class Node(val value: Int, var left: Node? = null, var right: Node? = null)
fun render(node: Node?): String {
    if (node == null) return "_"
    if (node.left == null && node.right == null) return node.value.toString()
    return "${node.value}(${render(node.left)},${render(node.right)})"
}
fun sampleTree() = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")
fun search(root: Node?, target: Int): Boolean { var node = root; while (node != null) { if (target == node.value) return true; node = if (target < node.value) node.left else node.right }; return false }
fun main() { val root = sampleTree(); println(if (search(root, 5)) "5 found" else "5 not found"); println(if (search(root, 8)) "8 found" else "8 not found") }

A BST search follows one comparison path. The same pinned tree shows a found path for 5 and a missing path for 8.

Step 1 - Find 5

Search 5 takes right from 4, then left from 6, then matches 5.

Present search path: 4 -> 6 -> 5.4#126#2135match7

Step 2 - Miss 8

Search 8 takes right from 4, right from 6, right from 7, then reaches null.

Absent search path: 4 -> 6 -> 7 -> null.4#126#21357#3nullnot found

Complexity

  • Time: O(h) per search
  • Space: O(1) iterative

Implementation notes

  • Kotlin represents nodes with class Node(val value: Int, var left: Node? = null, var right: Node? = null), so child links are nullable references.
  • sampleTree() allocates the fixed tree with nested Node(...) calls and returns a non-null root for main.
  • search(root: Node?, target: Int): Boolean is iterative. It starts with var node = root, then loops while the nullable cursor is not null.
  • A matching target == node.value returns true; otherwise node is rebound to node.left when target < node.value, or node.right for larger values.
  • Falling out of the loop means the cursor reached null, so the function returns false instead of using an exception or nullable result.
  • The trace searches 5 by visiting 4 right, 6 left, then matching 5. It searches 8 by visiting 4, 6, and 7 to the right before reaching null.
  • println(if (search(root, 5)) "5 found" else "5 not found") and the second call print 5 found and 8 not found.
search path A comparison chooses one subtree at each step, so whole branches are skipped.