BST Search - Java DSA

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

Algorithm

Basic Implementation

Basic.java

import java.util.*;

public class Basic {
    static class Node {
        int value;
        Node left;
        Node right;
        Node(int value) { this.value = value; }
        Node(int value, Node left, Node right) { this.value = value; this.left = left; this.right = right; }
    }
    static String render(Node node) {
        if (node == null) return "_";
        if (node.left == null && node.right == null) return Integer.toString(node.value);
        return node.value + "(" + render(node.left) + "," + render(node.right) + ")";
    }
    static Node sampleTree() {
        return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
    }
    static boolean search(Node root, int target) { Node node = root; while (node != null) { if (target == node.value) return true; node = target < node.value ? node.left : node.right; } return false; }
    public static void main(String[] args) { Node root = sampleTree(); System.out.println(search(root, 5) ? "5 found" : "5 not found"); System.out.println(search(root, 8) ? "8 found" : "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

Java represents the tree with Node objects containing primitive int value plus Node left and Node right reference fields. Missing children are null.
search is iterative, not recursive: it copies the root reference into a local Node node cursor and runs while (node != null).
Each step compares the primitive target with node.value. Equality returns true; otherwise node = target < node.value ? node.left : node.right follows the next child reference. A null cursor exits the loop and returns false.
The replay shows the found path for 5 as 4 -> right, 6 -> left, then match at 5; the missing search for 8 walks right from 4, 6, and 7 before reaching null. The search allocates no new nodes, so GC relevance is limited to the prebuilt tree objects.

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