Binary Search Trees: Smaller Keys Left, Larger Keys Right

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 15.1 Free with a free account

Binary Search Trees: Smaller Keys Left, Larger Keys Right

Data Structures and Algorithms · Chapter 15: Balanced Search TreesSection 15.1 · lesson 63 of 8711 min · free with a free account

← Real Applications Built on HashingNext lesson: AVL Trees: Rebalancing After Every Insertion and Deletion →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Search, insertion, deletion and sorted traversal in binary search trees.

  • State the binary search tree property and check it over whole subtrees
  • Implement recursive search and insertion that store returned links
  • Delete leaves, one-child nodes and two-child nodes correctly
  • Explain why every operation costs order h and how sorted input hurts

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,566 words). Read along, or search it.

Opening Question

Search Like an Array, Insert Like a List

A library app keeps 50,000 call numbers in a sorted array. Finding one takes about sixteen halvings. But a new book means shifting thousands of entries, to open a gap in the right place. A linked list takes the new book instantly, by rewiring two links. But finding a book means walking the list, one entry at a time. Can one structure search like the array, and insert like the list?

Definition

The Ordering Property

A binary search tree tries to do both. It's built from linked nodes, so an insert rewires links, and nothing shifts. And its keys are arranged so that one comparison, at each node, rules out a whole branch. The arrangement is a single rule, the ordering property. For every node with key k, every key in its left subtree is smaller than k. And every key in its right subtree is larger than k. Duplicates aren't stored here. Inserting a key a second time changes nothing.

Worked Example

Eight Keys Inserted in Order

Here's a tree built by inserting 50, 30, 70, 20, 40, 60, 80, and 65, in that order. 50 is the root. Everything in its left subtree, 20, 30, and 40, is smaller. Everything on its right is larger. And the same rule holds inside every subtree. Below 70, the keys 60 and 65 sit on its left, and 80 on its right.

Common Mistake

The Rule Covers Whole Subtrees

The rule is about whole subtrees, not just a node and its two children. That's easy to misjudge. Take a root of ten, with left child five and right child twenty, and give five a right child, fifteen. Locally, everything looks fine. Fifteen is larger than five, so it sits on five's right. But fifteen lives in ten's left subtree, and it's larger than ten. So this is not a valid search tree. A search for fifteen goes right at ten, and never finds it. A correct checker hands each node a lower and an upper bound, inherited from all of its ancestors. Fifteen must lie between five and ten. It doesn't, so the check fails.

Search

One Comparison Rules Out a Branch

Searching uses the rule directly. Compare the target with the current node. If it's smaller, go left, and the whole right subtree is never looked at. If it's larger, go right. Search for 60. It's larger than 50, so go right. Smaller than 70, so go left. And there's 60: three keys examined. Now search for 45. Smaller than 50: left. Larger than 30: right. Larger than 40, so go right again. But 40 has no right child. The search falls off the tree, so 45 isn't stored. Either way, a search examines at most one key per level.

Insertion

Storing the Returned Link

Insertion is a search that ends at an empty spot. Walk down exactly as a search would, and when you reach a missing child, hang the new node there. In Java, the recursive version returns the root of each subtree, and the caller stores it back. n dot left equals insert of n dot left. That assignment is what links the new node into the tree. Forget to store the result, and the parent still points where it did before. The new node is created, and then lost. And inserting a key that's already there changes nothing. The tree still holds eight keys.

Quick Check

Where Thirty-Five Hangs

Quick check, on the same tree. Insert 35. Where does the new node go? Pause, and decide. The left child of 40. 35 is smaller than 50, so go left. Larger than 30, so go right. Smaller than 40, so go left, and that spot is empty. It can't hang under 20. Any key larger than 30 belongs in 30's right subtree.

Extremes and Successors

Minimum, Maximum and Next Larger Key

The rule also makes the extremes easy to find. The smallest key is as far left as you can go: 20. The largest is as far right as you can go: 80. The successor of a key is the next larger key in the tree. It has two cases. If the node has a right child, the successor is the minimum of its right subtree: go right once, then left as far as possible. The successor of 50 is 60. If there's no right child, it's the nearest ancestor you reach by coming up from a left child. 40 has no right child. Climb: 40 sits in 50's left subtree, so its successor is 50. Likewise, the successor of 65 is 70. And 80, the maximum, has none.

In Code

Successor Without Parent Links

In code, there's no need for links back to the parent. Walk down from the root, just as a search would, and remember the last node where you went left. That node is the smallest key seen so far that's larger than the target, which is exactly the successor. It even works for a key that isn't stored. The successor of 55 is 60, the next larger key.

Deletion Overview

Three Cases by Child Count

Deletion is the hardest operation. The tree must still obey the rule, and it must still be connected. First, find the node, with the same search. Then it depends on how many children the node has. There are three cases.

Case One

Removing a Leaf

Case one, a leaf. Delete 20, down at the bottom left. Nothing hangs below it, so it's simply removed. Its parent's left link becomes null. Every other key stays exactly where it was, so the rule still holds everywhere.

Case Two

Replacing a Node by Its Only Child

Case two, one child. Delete 60. It has a right child, 65, and no left child. Replace the node by its child. 65 moves up into 60's place, and 70's left link now points to it. That's safe, because every key in the child's subtree was already on the correct side of every ancestor.

Case Three

Copying the Successor's Key

Case three, two children. Delete 50, the root. Simply unlinking it would leave two subtrees, and only one link from above to hold them. Instead, copy the successor's key into the node. The successor of 50 is 60, so 60 is copied into the root. Then delete the old 60 from the right subtree. The successor never has a left child, so that's always an easy case one or case two. The mirror image works too: copy the predecessor, the largest key on the left.

Quick Check

Deleting Root Forty

Quick check, on a new tree. Delete its root, 40, with the successor rule. Which key ends up in the root? Pause, and decide. Fifty. 40 has two children, so it takes its successor's key. Go right once, to 60, then left as far as possible, to 50. 50's old node is a leaf, so it's simply removed. 35 is the predecessor, which the mirror rule would use. And 60 is just 40's right child, not the next larger key.

Inorder Traversal

Sorted Output and Tree Sort

An inorder traversal visits the left subtree, then the node, then the right subtree. On a search tree, it lists the keys in increasing order. Why? Everything on the left is smaller than the node, and everything on the right is larger. So left, node, right comes out sorted, and the same argument holds inside every subtree. Insert eight keys in no particular order: 45, 12, 78, 3, 29, 56, 91, 20. The inorder walk gives 3, 12, 20, 29, 45, 56, 78, 91. Insert everything, then read it back in order: that's a sorting method called tree sort. Its cost depends on the shape of the tree.

Shape Problem

Sorted Arrival Builds a Chain

The shape depends on the order the keys arrive in, not just on which keys they are. Insert 10, 20, 30, 40, 50, in sorted order. Each new key is the largest so far, so it goes to the right of the last node. The result is a chain, five levels tall. It's really a linked list. The same keys in the order 30, 10, 50, 20, 40 give only three levels.

Measured Results

Tall Trees Do Seventy Times the Work

How much does that cost? In one test with 2,000 keys, the tree built from sorted keys was 2,000 levels tall. An average search examined about 1,000 keys. The same keys in random order gave 23 levels, and an average search examined about 13 keys. The sorted tree did more than seventy times the work. A chain has another cost. Insertion is recursive, so the recursion is as deep as the tree. Inserting 200,000 sorted keys ran out of call stack, with a StackOverflowError.

Cost

Every Operation Costs Order h

So every operation costs order h, where h is the number of levels. That's search, insert, delete, min, max, and successor. In a well-shaped tree, h is about log n. In a chain, h is n, and building it takes order n squared. Real data often arrives in patterns: dates, serial numbers, already sorted exports. What's needed is a tree that keeps itself balanced, whatever the arrival order. Everything in this lesson, the rule, search, successor, and the three deletion cases, carries over to such a tree unchanged.

Key Takeaways

Rule, Operations and Height

To sum up. Every key on a node's left is smaller, and every key on its right is larger, in every subtree. Search and insert follow one path down, and insertion stores the new link back into the parent. Deletion has three cases: a leaf, one child, and two children, where the successor's key is copied in. An inorder traversal lists the keys in sorted order. And every operation costs order h: sorted arrival makes a chain, with h equal to n.

Think About It

Unsorted Keys That Still Build a Tall Tree

Here's something to think about. The keys 1, 5, 2, 4, 3 are not in sorted order. How tall is the tree they build? And what does that say about the idea that only sorted data is dangerous?

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Binary Search Trees: Smaller Keys Left, Larger Keys Right

What is the binary search tree property?
Every key in a node's left subtree is smaller than the node's key, and every key in its right subtree is larger. The rule covers whole subtrees, not just direct children: a root of 10 with left child 5, where 5 has a right child of 15, passes the parent-child check but breaks the rule, because 15 sits in 10's left subtree. A correct validator passes allowed lower and upper bounds down the tree.
How do you delete a node with two children from a binary search tree?
Replace the node's key with its successor's key, then delete the successor from the right subtree. The successor is the smallest key in the right subtree, found by stepping right once and then left as far as possible, and it has no left child, so removing it is one of the easy cases. For example, deleting root 50 whose right subtree's smallest key is 60 puts 60 at the root.
Why does an inorder traversal of a binary search tree give sorted order?
Inorder visits the left subtree, then the node, then the right subtree, and the ordering property places every smaller key on the left and every larger key on the right. Inserting 45, 12, 78, 3, 29, 56, 91 and 20 and then traversing inorder prints 3, 12, 20, 29, 45, 56, 78, 91. Inserting keys and reading them back this way is called tree sort.
Why must recursive BST insertion assign the returned node to a child link?
When the recursion reaches an empty spot, it creates the new node and returns it, and only the assignment links that node into the tree. A correct version is Node insert(Node n, int k) { if (n == null) return new Node(k); if (k < n.key) n.left = insert(n.left, k); else if (k > n.key) n.right = insert(n.right, k); return n; }. Dropping the assignment leaves the new node unattached.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →