What is a binary search tree?

A binary tree where each node's left subtree contains smaller keys and its right subtree contains greater keys, assuming distinct keys.

How does tree height affect BST operations?

Search, insertion, and deletion follow paths through the tree, so their time is proportional to its height.

What is the worst-case time for an operation in an ordinary, unbalanced BST?

$O(n)$, because the tree can become a chain of $n$ nodes.

What is a self-balancing BST?

A BST that restructures during updates to keep its height bounded, commonly by $O(\log n)$.

How does tree sort produce ordered output?

It inserts input keys into a BST and then performs an inorder traversal.

Data structures & algorithmsLesson 1 of 2 in the course Trees and hashing

Binary Search Trees: Ordering, Operations, Height, and Uses

5 flashcards · 5 quiz questions · 5 match pairs · 5 fill-in sentences · English

Save course

Lesson progress

0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

A binary search tree (BST) organizes keys so that comparisons can guide a search toward one part of the tree at a time. This lesson introduces the BST ordering rule, explains how tree shape affects performance, and connects the structure to common uses.

A BST is a rooted binary tree: each node has at most two children, called its left and right children. Each node stores a key. For a node with key $k$ , every key in its left subtree is less than $k$ , and every key in its right subtree is greater than $k$ . This lesson uses the strict-order convention for distinct keys; implementations that allow duplicate keys must define a consistent policy for where duplicates go.

All flashcards

What is a binary search tree?: A binary tree where each node's left subtree contains smaller keys and its right subtree contains greater keys, assuming distinct keys.
How does tree height affect BST operations?: Search, insertion, and deletion follow paths through the tree, so their time is proportional to its height.
What is the worst-case time for an operation in an ordinary, unbalanced BST?: $O(n)$ , because the tree can become a chain of $n$ nodes.
What is a self-balancing BST?: A BST that restructures during updates to keep its height bounded, commonly by $O(\log n)$ .
How does tree sort produce ordered output?: It inserts input keys into a BST and then performs an inorder traversal.

Quiz questions

When searching a BST for a key smaller than the current node's key, which subtree should be searched next?Answer: The left subtree, because it contains smaller keys.
In a nonempty BST, where is a new distinct key inserted?Answer: At the empty child position reached by following its search path.
Which method can remove a node with two children while preserving BST order?Answer: Replace it with its inorder successor or predecessor.
What order does an inorder traversal use, and what does it produce for a BST with distinct keys?Answer: Left subtree, root, right subtree; keys are visited in increasing order.
What is the purpose of a self-balancing BST such as an AVL or red-black tree?Answer: To keep the tree's height logarithmic and worst-case operations efficient.

Based on the Wikipedia article Binary search tree, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

All Data structures & algorithms lessons

Data structures & algorithmsBinary Heaps: Ordering, Array Operations, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Data structures & algorithmsMerge Sort: Algorithms, Complexity, Variants, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →

Summary

All flashcards

Quiz questions

More in Data structures & algorithms