Is Search in a Binary Search Tree easy or hard?

Search in a Binary Search Tree is classified as an Easy problem. The core requirement is understanding the BST ordering rule and using it to avoid scanning the entire tree. Once the property is applied correctly, the implementation is straightforward.

How to solve Search in a Binary Search Tree in O(n)?

A general binary tree search that checks every node would take O(n) time. However, because the structure is a Binary Search Tree, you can do better by comparing the target with the current node and moving left or right. This reduces the search to O(h), typically O(log n) for balanced trees.

Search in a Binary Search Tree Python or Java solution?

Python and Java solutions follow the same logic: compare the target with the current node and move left or right accordingly. Python implementations often use recursion for brevity, while Java solutions commonly use iterative loops to avoid recursion overhead.

What is the best approach for Search in a Binary Search Tree?

The optimal approach uses the Binary Search Tree property to move left or right depending on the target value. Both recursive and iterative methods achieve O(h) time complexity, where h is the tree height. The iterative version is often preferred because it uses O(1) extra space while recursion uses O(h) stack space.

Is Search in a Binary Search Tree asked at Google/Amazon/Meta?

BST search is a foundational tree problem and frequently appears in interviews at companies like Amazon, Google, Meta, and Microsoft. It is often used as a warm‑up question before more complex BST operations such as insert, delete, or lowest common ancestor.

What data structure is used in Search in a Binary Search Tree?

The problem uses a Binary Search Tree, which is a specialized form of a binary tree where left subtree values are smaller and right subtree values are larger than the current node. This ordering property enables efficient search operations similar to binary search on arrays.

What is the time complexity of Search in a Binary Search Tree?

Searching in a Binary Search Tree takes O(h) time, where h is the height of the tree. In a balanced BST this becomes O(log n). In the worst case, when the tree is skewed like a linked list, the complexity degrades to O(n).

Description Solution Video 6:15

700. Search in a Binary Search Tree

Easy83.1% acceptance5 companies

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

Constraints:

The number of nodes in the tree is in the range [1, 5000].
1 <= Node.val <= 10⁷
root is a binary search tree.
1 <= val <= 10⁷

Asked at 5 companies

Google Amazon Microsoft Meta Bloomberg

Topics

6:15

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

700. Search in a Binary Search Tree

Asked at 5 companies

Topics

Similar problems