BST Search - Python DSA

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

Algorithm

Basic Implementation

basic.py

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def render(node):
    if node is None:
        return "_"
    if node.left is None and node.right is None:
        return str(node.value)
    return f"{node.value}({render(node.left)},{render(node.right)})"

def sample_tree():
    n1 = Node(1)
    n3 = Node(3)
    n2 = Node(2, n1, n3)
    n5 = Node(5)
    n7 = Node(7)
    n6 = Node(6, n5, n7)
    return Node(4, n2, n6)

root = sample_tree()
def search(root, target):
    node = root
    while node is not None:
        if target == node.value:
            return True
        node = node.left if target < node.value else node.right
    return False
print("5 found" if search(root, 5) else "5 not found")
print("8 found" if search(root, 8) 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

Python represents each node as a Node object with value, left, and right attributes. root = sample_tree() keeps a reference to the top node of the checked-in tree.
Search is iterative, not recursive: node = root creates a cursor reference, while node is not None guards every attribute read, and node = node.left if target < node.value else node.right moves that cursor without mutating the tree.
The function returns the boolean singletons True or False; no search-time nodes are allocated, and Python manages tree objects while they remain reachable from root. The replay shows 5 taking right-left-match and 8 taking right-right-right to None.

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