700. Search in a Binary Search Tree

Description

Given the root of a binary search tree (BST) and an integer value, the task is to search the BST for the node that contains the given value. If the value is found, return the corresponding node. If the value is not found in the tree, return null or None.

Intuition

In a binary search tree, for any given node, the values of all the nodes in its left subtree are smaller, and the values of all the nodes in its right subtree are larger. This property makes searching in a BST efficient, as you can eliminate half of the tree at each step depending on the value you are searching for.

Approach

1. Start at the root node of the BST.
2. Compare the given value with the current node's value: - If they are equal, return the current node. - If the given value is smaller, move to the left child. - If the given value is larger, move to the right child.
3. Repeat the process until you either find the node with the matching value or reach a null pointer (indicating that the value is not present in the tree).
4. If the value is not found in the tree, return null or None.

Complexity

Time Complexity:

O(h), where h is the height of the tree. In the worst case, this can be O(n) for a skewed tree, but in a balanced tree, it would be O(log n).

Space Complexity:

O(1) for the iterative approach, as no additional space is required other than pointers. If using a recursive approach, the space complexity would be O(h) due to the function call stack.

Code

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        TreeNode* current = root;
        while (current != nullptr) {
            if (val == current->val) {
                return current;
            } else if (val < current->val) {
                current = current->left;
            } else {
                current = current->right;
            }
        }
        return nullptr;
    }
};

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: TreeNode, val: int) -> TreeNode:
        current = root
        while current:
            if val == current.val:
                return current
            elif val < current.val:
                current = current.left
            else:
                current = current.right
        return None

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode current = root;
        while (current != null) {
            if (val == current.val) {
                return current;
            } else if (val < current.val) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return null;
    }
}

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var searchBST = function (root, val) {

    let current = root;
    while (current) {
        if (val === current.val) {
            return current;
        } else if (val < current?.val) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    
    return null;
};