Domain 1EasyCORE

Search in a Binary Search Tree

The problem requires finding a node in a binary search tree (BST) where the node's value matches a given integer `val`. If such a node exists, we return the subtree rooted at that node. If no such node exists, we return `null`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree

700. Search in a Binary Search Tree

Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 73.4%


Problem Breakdown

The problem requires finding a node in a binary search tree (BST) where the node’s value matches a given integer val. If such a node exists, we return the subtree rooted at that node. If no such node exists, we return null.

Inputs:

  • root: The root node of the BST.
  • val: An integer value to search for in the BST.

Outputs:

  • The subtree rooted at the node with value val, or null if no such node exists.

Implicit Constraints/Edge Cases:

  • The tree can be empty, though the problem guarantees at least one node.
  • The values are unique within the BST.

Intuition

A brute-force approach would involve traversing the entire tree to find the node with value val. This would have a time complexity of O(n), where n is the number of nodes in the tree. However, since it’s a binary search tree, we can leverage its properties to improve efficiency.

The key insight is that for any given node in a BST:

  • If the target value val is less than the current node’s value, then the target must be in the left subtree.
  • If the target value val is greater than the current node’s value, then the target must be in the right subtree.

This allows us to perform a binary search-like traversal, reducing the time complexity to O(h), where h is the height of the tree. In the worst case (a skewed tree), this could still be O(n), but for a balanced BST, it would be O(log n).

Approach

We will use an iterative approach with a stack to traverse the BST. The steps are as follows:

  1. Initialize a stack and push the root node onto it.
  2. While the stack is not empty:
    • Pop a node from the stack.
    • If the node’s value matches val, return the node (which represents the subtree).
    • If val is less than the node’s value, push the left child onto the stack if it exists.
    • If val is greater than the node’s value, push the right child onto the stack if it exists.
  3. If we exit the loop without finding the node, return null.

Complexity Analysis

  • Time Complexity: O(h), where h is the height of the tree. In the worst case (a skewed tree), this could be O(n). For a balanced BST, it would be O(log n).
  • Space Complexity: O(h) due to the stack used for traversal. In the worst case, this could be O(n).

Solution

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:
    stack = [root]
    
    while stack:
        node = stack.pop()
        
        if node.val == val:
            return node
        
        if node.val > val and node.left:
            stack.append(node.left)
        
        if node.val < val and node.right:
            stack.append(node.right)
    
    return None

Edge Cases Handled

  • Empty Tree: The function will return null immediately since the root is None.
  • Node Not Found: If no node with value val exists in the tree, the function will traverse the entire tree and finally return null.