Leetcode – Search in a Binary Search Tree Solution in Python

Spread the love

Introduction

In this article, we’ll delve into the Search in a Binary Search Tree problem on Leetcode, understand its requirements, and ultimately solve it using Python.

Problem Statement

Here’s the problem statement for “Search in a Binary Search Tree”:

You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Understanding the Problem

A binary search tree (BST) is a binary tree data structure where each node has a comparable value. For each node, its left children are less than the node, and its right children are more than the node.

The problem requires us to search a given integer val in the given BST. If found, we should return the subtree rooted with the found node. If not found, we should return null.

A Simplified Approach – Depth-First Search (DFS)

One straightforward method to approach this problem is by using Depth-First Search (DFS). In DFS, we start at the root (or any arbitrary node) and traverse as far as possible along each branch before backtracking.

A binary search tree property can be utilized here to optimize our search. If the current node’s value is less than val, we only need to search the right subtree. If the current node’s value is more than val, we only need to search the left subtree.

This approach simplifies the problem as it effectively reduces the search space by half at each step, leading to an average and best-case time complexity of O(log n). However, in the worst-case scenario, where the tree is skewed, the time complexity is O(n).

We can solve this problem using recursion, which is the most common way to implement a DFS. Below is a Python solution for this problem:

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

class Solution:
    def searchBST(self, root, val):
        if root is None or val == root.val:
            return root
        
        if val < root.val:
            return self.searchBST(root.left, val)
        
        return self.searchBST(root.right, val)

In this Python code:

  1. We first check if the root is null (which means the tree is empty or we’ve traversed the tree without finding val), or the root‘s value equals val. If either of these conditions is true, we return the root.
  2. If val is less than root.val, we return the result of a recursive call of searchBST on the left subtree.
  3. If val is more than root.val, we return the result of a recursive call of searchBST on the right subtree.

Time and Space Complexity Analysis

The time complexity for this solution is O(log n) for a balanced tree and O(n) for a skewed tree, where n is the number of nodes in the tree.

The space complexity is O(h), where h is the height of the tree. This space is used by the call stack during the recursion. The worst case occurs when the tree is skewed, making the height equal to the number of nodes, i.e., O(n).

Conclusion

In conclusion, the “Search in a Binary Search Tree” problem is a great way to understand how the properties of a binary search tree can be used to our advantage. Although it might seem challenging at first, breaking down the problem into smaller, more manageable parts can significantly simplify the task.

Leave a Reply