✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-088

Searching in Binary Search Trees

Searching in a binary search tree uses key comparisons to eliminate one subtree at each step. The search begins at the root and follows either the left or right child until the target is found or a null reference is reached.

Explanation

Overview

BST searching is an algorithm that locates a specified key by using the ordering property of a binary search tree.

Key concepts

name: Core idea; description: The central focus of searching in binary search trees is the capability described here: Searching in a binary search tree uses key comparisons to eliminate one subtree at each step. The search begins at the root and follows either the left or right child until the target is found or a null reference is reached.; name: Problem context; description: Searching in Binary Search Trees is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using searching in binary search trees, check its assumptions, input requirements, expected output, and resource constraints.

Space complexity

An iterative search uses O(1) auxiliary space. A recursive search uses O(h) call-stack space, where h is the tree height.

Applications

Searching ordered records.; Dictionary and set implementations.; Checking whether a value exists.; Finding values in sorted collections.; Implementing predecessor and successor operations.

Limitations

Maintaining the required structural invariants adds implementation complexity and can affect update costs.; An implementation of searching in binary search trees can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.; For searching in binary search trees, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.

Common mistakes

Searching both subtrees even though the BST ordering rule allows one to be eliminated.; Using an incorrect comparison direction.; Failing to handle a null root.; Assuming every BST has O(log n) search time.; Using inconsistent comparison rules during insertion and searching.

Example or application

A worked example has not yet been added.

Definition

BST searching is an algorithm that locates a specified key by using the ordering property of a binary search tree.

Core Principle

If the target key is smaller than the current node's key, search the left subtree. If it is larger, search the right subtree. If both keys are equal according to the comparison rules, the target has been found.

Search Algorithm

  • Start at the root.

  • If the current node is null, the key is not present.

  • Compare the target with the current node's key.

  • If equal, return the current node or its associated value.

  • If the target is smaller, move to the left child.

  • If the target is larger, move to the right child.

  • Repeat until the key is found or the search reaches a null reference.

Recursive Pseudocode

SEARCH(node, key):
if node == null or node.key == key:
return node
if key < node.key:
return SEARCH(node.left, key)
return SEARCH(node.right, key)

Iterative Pseudocode

SEARCH(root, key):
current = root
while current != null:
if key == current.key:
return current
if key < current.key:
current = current.left
else:
current = current.right
return null

Example Tree

Root

50

Left

Root

30

Left

20

Right

40

Right

Root

70

Left

60

Right

80

Example Search

Target

60

Comparisons

  • Compare 60 with 50: 60 is larger, so move right.

  • Compare 60 with 70: 60 is smaller, so move left.

  • Compare 60 with 60: the keys match.

Result

The key 60 is found after three node comparisons.

Unsuccessful Search

If the algorithm reaches a null child reference without finding the key, the target does not exist in the tree.

Average Complexity

O(log n) when the BST is reasonably balanced.

Worst Case Complexity

O(n) when the BST is degenerate, because the search may visit nearly every node.

Space Complexity

An iterative search uses O(1) auxiliary space. A recursive search uses O(h) call-stack space, where h is the tree height.

Comparison Cost

The stated complexity assumes key comparisons take constant time. Comparing long strings or complex objects may require additional time.

Search Optimizations

  • Maintain a balanced tree when predictable search performance is required.

  • Use an iterative search to avoid recursive call-stack overhead.

  • Choose a consistent comparison function.

  • Ensure the tree's ordering property remains valid after every update.

Common Mistakes

  • Searching both subtrees even though the BST ordering rule allows one to be eliminated.

  • Using an incorrect comparison direction.

  • Failing to handle a null root.

  • Assuming every BST has O(log n) search time.

  • Using inconsistent comparison rules during insertion and searching.

Applications

  • Searching ordered records.

  • Dictionary and set implementations.

  • Checking whether a value exists.

  • Finding values in sorted collections.

  • Implementing predecessor and successor operations.

Key Concepts

NameDescription

Core idea

The central focus of searching in binary search trees is the capability described here: Searching in a binary search tree uses key comparisons to eliminate one subtree at each step. The search begins at the root and follows either the left or right child until the target is found or a null reference is reached.

Problem context

Searching in Binary Search Trees is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using searching in binary search trees, check its assumptions, input requirements, expected output, and resource constraints.

Limitations

  • Maintaining the required structural invariants adds implementation complexity and can affect update costs.

  • An implementation of searching in binary search trees can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.

  • For searching in binary search trees, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.

Practice Questions

QuestionAnswer

What is the main purpose of searching in binary search trees?

Searching in a binary search tree uses key comparisons to eliminate one subtree at each step. The search begins at the root and follows either the left or right child until the target is found or a null reference is reached.

What should be checked before applying searching in binary search trees?

For searching in binary search trees, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of searching in binary search trees be validated?

Trace a representative searching in binary search trees case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Learning Objectives

  • Explain the central idea and purpose of searching in binary search trees.

  • Identify the assumptions, inputs, and conditions relevant to searching in binary search trees.

  • Evaluate an application of searching in binary search trees for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures