Mon Prof Augmenté
Smaller left, larger right
Age 17 · Technology
A binary search tree stores keys so that every key in a node’s left subtree is smaller than that node’s key and every key in its right subtree is larger. This lets you find a key by choosing left or right at each node, without checking every node.
This picture is part of the full library
Every lesson is open to everyone for 7 days after it is published. This one came out on October 23, 2026: its text stays readable here, and its picture opens with a subscription.
The app is free. A subscription opens every lesson, in every school year.
In the picture
- The root: the first key every search compares against
- Left child: smaller than the root, so it goes on the left
- Right child: larger than the root, so it goes on the right
- A leaf in the right subtree: larger than the root but smaller than its parent, so it hangs on that parent’s left
Examples
- Guessing a number from 1 to 100 when each answer is "higher" or "lower" rules out half of what is left
- Looking up a word in a paper dictionary by opening the middle and going earlier or later
Key takeaways
- The rule holds for whole subtrees, not just a node’s direct children
- In a well-balanced tree, a search only checks about one node per level
Quiz: Smaller left, larger right (Age 17)
-
In a binary search tree, which keys can appear anywhere in the left subtree of a node whose key is 50?
-
A binary search tree has root 50, and the root’s right child is 80. Where does a new key 60 go?
-
When you search for a key in a well-balanced binary search tree, roughly how many nodes do you check?
The answers, each with its explanation, are in the app. This lesson has left the free week, so its quiz is part of the subscription.
Free app, optional subscription
App Store Google Play
Carry on in the app
At least one new illustrated lesson every weekday for your child’s year, with its quiz and a reminder at 6:15 pm.
Your child’s teacher does not use My Enhanced Teacher yet?
Tell them about it
