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

Binary Search Trees (BST)

A binary search tree is an ordered binary tree in which keys in the left subtree follow a smaller-key ordering rule and keys in the right subtree follow a larger-key ordering rule. This structure supports efficient searching and updates when its height remains controlled.

Explanation

Overview

A binary search tree is a binary tree in which each node stores a key and follows an ordering property that places smaller keys in its left subtree and larger keys in its right subtree, according to the implementation's comparison rules.

Key concepts

name: Core idea; description: The central focus of binary search trees (bst) is the capability described here: A binary search tree is an ordered binary tree in which keys in the left subtree follow a smaller-key ordering rule and keys in the right subtree follow a larger-key ordering rule. This structure supports efficient searching and updates when its height remains controlled.; name: Problem context; description: Binary Search Trees (BST) is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using binary search trees (bst), check its assumptions, input requirements, expected output, and resource constraints.

Complexity

average: O(log n) for search, insertion, and deletion when the tree is reasonably balanced under typical assumptions.; worstCase: O(n) when the tree becomes highly unbalanced or degenerate.; traversal: O(n) to visit all nodes.; minimumMaximum: O(h), where h is the tree height.

Applications

Ordered dictionaries and sets.; Maintaining sorted collections.; Finding minimum and maximum values.; Range searching.; Predecessor and successor queries.; Educational implementation of ordered tree algorithms.

Advantages

Supports ordered searching.; Provides sorted output through inorder traversal.; Allows dynamic insertion and deletion.; Supports predecessor and successor operations.; Can answer certain range and ordered queries efficiently when balanced.

Limitations

An ordinary BST does not automatically maintain balance.; Sorted insertion order can produce a degenerate tree.; Worst-case operations may become O(n).; Correct duplicate handling requires an explicit policy.; Pointer-based implementations require additional memory.

Example or application

A worked example has not yet been added.

Definition

A binary search tree is a binary tree in which each node stores a key and follows an ordering property that places smaller keys in its left subtree and larger keys in its right subtree, according to the implementation's comparison rules.

Ordering Property

  • Keys in the left subtree of a node must be ordered before that node's key.

  • Keys in the right subtree must be ordered after that node's key.

  • Both left and right subtrees must independently satisfy the BST property.

  • The ordering rule applies to entire subtrees, not only immediate children.

Duplicate Policy

A BST implementation must define how duplicate keys are handled. Common choices include rejecting duplicates, storing a count, or consistently placing equal keys on a specified side.

Node Structure

Key

The value used to maintain the search ordering.

Value

Optional associated information.

Left

Reference to the left child.

Right

Reference to the right child.

Parent

An optional reference to the parent node.

Example Tree

Root

50

Left

Root

30

Left

20

Right

40

Right

Root

70

Left

60

Right

80

Example Explanation

The root is 50. Values smaller than 50 appear in its left subtree, while larger values appear in its right subtree. The same ordering rule is applied recursively at every node.

Search Property

At each node, a comparison determines whether the target is equal to the current key, belongs in the left subtree, or belongs in the right subtree.

Inorder Property

Inorder traversal visits BST keys in nondecreasing order when the duplicate policy and comparison rules are consistent.

Minimum Value

The minimum key is found by following left-child references until no further left child exists.

Maximum Value

The maximum key is found by following right-child references until no further right child exists.

Successor

The inorder successor of a node is the next larger key. If the node has a right subtree, its successor is the minimum key in that subtree.

Predecessor

The inorder predecessor is the next smaller key. If the node has a left subtree, its predecessor is the maximum key in that subtree.

Common Operations

  • Search for a key.

  • Insert a new key.

  • Delete an existing key.

  • Find the minimum and maximum keys.

  • Find inorder predecessors and successors.

  • Traverse keys in sorted order.

Complexity

Average

O(log n) for search, insertion, and deletion when the tree is reasonably balanced under typical assumptions.

Worst Case

O(n) when the tree becomes highly unbalanced or degenerate.

Traversal

O(n) to visit all nodes.

Minimum Maximum

O(h), where h is the tree height.

Advantages

  • Supports ordered searching.

  • Provides sorted output through inorder traversal.

  • Allows dynamic insertion and deletion.

  • Supports predecessor and successor operations.

  • Can answer certain range and ordered queries efficiently when balanced.

Limitations

  • An ordinary BST does not automatically maintain balance.

  • Sorted insertion order can produce a degenerate tree.

  • Worst-case operations may become O(n).

  • Correct duplicate handling requires an explicit policy.

  • Pointer-based implementations require additional memory.

Applications

  • Ordered dictionaries and sets.

  • Maintaining sorted collections.

  • Finding minimum and maximum values.

  • Range searching.

  • Predecessor and successor queries.

  • Educational implementation of ordered tree algorithms.

Important Distinction

Every BST is a binary tree, but not every binary tree is a BST. A BST must satisfy its key-ordering property throughout both subtrees.

Key Concepts

NameDescription

Core idea

The central focus of binary search trees (bst) is the capability described here: A binary search tree is an ordered binary tree in which keys in the left subtree follow a smaller-key ordering rule and keys in the right subtree follow a larger-key ordering rule. This structure supports efficient searching and updates when its height remains controlled.

Problem context

Binary Search Trees (BST) is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using binary search trees (bst), check its assumptions, input requirements, expected output, and resource constraints.

Practice Questions

QuestionAnswer

What is the main purpose of binary search trees (bst)?

A binary search tree is an ordered binary tree in which keys in the left subtree follow a smaller-key ordering rule and keys in the right subtree follow a larger-key ordering rule. This structure supports efficient searching and updates when its height remains controlled.

What should be checked before applying binary search trees (bst)?

For binary search trees (bst), verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of binary search trees (bst) be validated?

Trace a representative binary search trees (bst) 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 binary search trees (bst).

  • Identify the assumptions, inputs, and conditions relevant to binary search trees (bst).

  • Evaluate an application of binary search trees (bst) 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