700. Search in a Binary Search Tree

EasyTreeBinary Search TreeBinary Tree
Leetcode Link

Problem Description

The given problem is about searching for a node with a specific value in a Binary Search Tree (BST). In a BST, every node's left child is less than the node's value, and the right child's value is greater. We are required to implement a function that takes the root of a BST and an integer val as its input. The function should search for a node in the BST whose value is equal to val. If such a node is found, our function should return the subtree that is rooted at this node. In case there is no node with the value equal to val, the function should return null.

Intuition

The intuition behind the provided solution leverages the properties of a BST. In a BST, for any given node, all values in its left subtree are smaller and all values in its right subtree are larger than the node's value. This characteristic greatly optimizes the search operation.

Here's how we can think about the solution step-by-step:

  1. We start at the root of the BST.
  2. If the root is null, it means we've reached the end of a branch without finding the value, so we return null.
  3. If the root's value is equal to val, we've found the node we're looking for, and we return the root (thus returning the subtree rooted at the found node).
  4. If the root's value is less than val, due to the BST property, we know that if a node with value val exists, it must be in the right subtree. So, we recursively search in the right subtree for val.
  5. Conversely, if the root's value is greater than val, we search in the left subtree.

By recursively subdividing the problem, we either find the node we're looking for or conclude it doesn't exist in the BST. This approach is efficient because it discards half of the BST from consideration in each step.

Learn more about Tree, Binary Search Tree and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Solution Approach

The solution is a classic example of the divide-and-conquer strategy, which is a recurring pattern in algorithms that deal with trees. This strategy involves breaking down a problem into smaller subproblems of the same type and solving them independently.

The provided solution uses a simple recursive function that follows the binary search property according to which, for any node:

  • All values in the left subtree are less than the node's value.
  • All values in the right subtree are greater than the node's value.

Here's a step-by-step breakdown of the code and its logic:

  1. The function searchBST takes in two parameters: root, which is a TreeNode object, and val, which is the integer value you are searching for in the tree.
  2. The base cases handle two situations:
    • If root is None, this indicates that we've reached a leaf's child (which is None), and because we haven't returned earlier, we know val is not present in the tree. Therefore, we return None.
    • If root.val is equal to val, then we have found the node we are looking for, and we return the current root node, which by definition will have the desired subtree rooted at it.
  3. The decision cases dictate the flow of the recursive search:
    • If the current node's value is less than val, then, according to BST properties, we should search in the right subtree. Consequently, we make a recursive call to searchBST(root.right, val).
    • Otherwise, if the current node's value is greater than val, the required node must be in the left subtree. Hence, we make a recursive call to searchBST(root.left, val).

The recursive calls continue until the base case is satisfied, which will either return the desired node (TreeNode object) if the value val is found, or None if it is absent in the BST.

The solution approach is efficient and takes advantage of the BST properties to minimize the search space with each recursive call, leading to a time complexity of O(h), where h is the height of the BST.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Example Walkthrough

Let's illustrate the solution approach with a small example.

Suppose we have a Binary Search Tree and an integer value val that we want to search for in the BST.

BST:

1   6
2  / \
3 4   8
4/ \   \

3 5 9

Let's say val = 5. According to the solution approach:

  1. Begin at the root of the BST, which has the value 6.
  2. Compare the root's value (6) with val (5). Since 5 is less than 6, look into the left subtree based on BST property.
  3. The new root node to consider is now the left child of the previous root, which has the value 4.
  4. Compare the new root's value (4) with val (5). Since 5 is greater than 4, we need to search in the right subtree of node 4 based on BST property.
  5. The new root node to consider is now the right child of the previous root, which has the value 5.
  6. Compare the new root's value (5) with val (5). They are equal, hence we have found the node with the value we are looking for.
  7. Return the subtree rooted at the node with value 5.

Since we have found the value, our function will return the subtree rooted at node 5, which, since node 5 is a leaf, is just the node itself:

15

If val were not in the BST, for instance val = 7, the search process would eventually reach a point where the next recursive call would try to access a child of a leaf node (which is null), leading to step 2 of our solution approach and returning None.

Solution Implementation

1class TreeNode:
2    def __init__(self, value=0, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7class Solution:
8    def search_bst(self, root: TreeNode, value: int) -> TreeNode:
9        """
10        Searches for a node with a given value in a binary search tree.
11
12        :param root: TreeNode, the root node of the binary search tree
13        :param value: int, the value to search for
14        :return: TreeNode, the node containing the value, or None if not found
15        """
16        # If root is None, or root's value matches the search value, return root.
17        if root is None or root.value == value:
18            return root
19      
20        # If the value to be searched is greater than the root's value, search in the right subtree,
21        # otherwise, search in the left subtree.
22        if root.value < value:
23            return self.search_bst(root.right, value)
24        else:
25            return self.search_bst(root.left, value)
26
1/**
2 * Definition for a binary tree node.
3 */
4public class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8
9    TreeNode() {}
10
11    TreeNode(int val) {
12        this.val = val;
13    }
14
15    TreeNode(int val, TreeNode left, TreeNode right) {
16        this.val = val;
17        this.left = left;
18        this.right = right;
19    }
20}
21
22class Solution {
23    /**
24     * Searches for a node with a given value in a Binary Search Tree.
25     * @param root The root of the binary search tree.
26     * @param val The value to search for.
27     * @return The subtree rooted with the target value; or null if value doesn't exist in the tree.
28     */
29    public TreeNode searchBST(TreeNode root, int val) {
30        // Base case: if the root is null or root value equals the search value, return the root.
31        if (root == null || root.val == val) {
32            return root;
33        }
34
35        // If the value of the root is less than the search value, search in the right subtree.
36        // Otherwise, search in the left subtree.
37        return root.val < val ? searchBST(root.right, val) : searchBST(root.left, val);
38    }
39}
40
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5   public:
6    int val;                // The value stored in the tree node
7    TreeNode *left;         // Pointer to the left child
8    TreeNode *right;        // Pointer to the right child
9
10    // Constructor to initialize the node with default values
11    TreeNode() : val(0), left(nullptr), right(nullptr) {}
12
13    // Constructor to initialize the node with a given value
14    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
15
16    // Constructor to initialize the node with given value, left and right children
17    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
18};
19
20class Solution {
21   public:
22    /**
23     * Searches the Binary Search Tree for a node with the given value.
24     *
25     * @param root A pointer to the root node of the BST.
26     * @param value The value to search for in the BST.
27     * @return The TreeNode pointer to the found node or nullptr if not found.
28     */
29    TreeNode* searchBST(TreeNode* root, int value) {
30        // Base case: If the root is nullptr or the root's value is the one we're searching for
31        if (!root || root->val == value) {
32            return root;
33        }
34      
35        // If the given value is greater than the root's value, search in the right subtree.
36        if (root->val < value) {
37            return searchBST(root->right, value);
38        }
39      
40        // If the given value is smaller than the root's value, search in the left subtree.
41        return searchBST(root->left, value);
42    }
43};
44
1// Definition for a binary tree node.
2class TreeNode {
3    val: number;         // The value stored in the tree node
4    left: TreeNode | null;   // Pointer to the left child
5    right: TreeNode | null;  // Pointer to the right child
6
7    // Constructor to initialize the node with default values or with given values for val, left, and right.
8    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
9        this.val = val;
10        this.left = left;
11        this.right = right;
12    }
13}
14
15/**
16 * Searches for a node with the given value in a Binary Search Tree.
17 * 
18 * @param root A TreeNode representing the root of the BST.
19 * @param value The value to search for in the BST.
20 * @return A TreeNode pointer to the found node or null if not found.
21 */
22function searchBST(root: TreeNode | null, value: number): TreeNode | null {
23    // Base case: if the root is null or the root's value matches the search value
24    if (!root || root.val === value) {
25        return root;
26    }
27
28    // If the search value is greater than the root's value, search in the right subtree.
29    if (value > root.val) {
30        return searchBST(root.right, value);
31    }
32
33    // If the search value is less than the root's value, search in the left subtree.
34    return searchBST(root.left, value);
35}
36
Not Sure What to Study? Take the 2-min Quiz๏ผš

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Time and Space Complexity

The time complexity of the given code is O(h) where h is the height of the tree. This is because in the worst case, we may have to traverse from the root to the leaf which involves going through the height of the tree. In the case of a balanced binary search tree, this would be O(log n), where n is the number of nodes in the tree. However, if the tree is skewed, the height h can become n, resulting in a time complexity of O(n).

The space complexity of the code is also O(h) due to the recursive nature of the algorithm. Each recursive call adds a new layer to the call stack, which means that in the worst case, we could have h recursive calls on the stack at the same time. In the best case of a balanced tree, this would be O(log n), while in the worst case of a skewed tree, this would be O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

Binary Search Tree Intro

Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ