Jobs

Interviews

Discussions

Search in a Binary Search Tree

Easy

Apple

2 views

Topics:

TreesBinary Search

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST whose value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Example 1:

Consider the following BST:

If val = 2, the expected output is the subtree rooted at node 2:

    2
   / \
  1   3

Example 2:

Using the same BST:

If val = 5, the expected output is null because a node with value 5 does not exist in the BST.

Describe an algorithm to efficiently find the node with value val in the BST. Analyze the time and space complexity of your solution. Discuss any edge cases that need to be handled.

Search in a Binary Search Tree

Easy

Apple

2 views

Topics:

TreesBinary Search

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST whose value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Example 1:

Consider the following BST:

If val = 2, the expected output is the subtree rooted at node 2:

    2
   / \
  1   3

Example 2:

Using the same BST:

If val = 5, the expected output is null because a node with value 5 does not exist in the BST.

Describe an algorithm to efficiently find the node with value val in the BST. Analyze the time and space complexity of your solution. Discuss any edge cases that need to be handled.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values stored in the nodes of the Binary Search Tree?
Can the tree be empty, and if so, what should I return in that case?
If the target value appears multiple times in the tree, should I return the first node I encounter, or is there a specific node I need to return?
What should I return if the target value is not found in the tree?
Is the tree guaranteed to be a valid Binary Search Tree?

Brute Force Solution

Approach

Let's say you're looking for a specific book in a library organized like a family tree. The most basic way is to simply check every single book until you find the one you want. This is essentially what a brute force approach does.

Here's how the algorithm would work step-by-step:

Start by looking at the first book at the very top of the library tree.
If it's the book you're searching for, great, you're done!
If it's not, check the book to the left.
If you don't find your book, then you check the book to the right.
Keep repeating the process: check the book, then check to the left, then to the right, moving down the tree until you find the book you're looking for.
If you reach a point where there are no more books to check in that direction (left or right), go back to the previous level and explore other branches.
If you have gone through every book in the library and still haven't found the one you're looking for, it means the book is not in the library.

Code Implementation

def search_in_binary_search_tree_brute_force(root, target):
    if root is None:
        return None

    nodes_to_visit = [root]

    while nodes_to_visit:
        current_node = nodes_to_visit.pop(0)

        if current_node.val == target:
            return current_node

        # Add left child to the queue if it exists
        if current_node.left:

            nodes_to_visit.append(current_node.left)

        # Add right child to the queue if it exists
        if current_node.right:

            nodes_to_visit.append(current_node.right)

    # If the target is not found after visiting all nodes.
    return None

Big(O) Analysis

Time Complexity

O(n) – The provided approach resembles a brute-force tree traversal, where each node is visited at most once. In the worst-case scenario, we might need to examine every node in the binary search tree. If 'n' represents the number of nodes in the tree, the algorithm could potentially visit all 'n' nodes. Therefore, the time complexity is directly proportional to the number of nodes, resulting in O(n) time complexity.

Space Complexity

O(N) – The provided plain English explanation describes a brute-force, depth-first search through a binary search tree. In the worst-case scenario, if the target element is not present or located at the deepest level, the algorithm might explore every node. The implicit recursion stack will grow to a maximum depth proportional to the height of the tree, which in the worst-case (e.g., a skewed tree) can be equal to N, where N is the number of nodes in the tree. Therefore, the maximum space occupied by the call stack is O(N). The algorithm does not create any other significant auxiliary data structures.

Optimal Solution

Approach

The efficient way to search a special tree is to use its structure to guide you directly to the target. Each step eliminates a large portion of the tree, making the search very fast. This approach focuses on navigating directly towards the target like a guided missile.

Here's how the algorithm would work step-by-step:

Begin at the very top of the tree.
Compare the value you are searching for with the value at your current location.
If the value you are searching for is smaller, go to the left branch because everything on the left is smaller.
If the value you are searching for is larger, go to the right branch because everything on the right is larger.
If the value you are searching for matches the value at your current location, you have found it! Return the current location.
Repeat steps 2-5 until you either find the value or reach the end of a branch without finding it. If you reach the end without finding the value, it doesn't exist in the tree.

Code Implementation

def search_bst(root, target_value):
    current_node = root

    while current_node:
        # If target is smaller, go left
        if target_value < current_node.val:

            current_node = current_node.left

        # If target is larger, go right
        elif target_value > current_node.val:

            current_node = current_node.right

        # Value found!
        else:

            return current_node

    return None

Big(O) Analysis

Time Complexity

O(log n) – The algorithm searches for a value in a Binary Search Tree (BST) by traversing down the tree. In the best and average cases, each comparison halves the search space. Therefore, the number of comparisons is proportional to the height of the tree. A balanced BST has a height of log n, where n is the number of nodes. Thus, the time complexity is O(log n).

Space Complexity

O(1) – The search algorithm iteratively traverses the binary search tree. It uses a constant amount of extra memory regardless of the tree's size (N, where N is the number of nodes in the tree). The algorithm does not create any auxiliary data structures like lists or hash maps. The space used is only for storing a few variables to keep track of the current node during the traversal, leading to constant auxiliary space.

Edge Cases

Case	How to Handle
Empty tree (root is null)	Return null immediately as the target cannot be found in an empty tree.
Target value is smaller than the smallest value in the BST	The algorithm should traverse to the leftmost leaf and terminate correctly when the target is not found.
Target value is larger than the largest value in the BST	The algorithm should traverse to the rightmost leaf and terminate correctly when the target is not found.
BST with only one node and target matches the node's value	The algorithm should return the single node if its value matches the target.
BST with only one node and target does not match the node's value	The algorithm should return null if the single node's value does not match the target.
Target value is present multiple times in the BST (duplicates)	The algorithm should return the first node encountered during traversal with the target value, as BST search typically only finds the first matching node.
Extremely skewed BST (essentially a linked list)	The algorithm's time complexity degrades to O(n) in the worst case (skewed tree), which must be acknowledged, but traversal still works correctly.
Integer overflow when comparing large target value or node values	While unlikely with typical integer ranges, consider using long if potential overflow is a concern, especially with given node values.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values stored in the nodes of the Binary Search Tree?
Can the tree be empty, and if so, what should I return in that case?
If the target value appears multiple times in the tree, should I return the first node I encounter, or is there a specific node I need to return?
What should I return if the target value is not found in the tree?
Is the tree guaranteed to be a valid Binary Search Tree?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the first book at the very top of the library tree.
If it's the book you're searching for, great, you're done!
If it's not, check the book to the left.
If you don't find your book, then you check the book to the right.
Keep repeating the process: check the book, then check to the left, then to the right, moving down the tree until you find the book you're looking for.
If you reach a point where there are no more books to check in that direction (left or right), go back to the previous level and explore other branches.
If you have gone through every book in the library and still haven't found the one you're looking for, it means the book is not in the library.

Code Implementation

def search_in_binary_search_tree_brute_force(root, target):
    if root is None:
        return None

    nodes_to_visit = [root]

    while nodes_to_visit:
        current_node = nodes_to_visit.pop(0)

        if current_node.val == target:
            return current_node

        # Add left child to the queue if it exists
        if current_node.left:

            nodes_to_visit.append(current_node.left)

        # Add right child to the queue if it exists
        if current_node.right:

            nodes_to_visit.append(current_node.right)

    # If the target is not found after visiting all nodes.
    return None

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Begin at the very top of the tree.
Compare the value you are searching for with the value at your current location.
If the value you are searching for is smaller, go to the left branch because everything on the left is smaller.
If the value you are searching for is larger, go to the right branch because everything on the right is larger.
If the value you are searching for matches the value at your current location, you have found it! Return the current location.
Repeat steps 2-5 until you either find the value or reach the end of a branch without finding it. If you reach the end without finding the value, it doesn't exist in the tree.

Code Implementation

def search_bst(root, target_value):
    current_node = root

    while current_node:
        # If target is smaller, go left
        if target_value < current_node.val:

            current_node = current_node.left

        # If target is larger, go right
        elif target_value > current_node.val:

            current_node = current_node.right

        # Value found!
        else:

            return current_node

    return None

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty tree (root is null)	Return null immediately as the target cannot be found in an empty tree.
Target value is smaller than the smallest value in the BST	The algorithm should traverse to the leftmost leaf and terminate correctly when the target is not found.
Target value is larger than the largest value in the BST	The algorithm should traverse to the rightmost leaf and terminate correctly when the target is not found.
BST with only one node and target matches the node's value	The algorithm should return the single node if its value matches the target.
BST with only one node and target does not match the node's value	The algorithm should return null if the single node's value does not match the target.
Target value is present multiple times in the BST (duplicates)	The algorithm should return the first node encountered during traversal with the target value, as BST search typically only finds the first matching node.
Extremely skewed BST (essentially a linked list)	The algorithm's time complexity degrades to O(n) in the worst case (skewed tree), which must be acknowledged, but traversal still works correctly.
Integer overflow when comparing large target value or node values	While unlikely with typical integer ranges, consider using long if potential overflow is a concern, especially with given node values.