The challenge
Find a key in a binary search tree and return its node object, or null if absent.
Strict BST: every key in the left subtree is smaller; every key in the right subtree is larger.
Example
Key 10 follows 8 → 12 → 10 and returns F:10. Key 11 reaches a null child.
Use the walkthrough below to inspect the input and each state change.
See BST search, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View original input
A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]
Key: 10
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
Use the ordering rule to choose exactly one child at each comparison.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def bst_search(root, key):
node = root
while node:
if key == node.value:
return node
node = node.left if key < node.value else node.right
return None
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
Node* bst_search(Node* root, long long key) {
Node* node = root;
while (node) {
if (key == node->value) return node;
node = key < node->value ? node->left : node->right;
}
return nullptr;
}