Sorting with Trees: Benefits and Limitations | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 11.3 Free with a free account

Sorting with Trees: Benefits and Limitations

Discrete Mathematics · Chapter 11: Trees, Spanning Trees, and Minimum Cost NetworksSection 11.3 · lesson 73 of 878 min · free with a free account

← Tree Traversal MethodsNext lesson: Spanning Trees and Their Properties →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Sorted order is always one traversal away - until it isn't.

  • Build a binary search tree by insertion
  • Sort with an in-order traversal
  • Bound tree sort's cost by the tree's height
  • Explain when tree sort degenerates

Transcript

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

Trees, Spanning Trees, and Minimum Cost Networks

Sorting with Trees: Benefits and Limitations

Section eleven point two noted that in-order traversal has a famous use. This section cashes that in. We'll use a binary search tree to sort data, work out what that costs in the best case, and see where it can quietly fall apart.

The Opening Problem

A Leaderboard That Never Stops

A live leaderboard for an online competition receives player scores continuously while the event is underway, not as one batch at the end. At any moment, it must show the current standings in sorted order, even as new scores keep arriving. Classical sorting algorithms, like merge sort, assume the entire dataset is already in memory before sorting begins. A binary search tree offers something different. It stays organized as data streams in, one value at a time, with the sorted order always just one traversal away.

Definition 11.3.1

Binary Search Trees, Recap

Recall that a binary search tree is a binary tree, where every node's key is greater than every key in its left subtree, and less than every key in its right subtree. We'll assume the keys are distinct. And an in-order traversal, left subtree, then the node, then the right subtree, visits every key in strictly increasing order. That one fact is the entire basis of the sorting technique.

Worked Example

7 Scores, 10 Comparisons

Suppose the leaderboard receives seven scores, in the order forty-two, seventeen, sixty-three, eight, twenty-nine, fifty-one, seventy-seven. Each insertion follows a path from the root, comparing as it goes, until it reaches an empty spot. Forty-two goes into the empty tree as the root. Seventeen is less than forty-two, so it goes left. Sixty-three is larger, so it goes right. Each of those took one comparison. Eight goes left of forty-two, then left of seventeen. Twenty-nine goes left of forty-two, then right of seventeen. Fifty-one and seventy-seven go right of forty-two, then left and right of sixty-three. Two comparisons each. That's ten comparisons in all, and the tree has height two, perfectly balanced. Traverse it in order, and the scores come out eight, seventeen, twenty-nine, forty-two, fifty-one, sixty-three, seventy-seven. Strictly increasing, as promised.

Listing 11.3.1

Tree Sort in Python

Here's tree sort in Python. Insert walks down the tree recursively. It goes left when the key is smaller, and right otherwise, until it finds an empty spot, where it creates a new node. In-order is the traversal from the last section, so it isn't repeated here. And tree sort just inserts every value into an initially empty tree, then reads the result back out with an in-order traversal. On the seven scores, it prints them in increasing order.

11.3.2

What Tree Sort Costs

Tree sort's cost has two parts: building the tree, and traversing it. The traversal always visits each of the n nodes once, so it's theta of n, whatever the tree's shape. The interesting cost, the one that varies dramatically, is building the tree. Here's the key proposition. Inserting a key into a tree of height h takes at most h plus one comparisons. Why? An insertion follows a single path from the root, making one comparison at each node it passes. A root-to-leaf path in a tree of height h passes at most h plus one nodes. So if the tree stays balanced, with height around log base two of n, the total insertion cost is order n log n. But if the height grows as large as n minus one, the total can be as bad as theta of n squared.

11.3.3

Sorted Input Builds a Chain

When does the height get that large? Suppose the same seven scores arrive already sorted: eight, seventeen, twenty-nine, and so on up to seventy-seven. Eight becomes the root. Seventeen is larger, so it goes right. Twenty-nine is larger than both, so it goes right twice. Every new value is larger than everything already in the tree. So each insertion walks the entire chain of right children before landing at the bottom. The comparisons are zero, one, two, and so on up to six. That totals twenty-one, which is n times n minus one over two, for n equals seven. Compare that with just ten for the balanced order. On the left is the balanced tree, with height two. On the right, the same seven keys form a chain of height six.

Definition 11.3.2

A Degenerate Tree Is a Linked List

A binary tree is degenerate if every node has at most one child. A degenerate tree on n nodes has height exactly n minus one, and each node links only to the next. Structurally, it's indistinguishable from a singly linked list. And sorted input isn't some rare corner case. Incrementing record IDs, timestamps, or a leaderboard export that was sorted before being fed back in, would all arrive in exactly this order.

Listing 11.3.2

Measuring Both Orders

This program confirms both outcomes. It counts one comparison for every node an insertion passes, and measures the height in edges, with an empty tree counting as minus one. For the order forty-two, seventeen, sixty-three and so on, it reports height two and ten comparisons. For the sorted order, it reports height six and twenty-one comparisons, exactly as traced.

Table 11.3.1

Insertion Order Decides the Cost

So the same values can cost very different amounts, depending on the order they arrive in. For a uniformly random order, the expected height is theta of log n. That result is due to Devroye, in nineteen eighty-six, and its proof needs probability tools beyond this course. So the expected total cost is order n log n. For already sorted input, in either direction, the height is n minus one, and the cost is theta of n squared. And if you build the tree deliberately, say by always inserting a remaining median, the height stays about log base two of n, guaranteeing theta of n log n.

The Central Limitation

No Defense Against Bad Order

That's the central limitation of tree sort. Its performance depends entirely on insertion order, and a plain binary search tree has no defense against an unlucky, or entirely ordinary, order. Merge sort splits its input by position, not by comparison results. So its recursion depth is always about log n, however the input is arranged. A plain binary search tree makes every placement by comparison alone. It has no way to notice or correct a growing imbalance. So systems that need guaranteed logarithmic performance use self-balancing trees instead. Java's TreeMap, and typical C++ standard map implementations, use red-black trees. These do extra bookkeeping on every insertion, to keep the height within a constant factor of log base two of n, whatever order the data arrives in.

Takeaways

Only as Good as Its Height

To summarize. Because an in-order traversal of a binary search tree always yields sorted keys, inserting n values and traversing them is a complete sorting algorithm. That's tree sort. Each insertion costs at most the tree's height plus one comparisons. So a random order gives expected order n log n performance, while sorted input degenerates into a linked list, costing theta of n squared. And guaranteed performance needs a self-balancing tree. Here's something to think about. A classmate says tree sort is just as good as merge sort, since both are called n log n algorithms. But their program regularly receives data that's already sorted, or nearly sorted. Where exactly does that reasoning break down? Does merge sort's guarantee depend on the input's arrangement? What would need to change about how the tree is built? And would randomly shuffling the data first be enough on its own?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 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 Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 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

Discrete Mathematics 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 Sorting with Trees: Benefits and Limitations

How do you sort numbers using a binary search tree?
Insert each number into an initially empty binary search tree, then read the keys back with an in-order traversal. Each insertion starts at the root and goes left for a smaller key and right for a larger one until it reaches an empty spot. In-order traversal visits keys in strictly increasing order, so the output is sorted.
Why is the cost of tree sort bounded by the height of the tree?
Inserting a key into a tree of height h takes at most h+1 comparisons, because an insertion follows one root-to-leaf path and makes one comparison per node. The in-order traversal costs \Theta(n) for any shape. So building the tree dominates, and it costs about n times the height.
What happens when you build a binary search tree from already sorted data?
The tree degenerates into a chain of height n-1, which behaves like a linked list. Every new key is larger than all earlier keys, so each insertion walks down the whole chain. The comparisons total 0+1+\cdots+(n-1)=\frac{n(n-1)}{2}, so the cost is \Theta(n^2). For n=7 that is 21 comparisons, compared with 10 for a balanced order.
Is tree sort as good as merge sort since both are O(n \log n)?
No, because tree sort's O(n\log n) cost holds only when the tree stays balanced, such as for random input. Sorted input can push it to \Theta(n^2). Merge sort splits by position, so its recursion depth stays about \log n for any arrangement. Self-balancing trees such as red-black trees fix this by keeping the height near \log_2 n.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 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 Discrete Mathematics 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 Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 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 4 credits in Discrete Mathematics.

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

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →