Search in a Binary Search Tree – LeetCode75 Python Solution Explained

The Search in a Binary Search Tree (BST) problem (LeetCode75) is a fundamental binary tree challenge that tests your understanding of binary search logic, recursion and tree traversal. It is commonly asked in technical interviews to evaluate problem-solving skills with tree data structures and efficient searching.

In this blog, we will break down the problem, provide examples, explain the Python solution step by step with code snippets, analyze time and space complexity, discuss edge cases and explore real-world applications.

Problem Statement

Given the root of a binary search tree (BST) and an integer val, return the subtree rooted with the node whose value equals val. If such a node does not exist, return None.

BST Properties

1. Left subtree contains values less than the node’s value.
2. Right subtree contains values greater than the node’s value.
3. Both subtrees must also be BSTs.

Example 1

Input:

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

Tree visualization:

       4
     /   \
    2     7
   / \
  1   3

Output:

[2,1,3]

Explanation: The node with value 2 exists so we return its subtree.

Example 2

Input:

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

Output:

None

Explanation: Node with value 5 does not exist in the BST.

Complete Python Solution

from typing import Optional

# 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]:
        return root if not root or root.val == val else self.searchBST(
            root.left if root.val > val else root.right, val
        )

Step-by-Step Explanation

Step 1: Handle Base Case

If the tree is empty (root is None) or the current node equals the target value, return the node.

if not root or root.val == val:
    return root

Step 2: Recursive Search

• If val is less than root.val, search in the left subtree.
• If val is greater than root.val, search in the right subtree.

if root.val > val:
    return self.searchBST(root.left, val)
else:
    return self.searchBST(root.right, val)

Concise one-line version:

return root if not root or root.val == val else self.searchBST(
    root.left if root.val > val else root.right, val
)

Step 3: Return Result

• If the node is found, recursion returns the node.
• If not found, the function returns None.

Time and Space Complexity

• Time Complexity:O(h)
  • h = height of the tree.
  • Balanced BST → O(log n)
  • Skewed BST → O(n)
• Space Complexity: O(h) due to recursion stack.

Edge Cases

1. Empty tree: root = None → returns None.
2. Value at root: returns root immediately.
3. Value not present: traversal reaches None, returns None.

Real-World Applications

• Databases: Indexing using BSTs (like B-Trees or AVL Trees).
• File Systems: Searching directories efficiently.
• Autocomplete Systems: Quick lookups in sorted hierarchical data.
• Gaming AI: Decision trees and pathfinding using tree search.

Conclusion

The Search in a Binary Search Tree problem is a classic exercise in recursion, BST properties and efficient searching.

By practicing this problem, you improve your understanding of:

• Recursive tree traversal
• Leveraging BST properties for faster search
• Edge case handling in hierarchical structures

It is excellent preparation for technical interviews and real-world data structure implementations.

Related Reads

• Maximum Level Sum of a Binary Tree – LeetCode75 Python Solution Explained
• Kth Largest Element in an Array – LeetCode75 Python Solution Explained
• Rotting Oranges – LeetCode75 Python Solution Explained
• Delete Node in a Binary Search Tree – LeetCode75 Python Solution Explained
• Number of Provinces – LeetCode75 Python Solution Explained

References

1. LeetCode – Search in a BST
2. Programiz – Binary Search Tree Tutorial
3. TutorialsPoint – Binary Search Tree