algoadvance

Leetcode 700. Search in a Binary Search Tree

Problem Statement

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:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Input: root = [4,2,7,1,3], val = 5
Output: []

Constraints:

Clarifying Questions

  1. Can the BST contain duplicate values?
    • No, it’s guaranteed by the problem constraints.
  2. What should be the output format if the node is found?
    • Return the subtree rooted at the found node.
  3. What should be returned if the node is not found?
    • Return null.

Strategy

To solve this problem efficiently, we can leverage the properties of a Binary Search Tree (BST):

To search for a value in a BST:

  1. Start at the root node.
  2. Compare the value to be found (val) with the value of the current node:
    • If val is equal to the node’s value, return the current node.
    • If val is less than the node’s value, search in the left subtree.
    • If val is greater than the node’s value, search in the right subtree.

This approach results in a recursive or iterative search with a time complexity of O(h), where h is the height of the tree. In the worst case, for a completely unbalanced tree, it will be O(n).

Time Complexity

Code

Here is the implementation of the solution in 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) {
        // Base case: root is null or root's value is the one we're looking for
        if (root == null || root.val == val) {
            return root;
        }
        
        // If `val` is less than the root's value, search in the left subtree
        if (val < root.val) {
            return searchBST(root.left, val);
        }
        
        // If `val` is greater than the root's value, search in the right subtree
        return searchBST(root.right, val);
    }
}

This implementation uses recursion to traverse the BST and find the node with the given value. If the node is found, it returns the subtree rooted at that node; otherwise, it returns null.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI