Goal: Compare with root and step left or right, discarding half the remaining nodes each time.

Stepping left or right

At any node, compare your target with the node's value. If they are equal, you found it. If the target is smaller, search the left subtree. Otherwise, search the right subtree.

If you fall off the tree by reaching an empty spot, the value is not in the tree. Like following signs in a building: each sign sends you one way, until you arrive or hit a dead end.

Equal: found: return the node.

Smaller: search the left side.

Larger: search the right side.

In code

if name < node.name:
    node = node.left
else:
    node = node.right

Searching for 7

7 < 8, so 7 can only be on the left. The whole right side is ruled out without looking at it.

Move 1 of 4

Time complexity

Each step moves down one level of the tree. If the tree is balanced, with height about log₂ of n, searching takes only about log n steps rather than n.

That is the same speed-up as halving a sorted list: a tree of a million nodes needs only about 20 steps to find anything.

Time depends on height: not on the total node count.

Worst case: if all nodes line up like a linked list, the height is n.