Binary search tree: search

Look up a key by walking down from the root, discarding a whole subtree at every step.

Time O(h)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

It is binary search on a tree. Every node splits the remaining keys into smaller ones on the left and larger ones on the right, so one comparison picks the side.

Code

C++PythonC#

bool search(TreeNode* root, int key) {
    while (root) {
        if (key == root->val) return true;
        root = key < root->val ? root->left : root->right;
    }
    return false;
}

def search(root: TreeNode | None, key: int) -> bool:
    while root:
        if key == root.val: return True
        root = root.left if key < root.val else root.right
    return False

public static bool Search(TreeNode root, int key) {
    while (root != null) {
        if (key == root.val) return true;
        root = key < root.val ? root.left : root.right;
    }
    return false;
}

Tips

The iterative version needs no call stack, so space is O(1).
Performance depends entirely on the tree being balanced.

In the .NET library

SortedSet<T>.Contains does this walk on a balanced tree. For plain membership tests with no ordering, HashSet<T> is faster at O(1).