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)
Difficulty
and has an acceptance rate of about 83% (1+ million submissions).
Typical patterns to solve this problem:
- Binary Search Tree
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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 |
Videos
Similar Problems
- problem 270: Closest Binary Search Tree Value
- problem 701: Insert into a Binary Search Tree
- problem 2476: Closest Nodes Queries in a Binary Search Tree
Solved On The Same Day
- problem 144: Binary Tree Preorder Traversal
- problem 145: Binary Tree Postorder Traversal
- problem 222: Count Complete Tree Nodes
- problem 404: Sum of Left Leaves
- problem 501: Find Mode in Binary Search Tree
- problem 543: Diameter of Binary Tree
- problem 559: Maximum Depth of N-ary Tree
- problem 589: N-ary Tree Preorder Traversal
- problem 590: N-ary Tree Postorder Traversal
- problem 637: Average of Levels in Binary Tree
- problem 703: Kth Largest Element in a Stream
- problem 79: Word Search
- problem 81: Search in Rotated Sorted Array II
- problem 97: Interleaving String
- problem 99: Recover Binary Search Tree
- problem 173: Binary Search Tree Iterator
- problem 199: Binary Tree Right Side View
- problem 230: Kth Smallest Element in a BST
- problem 235: Lowest Common Ancestor of a Binary Search Tree
- problem 341: Flatten Nested List Iterator
- problem 429: N-ary Tree Level Order Traversal
- problem 508: Most Frequent Subtree Sum
- problem 513: Find Bottom Left Tree Value
- problem 538: Convert BST to Greater Tree
- problem 65: Valid Number
- problem 85: Maximal Rectangle
- problem 87: Scramble String
- problem 126: Word Ladder II
- problem 127: Word Ladder
Extra
- 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