BST Search - Kotlin DSA

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Kotlin DSA implementation can be compared directly with the rest of the DSA track.

search path A comparison chooses one subtree at each step, so whole branches are skipped.

Visual walkthrough

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.

Step 2 - Miss 8

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

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") }

                        

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.