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.
Example 1:
Input: root = [4,2,7,1,3], val = 2 Output: [2,1,3]
Example 2:
Input: root = [4,2,7,1,3], val = 5 Output: []
Constraints:
[1, 5000].1 <= Node.val <= 107root is a binary search tree.1 <= val <= 107This approach uses the recursive traversal of the BST properties. It checks if the current node's value is equal to the target value. If it is, it returns the subtree rooted at the current node. If the target value is less than the current node, it recurses into the left subtree; if greater, it recurses into the right subtree. This method leverages the BST's inherent properties to narrow down the search.
This C code defines a recursive function searchBST that starts from the root of the tree. It checks if the current node is NULL or matches the target val. If it matches, it returns the node. If the target is smaller, it recurses into the left subtree; otherwise, it goes to the right subtree.
C++
Java
Python
C#
JavaScript
Time Complexity: O(h) where h is the height of the tree, as we traverse from the root to a leaf.
Space Complexity: O(h) due to the recursion stack.
In this approach, we use an iterative solution instead of recursion to save stack space. Starting from the root, we use a loop to traverse the tree. At each node, we check if it matches the target value. If it matches, we return the node; if not, we decide to move to the left or right child based on the BST property. The absence of a matching node returns null.
This code converts the recursive search logic into an iterative one by using a while loop. It repeatedly narrows down the search area based on the value comparison until it finds the value or reaches a NULL node.
C++
Java
Python
C#
JavaScript
Time Complexity: O(h) where h is tree height.
Space Complexity: O(1) since we're only using a few extra pointers.
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(h) where h is the height of the tree, as we traverse from the root to a leaf. |
| Iterative Approach | Time Complexity: O(h) where h is tree height. |
Balanced Binary Tree - Leetcode 110 - Python • NeetCode • 306,385 views views
Watch 9 more video solutions →Practice Search in a Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode