Code Logo

BST Search

Published at25 Jul 2026
Created by
Binary Search Tree Easy 1 views
Like0

Given an array representing a Binary Search Tree (BST) stored in level-order and a target value, determine whether the target exists in the tree. Return true if found, false otherwise.

For example, in the BST [5, 3, 8, 1, 4, 7, 9], the value 4 exists (return true) and the value 6 does not exist (return false). An empty tree returns false for any target. The tree uses the standard level-order array representation where index 0 is the root, 2i+1 is the left child, and 2i+2 is the right child.

Searching a BST is one of the most fundamental operations in computer science. The BST property — left child < parent < right child — allows you to eliminate half of the remaining tree at each step, making search extremely efficient. This property is what makes BSTs superior to linear data structures for search operations.

For the array-based representation, you can search by starting at the root (index 0) and traversing left or right based on comparisons. Move to index 2i+1 if the target is smaller than the current node, or index 2i+2 if it is larger. Continue until you find the target or go out of bounds.

Edge cases include an empty array (return false), searching for a value at the root (always the first comparison), and searching for a value not present (the search terminates when the index goes out of bounds or when a missing child is reached).

Example Input & Output

Example 1
Input
[1,2,3,4,5],6
Output
false
Explanation

6 not in tree

Example 2
Input
[],5
Output
false
Explanation

Empty tree

Example 3
Input
[1,2,3,4,5],3
Output
true
Explanation

3 exists

Example 4
Input
[5],5
Output
true
Explanation

Root match

Example 5
Input
[10,20,30],15
Output
false
Explanation

Not found

Algorithm Flow

Recommendation Algorithm Flow for BST Search

Solution Approach

Traverse the BST by comparing the target with each node and moving to the appropriate child index.

function solution(arr, target) {
  var i = 0;
  while (i < arr.length) {
    if (arr[i] === target) return true;
    if (target < arr[i]) i = 2 * i + 1;
    else i = 2 * i + 2;
  }
  return false;
}

Start at index 0 (the root). While the index is within bounds, compare the current value with the target. If they match, return true. If the target is smaller, move to the left child (2i+1). If larger, move to the right child (2i+2). If the loop exits without finding the target, return false.

Time complexity is O(log n) for balanced trees, O(n) worst case for skewed trees. Space complexity is O(1).

Best Answers

java
class Solution {
    public boolean solution(int[] nums, int t) {
        for(int n:nums)if(n==t)return true;return false;
    }
}