Problem statement

You are given the root of a binary search tree (every value in a node's left subtree is smaller than the node's value, every value in its right subtree is larger) and an integer target.

Find the node whose value equals target and return the subtree rooted at that node. If no node holds target, return the empty tree [].

Example 1

Input: root = [4,2,7,1,3], target = 2
Output: [2,1,3]
Explanation: The node holding 2 has children 1 and 3, so its subtree is `[2,1,3]`.

Example 2

Input: root = [4,2,7,1,3], target = 5
Output: []
Explanation: 5 would sit as the left child of 7, but that spot is empty: no node holds 5.

Example 3

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13], target = 10
Output: [10,null,14,13]
Explanation: 10 has no left child and a right child 14, whose left child is 13.

Constraints

• 1 <= number of nodes <= 5000
• 1 <= Node.val <= 10^7
• all node values are distinct
• root is a valid binary search tree
• 1 <= target <= 10^7

Hints for Search in a Binary Search Tree

1. Hint 1

   You never need to look at both subtrees: the ordering tells you which side target must be on.

2. Hint 2

   Compare target with the current node — equal means found, smaller means go left, larger means go right.

3. Hint 3

   Walk down until you either hit the value or fall off the tree; the node you stopped on (or null) is the answer.

How to solve Search in a Binary Search Tree

The search-tree ordering turns the search into a single walk from the root: at each node exactly one subtree can contain target, so the other is skipped entirely.

Approach

1. Start at the root.
2. While the current node exists and its value is not target: move to the left child if target is smaller, otherwise to the right child.
3. Return the current node — the subtree rooted there, or null (the empty tree) if the walk fell off.

Why it works

If target is smaller than a node's value, every value in the right subtree is larger still, so target can only be on the left — and symmetrically on the right. The walk therefore never skips the node that holds target, and stops on it if it exists.

Complexity

• Time — O(h), h the height of the tree (O(log n) when balanced, O(n) for a chain)
• Space — O(1)

Pitfalls

• Return the node itself, not a copy of its value: the answer is the whole subtree hanging below it.
• Searching both subtrees still works but throws away the reason the tree is ordered.

Reference solution

Python

from typing import Optional

def searchBST(root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
    node = root
    while node is not None and node.val != target:
        node = node.left if target < node.val else node.right
    return node

Java

public static TreeNode searchBST(TreeNode root, int target) {
    TreeNode node = root;
    while (node != null && node.val != target) node = target < node.val ? node.left : node.right;
    return node;
}

C++

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

JavaScript

var searchBST = function(root, target) {
    var node = root;
    while (node !== null && node.val !== target) node = target < node.val ? node.left : node.right;
    return node;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More binary search problems

• Level of a Node in Binary Tree Easy
• Sum of Leaf Nodes at Minimum Level Easy
• Count BST Nodes That Lie in a Given Range Easy
• Nodes at Odd Levels Easy
• Kth Largest Element in BST Easy
• Ceil in BST Easy