Pular para o conteúdo principal

Search in a Binary Search Tree

Given the reference to the root of a binary search tree and a search value, return the reference to the node that contains the value if it exists and null otherwise.

Note: All values in the binary search tree will be unique.

Example(s)​

Example 1:

Tree:
        3
       / \
      1   4
Search value: 1
Output: Reference to node containing 1

Example 2:

Tree:
        7
       / \
      5   9
         / \ 
        8   10
Search value: 9
Output: Reference to node containing 9

Example 3:

Tree:
        8
       / \
      6   9
Search value: 7
Output: null

Recursive Solution​

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * Search in a binary search tree recursively
 * @param {TreeNode} root - Root of the BST
 * @param {number} val - Value to search
 * @return {TreeNode} - Node containing the value or null
 */
function searchBST(root, val) {
  if (!root) return null;
  if (root.val === val) return root;
  if (val < root.val) return searchBST(root.left, val);
  return searchBST(root.right, val);
}

Complexity (Recursive)​

  • Time Complexity: O(h) - Where h is the height of the tree (O(n) in worst case)
  • Space Complexity: O(h) - Recursion stack space

Iterative Solution​

// Definition for a binary tree node.
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

/**
 * Search in a binary search tree iteratively
 * @param {TreeNode} root - Root of the BST
 * @param {number} val - Value to search
 * @return {TreeNode} - Node containing the value or null
 */
function searchBSTIterative(root, val) {
  let current = root;
  while (current) {
    if (current.val === val) return current;
    if (val < current.val) {
      current = current.left;
    } else {
      current = current.right;
    }
  }
  return null;
}

Complexity (Iterative)​

  • Time Complexity: O(h) - Where h is the height of the tree (O(n) in worst case)
  • Space Complexity: O(1) - Constant extra space

Interactive Code Runner​

Test the Recursive Solution​

JavaScript Recursive Solution


// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = (val===undefined ? 0 : val)
  this.left = (left===undefined ? null : left)
  this.right = (right===undefined ? null : right)
}

/**
* Search in a binary search tree recursively
* @param {TreeNode} root - Root of the BST
* @param {number} val - Value to search
* @return {TreeNode} - Node containing the value or null
*/
function searchBST(root, val) {
if (!root) return null;
if (root.val === val) return root;
if (val < root.val) return searchBST(root.left, val);
return searchBST(root.right, val);
}

// Create test tree: [3,1,4]
const root = new TreeNode(3);
root.left = new TreeNode(1);
root.right = new TreeNode(4);

// Test cases
console.log(searchBST(root, 1)?.val); // 1
console.log(searchBST(root, 4)?.val); // 4
console.log(searchBST(root, 7)); // null
Output:
Click "Run Code" to execute the code and see the results.

Test the Iterative Solution​

JavaScript Iterative Solution


// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = (val===undefined ? 0 : val)
  this.left = (left===undefined ? null : left)
  this.right = (right===undefined ? null : right)
}

/**
* Search in a binary search tree iteratively
* @param {TreeNode} root - Root of the BST
* @param {number} val - Value to search
* @return {TreeNode} - Node containing the value or null
*/
function TreeNode(val, left, right) {
  this.val = (val===undefined ? 0 : val)
  this.left = (left===undefined ? null : left)
  this.right = (right===undefined ? null : right)
}

function searchBSTIterative(root, val) {
let current = root;
while (current) {
  if (current.val === val) return current;
  if (val < current.val) {
    current = current.left;
  } else {
    current = current.right;
  }
}
return null;
}

// Create test tree: [7,5,9,null,null,8,10]
const root = new TreeNode(7);
root.left = new TreeNode(5);
root.right = new TreeNode(9);
root.right.left = new TreeNode(8);
root.right.right = new TreeNode(10);

// Test cases
console.log(searchBSTIterative(root, 9)?.val); // 9
console.log(searchBSTIterative(root, 8)?.val); // 8
console.log(searchBSTIterative(root, 6)); // null
Output:
Click "Run Code" to execute the code and see the results.

Takeaways​

  • BST Property utilization leads to efficient search by pruning half the tree at each step
  • Iterative approach saves space compared to recursive, especially for deep trees
  • Unique values simplify the search without handling duplicates
  • Edge cases include empty tree, root match, and value not present
  • Height dependency means balanced BST ensures O(log n) average time