EasyTreeBinary Search TreeBinary Tree

Search in a Binary Search Tree

1 approach, code in every language

You are given the root of a binary search tree (BST) and an integer val.

Locate the node whose value equals val and return the subtree rooted at that node (that is, the node itself along with everything beneath it). If no node in the tree has the value val, return null.

Example 1

Input: root = [4,2,7,1,3], val = 2

Output: [2,1,3]

The node with value 2 has children 1 and 3, so the returned subtree is [2,1,3].

Example 2

Input: root = [4,2,7,1,3], val = 5

Output: []

No node holds the value 5, so the search returns null (shown as an empty tree).

Constraints

The number of nodes in the tree is in the range [1, 5000].
1 <= Node.val <= 10^7
root is a binary search tree.
1 <= val <= 10^7

Iterative BST Walk

Follow the BST ordering property, branching left or right until the value matches or the walk falls off the tree.

Loading animation…

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

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

Time

O(h)

Space

O(1)

The walk descends one level per iteration, so time is O(h) where h is the height, up to O(n) for a skewed tree and O(log n) when balanced. The iterative version uses constant extra space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Pulling A Branch Out Of A Code Index is our own problem on the technique behind Search in a Binary Search Tree: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free