Ordered Binary Tree of Strings

Question

These values are entered into an ordered binary tree: Mercury, Venus, Earth, Mars, Jupiter, Saturn and Uranus.

The resulting binary tree is supposed to be this.

          Mercury
        /         \
    Earth         Venus
       \           /
      Jupiter   Saturn
         \        \
        Mars     Uranus

Is there any reason for this order? Shouldn't Jupiter be under the Venus branch?

The given tree is incorrect for the given insertion order - Mars should be a right child of Earth and Jupiter should be a left child of Mars because the Jupiter node won't exist when inserting Mars. See this question for the correct ordering - Binary Search Tree of Strings (before balancing). — Bernhard Barker
– Bernhard Barker, Commented Dec 12, 2013 at 22:15

chepner · Accepted Answer · 2012-07-28 14:08:14Z

1

By "ordered binary tree", I assume you mean a binary search tree. As long as the tree satisfies the following criteria:

1. The key in a node is greater than (or equal to) any key stored in its left subtree.
2. The key in a node is less than (or equal to) any key stored in its right subtree.

then the exact structure of the tree depends on the order in which the keys are added and the exact algorithm used to construct the tree.

However, you indicate that you believe that Jupiter should occur in the subtree of Venus. What is your ordering criteria? The tree you show is valid if the names are being compared alphabetically.

answered Jul 28, 2012 at 14:08

chepner

538k77 gold badges594 silver badges746 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user1028145 Over a year ago

I see, that I was what I am wondering if they are ordered alphabetically or just random inserted into the tree. I take it its done by alphabetical order.

Collectives™ on Stack Overflow

Ordered Binary Tree of Strings

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related