700. Search in a Binary Search Tree

[songyy5517]

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: []

Intuition The problem mainly examines the properties of binary search tree (BST). As we know, for each node in a binary search tree, all the nodes in a node's left subtree are less than itself, while all the nodes in its right subtree are greater than itself. Based on this property, we can search for the target node from the root, if the current node is greater than the target node, than move to its left subtree; otherwise, move to its right subtree.

[songyy5517]

Approach: Binary Search in BST

1. Exception handling;
2. Search for the target node, starting from the root node, while the current node is not null: （1）If the current node is equal to the target node, then return the current node; （2）If the current node is less than the target node, move to its right subtree; （3）If the current node is greater than the target node, move to its left subtree;
3. Return null;

Complexity Analysis

• Time complexity: $O(\log_2N)$ in the average case, the depth of a binary search tree is $\log_2N$ under average circumstances; In the worst case, the binary search degenerates into a linked list, whose depth is $N$ , which makes the search process take $O(N)$ time.
• Space complexity: $O(1)$ , no extra variables are defined.

[songyy5517]

/**
 * 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) {
        // Intuition: Search of BST
        // 1. Exception handling
        if (root == null)
            return null;

        // 2. Search the target node
        while (root != null){
            if (root.val == val)
                return root;

            root = root.val > val ? root.left : root.right;
        }

        return null;
    }
}

[songyy5517]

2024/6/10