Search in a Binary Search Tree

Intuition

A binary search tree guarantees that every value in a node's left subtree is smaller than the node and every value on the right is larger. That ordering lets us skip half of the remaining tree at every step instead of scanning everything. Compare the target with the current node's value: if the target is smaller, the match can only be to the left, and if it is larger it can only be to the right. Move in that direction and repeat, stopping the moment the current node matches the target or becomes null. Because we never revisit a discarded branch, an iterative loop needs no extra stack.

Algorithm walkthrough

1. 1Start at the root as the current node.
2. 2While the current node is non-null and its value does not equal val, decide which way to go.
3. 3If val is less than the current node's value, move to the left child; otherwise move to the right child.
4. 4Loop back and re-check the new current node.
5. 5The loop exits either on a node whose value equals val or on null when the value is absent.
6. 6Return the current node, which is the matching subtree or null.

Implementation

class Solution:
    def searchBST(self, root: 'TreeNode', val: int) -> 'TreeNode':
        while root is not None and root.val != val:
            if val < root.val:
                root = root.left
            else:
                root = root.right
        return root