Search in a Binary Search Tree — Editorial

Opening the reading…

Intuitionthe BST property removes every wrong subtree

At any node, the BST property tells you where every possible match can be. Values smaller than the current node are in the left subtree, and values larger than the current node are in the right subtree. If the current value equals val, you already have the required answer: return this node, because returning it also returns the entire subtree rooted there.

If val is smaller, no node in the current node's right subtree can match, so moving left is forced. If val is larger, the left subtree is impossible and you move right. Each comparison discards one whole subtree, leaving a single path to follow. Reaching null means that path contains no matching node, so null is the correct result.

Approach

Start at root and keep the current candidate in the root pointer, because every node you visit is the root of the only subtree that can still contain val.

Continue while the current pointer is not null and its value is not val, because either condition ending means the search is already finished.

If val is smaller than the current value, move to the left child, because every value in the right subtree is too large to match.

Otherwise move to the right child, because the current value is not equal and val must be larger, so the left subtree cannot contain it.

Return the current pointer after the loop, because it is either the matching node or null after the only possible search path has been exhausted.

Complexitythe path height controls the work

MEASURE	BOUND	WHY
Time	O(h), worst case O(n)	The loop follows one child pointer per level and never revisits a node or explores a discarded subtree. A balanced tree has h proportional to log n, while a completely one-sided tree can have h equal to n.
Space	O(1) extra	The algorithm stores only the current pointer and val. The returned subtree is required output and uses no newly allocated storage, so it is excluded; the input shape does not change this constant auxiliary bound.

Here, n is the number of nodes and h is the height of the tree, measured as the maximum number of nodes on a root-to-leaf path.

Annotated solutionC++ · iterative · one pointer follows the only viable path

CPPIteratively search one BST path and return the matching node or null.

#include <cstddef>

using namespace std;

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != nullptr && root->val != val) {
            root = (val < root->val) ? root->left : root->right;
        }
        return root;
    }
};

The assignment is the central line: it replaces the current candidate with exactly one child. The comparison chooses left for a smaller target and right for a larger target; equality is excluded by the loop condition, so the remaining pointer can only be a match or null. No node is copied, and returning root returns the original subtree with all of its children intact.

The recursive alternativea clear arrangement, not a space optimisation

CPPRecursive search that returns the result directly from the chosen child.

#include <cstddef>

using namespace std;

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr || root->val == val) {
            return root;
        }

        if (val < root->val) {
            return searchBST(root->left, val);
        }
        return searchBST(root->right, val);
    }
};

The recursive version expresses the same decision at each node: stop for null or equality, otherwise recurse into one child. It is merely a different arrangement, not an optimisation. It still takes O(h) time, but its call stack uses O(h) extra space and can reach O(n) in a one-sided tree. The iterative solution keeps the same path in one pointer, so it is preferable when constant auxiliary space matters.