Problem 700

Abstract / Summary

Given a value and the root of a binary search tree find the node with that value or return null.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0700.py

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return None
        if root.val == val:
            return root

        if root.val > val:
            return self.searchBST(root.left,  val)
        else:
            return self.searchBST(root.right, val)
11 lines | 351 bytes | submitted September 1, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 83% (1+ million submissions).

Typical patterns to solve this problem:
  • Binary Search Tree
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a method searchBST that locates a node with a given value in a binary search tree (BST). The method follows a classic recursive pattern: it checks the current node, decides which subtree may contain the target based on the BST ordering invariant, and recurses accordingly. The design is concise, directly reflecting the logical structure of a BST search.

Key Steps

Base case for an empty subtree

The first conditional checks whether the current root reference is None. When the recursion reaches a leaf’s missing child, this condition triggers, and the method returns None to indicate that the value does not exist in the tree.

if not root:
    return None

Direct match detection

Immediately after confirming that a node exists, the method compares the node’s value with the target val. If they are equal, the current node is the desired result, and the method returns it without further recursion.

if root.val == val:
    return root

Choosing the left subtree

If the current node’s value is greater than the target, the BST property guarantees that any matching value must reside in the left subtree. The method therefore recurses on root.left, passing along the same target value.

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

Choosing the right subtree

Conversely, when the current node’s value is less than the target, the search proceeds to the right subtree. This branch mirrors the left-subtree case but targets root.right.

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

Edge Cases Handled

The algorithm gracefully handles the situation where the tree is empty from the outset; the initial if not root clause returns None instantly. It also correctly processes a tree consisting of a single node: if that node’s value matches the target, the method returns the node; otherwise, the recursive call on the appropriate missing child triggers the empty-subtree base case. Additionally, the code accommodates values that are not present anywhere in the tree; the recursion will eventually descend to a None child and return None, signaling an unsuccessful search.

Performance Optimizations

The implementation leverages the inherent ordering of a BST to eliminate half of the remaining nodes at each recursive step. By comparing the target value with the current node’s value, it decides deterministically which subtree could possibly contain the target, thereby avoiding unnecessary traversal of the opposite side. This selective recursion reduces the number of visited nodes dramatically compared to a naïve tree walk.

Furthermore, the method uses early returns for both the empty-tree and direct-match conditions. These immediate exits prevent additional stack frames from being created once the outcome is known, conserving call-stack depth and minimizing overhead.

The recursion is tail-recursive in the sense that each call returns the result of a single subsequent call without additional processing after the recursive invocation. While Python does not perform tail-call optimization, this pattern keeps the call stack as shallow as possible for the given search path.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a tall tree made of numbers where every branch has a specific rule. At the very top, there is a number that acts like a leader. If you are looking for a special treasure number, you start at that top leader.

You hold your treasure number in your hand and compare it to the leader. If the leader is exactly the number you want, then you have found it and reached the end of the game. If your treasure is smaller than the leader, you jump down to the left side of the tree to keep looking. If your treasure is bigger than the leader, you jump down to the right side of the tree instead. You keep doing this over and over again, bouncing from branch to branch, until you either find that secret treasure or you run out of branches to check. If you reach the bottom where there are no more branches and you still have not found the treasure, then it simply is not hiding in this tree.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 8.33 | σ = 0.90

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go TS
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
fpdjsns C++
halfrost Go
JoshCrozier JS
keineahnung2345 C++
Krazune C++
lkwq007 Python
qiyuangong Java
ruoru Rust
shreymehul C#
suxrobGM C#
trung-hn Python
varunu28 Java
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fpdjsns C++
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
Krazune C++
lkwq007 Python
qiyuangong Java
ruoru Rust
shreymehul C#
suxrobGM C#
trung-hn Python
varunu28 Java
YuriSpiridonov Python
38 links | 25 authors | 10 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

3 similar problems

Solved On The Same Day

30 solutions   September 1, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality