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.
if not root or root.val == val:
return root
if val < root.val:
return search_bst(root.left, val)
return search_bst(root.right, val)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.