Search in a Binary Search Tree

Difficulty: Easy | Acceptance: 82.70% | Paid: No Topics: Tree, Binary Search Tree, Binary Tree

You are given the root of a Binary Search Tree (BST) and an integer val.

Find the node in the BST that has the node’s value equal to val and return the subtree rooted at that node. If such a node does not exist, return null.

• Examples
• Constraints
• Recursive Approach
• Iterative Approach
• Iterative with Stack (DFS)

Examples

Example 1

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

Example 2

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

Constraints

The number of nodes in the tree is in the range [0, 5000].
-10⁴ <= Node.val <= 10⁴
All Node.val are unique.
root is a valid binary search tree.
-10⁴ <= val <= 10⁴

Recursive Approach

Intuition Leverage the BST property: left subtree contains smaller values, right subtree contains larger values. Recursively navigate to the correct subtree.

Steps

• If root is null or root value matches target, return root
• If target is less than root value, search left subtree
• Otherwise, search right subtree

# 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
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None or root.val == val:
            return root
        if val < root.val:
            return self.searchBST(root.left, val)
        else:
            return self.searchBST(root.right, val)

Complexity

• Time: O(h) where h is the height of the tree (O(log n) for balanced, O(n) for skewed)
• Space: O(h) for recursion stack
• Notes: Clean and intuitive, but uses call stack space

Iterative Approach

Intuition Eliminate recursion overhead by using a while loop to traverse the tree iteratively, following BST properties.

Steps

• Start from root and iterate while current node is not null
• If current node value matches target, return it
• Move to left child if target is smaller, right child otherwise
• Return null if not found

# 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
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        current = root
        while current is not None:
            if current.val == val:
                return current
            elif val < current.val:
                current = current.left
            else:
                current = current.right
        return None

Complexity

• Time: O(h) where h is the height of the tree (O(log n) for balanced, O(n) for skewed)
• Space: O(1)
• Notes: Optimal space complexity, avoids recursion stack overhead

Iterative with Stack (DFS)

Intuition Use an explicit stack to simulate DFS traversal, pushing only the relevant child based on BST comparison.

Steps

• If root is null, return null
• Push root onto stack
• While stack is not empty, pop node and check if value matches
• Push left child if target is smaller, right child if larger
• Return null if target not found

# 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
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return None
        stack = [root]
        while stack:
            node = stack.pop()
            if node.val == val:
                return node
            if val < node.val and node.left:
                stack.append(node.left)
            elif val > node.val and node.right:
                stack.append(node.right)
        return None

Complexity

• Time: O(h) where h is the height of the tree (O(log n) for balanced, O(n) for skewed)
• Space: O(h) for the stack
• Notes: Demonstrates explicit stack usage, but less efficient than simple iterative approach