BST Search - Scala DSA

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

Algorithm

Basic Implementation

basic.scala

import scala.collection.mutable.{ArrayBuffer, Queue}
class Node(val value: Int, var left: Node = null, var right: Node = null)
object Main {
  def render(node: Node): String = {
    if (node == null) "_"
    else if (node.left == null && node.right == null) node.value.toString
    else s"${node.value}(${render(node.left)},${render(node.right)})"
  }
  def sampleTree(): Node = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)))
  def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")
  def 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 }; false }
  def main(args: Array[String]): Unit = { 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.

Step 2 - Miss 8

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

Complexity

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

Implementation notes

class Node(val value: Int, var left: Node = null, var right: Node = null) gives each node an immutable Int value and mutable child references.
Empty links are plain null values in this source, not Option[Node].
search(root: Node, target: Int): Boolean is iterative: var node = root is the moving cursor, and the loop stops when that cursor becomes null.
Each loop checks target == node.value first and returns true immediately on a match.
If the values differ, target < node.value moves the cursor to node.left; otherwise it moves to node.right. Equal values are already handled by the match branch, so duplicates are not explored here.
The trace for 5 shows the path 4 -> right, 6 -> left, then 5 -> match.
The trace for missing 8 walks 4 -> right, 6 -> right, 7 -> right, then reaches null and returns false.
main prints the Boolean result as text, producing 5 found and 8 not found rather than rendering the searched nodes themselves.

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