We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Search in a Binary Search Tree

Number: 783

Difficulty: Easy

Paid? No

Companies: Meta, Google, Microsoft, Bloomberg, Adobe, Apple

Problem Description

Given the root of a binary search tree (BST) and an integer value, find the node in the BST with the given value. If such a node exists, return the subtree rooted at that node; otherwise, return null.

Key Insights

  • Utilize the BST property: for any node, all values in the left subtree are smaller and all values in the right subtree are larger.
  • This property allows efficient searching by choosing the correct subtree to continue the search.
  • The problem can be recursively or iteratively solved.
  • Recursion typically leads to a cleaner, more intuitive implementation.

Space and Time Complexity

Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h) due to recursion stack in the recursive approach, or O(1) if an iterative approach is used.

Solution

We traverse the BST starting at the root. For each node, we compare the target value with the current node's value:

  1. If the values match, we return the current node.
  2. If the target value is less, we recursively (or iteratively) search the left subtree.
  3. If the target value is greater, we proceed to search the right subtree. By making use of the BST properties, we avoid checking every node, which makes the approach efficient.

Code Solutions

Python:

JavaScript:

C++:

Java:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def searchBST(root: TreeNode, val: int) -> TreeNode:
    # Base case: if root is null or found the target value, return the root
    if not root or root.val == val:
        return root
    # If target value is less than current node's value, search in the left subtree
    if val < root.val:
        return searchBST(root.left, val)
    # Otherwise, search in the right subtree
    return searchBST(root.right, val)
← Back to All Questions