Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 11: Q5E (page 769)

Using alphabetical order, construct a binary search treefor the words in the sentence “The quick brown fox jumpsover the lazy dog.”

Short Answer

Expert verified

Given,

The first word is"The",make it as the root of the treeand the second word is Quick and Quick is lesser than "The", so will be added as the left child of the "The".

Now the third word is "brown" is lesser than "The", so will move towards the left sub- tree there compare with quick where brown is again lesser (in alphabetical order) so will be added as the left child of quick.

The next word is Fox is lesser than "The” and quick so will be moved to the left sub-tree but it is greater than brown so will be added as the right child of brown.

The next word is jumps is lesser than "The” and quick so will be moved to the left sub-tree but it is greater than brown so will be moved to the right of brown. And it is also greater than Fox so will be added as the right child of Fox.

The next word is Over is lesser than "The” and quick so will be moved to the left sub-tree but it is greater than brown so will be moved to the right of brown. And it is also greater than Foxand Jumps so will be added as the right child of Jumps.

The next word is Lazy is lesser than "The” and quick so will be moved to the left sub-tree but it is greater than brown so will be moved to the right of brown. And it is also greater than Foxand Jumps so will be moved to the right child of Jumps. But Lazy is lesser than “Over”, so will be added as the left child of the "Over".

Step by step solution

Achieve better grades quicker with Premium

  • Unlimited AI interaction
  • Study offline
  • Say goodbye to ads
  • Export flashcards
Start your free trial Skip

Over 22 million students worldwide already upgrade their learning with Vaia!

01

Firstly, use the given information and we shall build a binary search tree for the words.

Given,

The first word is"The",make it as the root of the treeand the second word is Quick and Quick is lesser than "The", so will be added as the left child of the "The".

Now the third word is "brown" is lesser than "The", so will move towards the left sub- tree there compare with quick where brown is again lesser (in alphabetical order) so will be added as the left child of quick.

The next word is Fox is lesser than "The” and quick so will be moved to the left sub-tree but it is greater than brown so will be added as the right child of brown.

The next word is jumps is lesser than "The” and quick so will be moved to the left sub-tree but it is greater than brown so will be moved to the right of brown. And it is also greater than Fox so will be added as the right child of Fox.

The next word is Over is lesser than "The” and quick so will be moved to the left sub-tree but it is greater than brown so will be moved to the right of brown. And it is also greater than Foxand Jumps so will be added as the right child of Jumps.

The next word is Lazy is lesser than "The” and quick so will be moved to the left sub-tree but it is greater than brown so will be moved to the right of brown. And it is also greater than Foxand Jumps so will be moved to the right child of Jumps. But Lazy is lesser than “Over”, so will be added as the left child of the "Over".

02

Final conclusion

The last word is dog is lesser than "The” and quick so will be moved to the left sub-tree but it is greater than brown so will be moved to the right of brown. And dog is lesser than Fox, so will be added as the left child of the "Fox".

Thus, the completed binary tree will look like:

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Suppose that \({{\bf{d}}_{\bf{1}}}{\bf{,}}{{\bf{d}}_{\bf{2}}}{\bf{,}}...{\bf{,}}{{\bf{d}}_{\bf{n}}}\) are n positive integers with sum \({\bf{2n - 2}}\). Show that there is a tree that has n vertices such that the degrees of these vertices are \({{\bf{d}}_{\bf{1}}}{\bf{,}}{{\bf{d}}_{\bf{2}}}{\bf{,}}...{\bf{,}}{{\bf{d}}_{\bf{n}}}\).

Which of these are well-formed formulae over the symbols \(\left\{ {{\bf{x,y,z}}} \right\}\) and the set of binary operators \(\left\{ {{\bf{ \ast , + ,}} \circ } \right\}\)?

  1. \({\bf{ \ast + + xyx}}\)
  2. \( \circ {\bf{xy \ast xz}}\)
  3. \({\bf{ \ast }} \circ {\bf{xz \ast \ast xy}}\)
  4. \({\bf{ \ast + }} \circ {\bf{xx}} \circ {\bf{xxx}}\)

How many comparisons are needed to locate or to add each of the words in the search tree for Exercise 2, starting fresh each time?

a) palmistry

b) etymology

c) paleontology

d) glaciology

a. Explain how backtracking can be used to determine whether a simple graph can be colored using \(n\) colors.

b. Show, with an example, how backtracking can be used to show that a graph with a chromatic number equal to \({\bf{4}}\) cannot be colored with three colors, but can be colored with four colors.

Can there be two different simple paths between the vertices of a tree?
See all solutions

Recommended explanations on Math Textbooks

Applied Mathematics

Read Explanation

Statistics

Read Explanation

Logic and Functions

Read Explanation

Probability and Statistics

Read Explanation

Theoretical and Mathematical Physics

Read Explanation

Discrete Mathematics

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free