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:
- The number of nodes in the tree is in the range [1, 5000].
- 1 <= Node.val <= 107
- root is a binary search tree.
- 1 <= val <= 107
🤓Explanation
Okay, imagine you're looking for a specific toy in a special kind of toy shelf. This shelf is organized in a super helpful way:
- Each shelf holds one toy.
- All the toys on the left side of a shelf are smaller than the toy on that shelf.
- All the toys on the right side of a shelf are bigger than the toy on that shelf.
This special shelf is like our Binary Search Tree (BST), and the toys are the TreeNodes with their values. You're trying to find a toy with a specific val.
Here's how you'd search:
function searchBST(shelf, target_toy_value):
# If the shelf is empty, the toy isn't here.
if shelf is empty:
return "Toy not found"
# Look at the toy on the current shelf.
current_toy_value = value of toy on shelf
# Is this the toy we're looking for?
if current_toy_value is equal to target_toy_value:
return "Found the toy on this shelf!"
# If our toy is smaller than the toy on this shelf,
# it must be on the left side (if it's anywhere).
else if target_toy_value is smaller than current_toy_value:
return searchBST(left side of shelf, target_toy_value)
# If our toy is bigger than the toy on this shelf,
# it must be on the right side (if it's anywhere).
else if target_toy_value is bigger than current_toy_value:
return searchBST(right side of shelf, target_toy_value)
⚙️Implementations
🐍Python
# # 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]:
"""
Searches for a node with a specific value in a Binary Search Tree (BST).
Args:
root (Optional[TreeNode]): The root node of the BST. Can be None if the tree is empty.
val (int): The value to search for in the BST.
Returns:
Optional[TreeNode]: The node in the BST whose value is equal to the target value 'val'.
Returns None if the value is not found in the BST or if the tree is empty.
"""
# Base case: If the current node is None (we've reached the end of a branch)
# or if the current node's value matches the target value.
if not root or root.val == val:
return root
# If the target value is less than the current node's value,
# it must be in the left subtree (due to BST property).
if val < root.val:
return self.searchBST(root.left, val)
# If the target value is greater than the current node's value,
# it must be in the right subtree (due to BST property).
else:
return self.searchBST(root.right, val)
🟦Typescript
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
/**
* Searches for a node with a specific value in a Binary Search Tree (BST).
*
* @param {TreeNode | null} root The root node of the BST. Can be null if the tree is empty.
* @param {number} val The value to search for in the BST.
* @returns {TreeNode | null} The node in the BST whose value is equal to the target value 'val'.
* Returns null if the value is not found in the BST or if the tree is empty.
*/
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
// Base case: If the current node is null (we've reached the end of a branch)
// or if the current node's value matches the target value.
if (!root || root.val === val) {
return root;
}
// If the target value is less than the current node's value,
// it must be in the left subtree (due to BST property).
if (val < root.val) {
return searchBST(root.left, val);
}
// If the target value is greater than the current node's value,
// it must be in the right subtree (due to BST property).
else {
return searchBST(root.right, val);
}
};
🐭Go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* searchBST searches for a node with a specific value in a Binary Search Tree (BST).
*
* @param root *TreeNode The root node of the BST. Can be nil if the tree is empty.
* @param val int The value to search for in the BST.
* @return *TreeNode The node in the BST whose value is equal to the target value 'val'.
* Returns nil if the value is not found in the BST or if the tree is empty.
*/
func searchBST(root *TreeNode, val int) *TreeNode {
// Base case: If the current node is nil (we've reached the end of a branch)
// or if the current node's value matches the target value.
if root == nil || root.Val == val {
return root
}
// If the target value is less than the current node's value,
// it must be in the left subtree (due to BST property).
if val < root.Val {
return searchBST(root.Left, val)
} else if val > root.Val { // Corrected syntax: else if on the same line
return searchBST(root.Right, val)
}
// This should ideally not be reached given the previous conditions,
// but it's good practice to have a final return in case of unexpected input.
return nil
}
If you liked this content I’d appreciate an upvote or a comment. That helps me improve the quality of my posts as well as getting to know more about you, my dear reader.
Muchas gracias!
Follow me for more content like this.
X | PeakD | Rumble | YouTube | Linked In | GitHub | PayPal.me | Medium
Down below you can find other ways to tip my work.
BankTransfer: "710969000019398639", // CLABE
BAT: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
ETH: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
BTC: "33xxUWU5kjcPk1Kr9ucn9tQXd2DbQ1b9tE",
ADA: "addr1q9l3y73e82hhwfr49eu0fkjw34w9s406wnln7rk9m4ky5fag8akgnwf3y4r2uzqf00rw0pvsucql0pqkzag5n450facq8vwr5e",
DOT: "1rRDzfMLPi88RixTeVc2beA5h2Q3z1K1Uk3kqqyej7nWPNf",
DOGE: "DRph8GEwGccvBWCe4wEQsWsTvQvsEH4QKH",
DAI: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875"