Practice Flashcards
Flip to reveal answersWhat is the binary search tree ordering rule?
Track your progress — Sign up free to save your progress and get smart review reminders based on spaced repetition.
All 5 Flashcards — Binary search trees
Sign up free to track progress and get spaced-repetition review schedules.
Question
What is the binary search tree ordering rule?
Answer
For **every** node, all values in its left subtree are smaller and all in its right subtree are larger — every descendant, not just the children.
Question
Why is a BST search fast?
Answer
Each comparison says which side the value must be on, so an **entire subtree** is discarded without being examined. About log₂ n comparisons when balanced.
Question
What does an in-order traversal give you?
Answer
Every value in **ascending order** — left subtree, node, right subtree — with no sorting step.
Question
What does sorted input do to a BST?
Answer
Every value goes the same direction, so the tree **degenerates into a line**: height n, search O(n), exactly like a linked list.
Question
How is a node with two children deleted?
Answer
It is replaced by its **in-order successor** — the smallest value in its right subtree — which preserves the ordering rule.
Read the notes
Full study notes for Binary search trees
Topic 8.1 hub
Fundamentals of ADTs
More from Topic 8.1
All flashcards in this topic
Computer Science exam skills
Paper structures & tips
Track your progress with spaced repetition
Sign up free — Aimnova tells you exactly which cards to review and when, so you remember everything before your IB exam.
Start Free