Re: insert number in binary tree

bbbb said:

thank you so much for you effort!

by the word sequence i mean the problem that gave us on the exams that
i can't solve it that says...

we give you the binary tree that has 10 nodes as shown below..

0
/ \
0 0
/ \ / \
0 0 0 0
/ \ \
0 0 0

in which order must be the following numbers when we insert them so
that the tree that will come out will be a binary search tree? write
your steps
10 15 25 40 45 60 70 80 90

and i can't solve it..
do you have any perhaps any idea?
Thanks again a lot

That's a different problem. And a fairly easy one, you'll be glad to know.
Unfortunately, your diagram is unclear, and in any case you don't have
sufficient data to fill every node indicated on the diagram, so I can't
answer your specific question. I can, however, explain to you how to do
it.

Start by placing your values in order (as you have done):

10 15 25 40 45 60 70 80 90

Now, starting at root, count the number of nodes in the left subtree. Take
that many values from the beginning of your list, and "mark" them as
belonging to that left subtree. Take the next value from the list. That's
your root. Everything else belongs in the right subtree.

Then recurse.

So let's say, for example, that we had a tree looking like this:


???
/ \
??? ???
/ \ / \
??? ??? ??? ???
/ \ \ / /
??? ??? ??? ??? ???

If this diagram looks like a mess, switch to a fixed-pitch font such as
Courier or Courier New. If it /still/ looks like a mess, that's just tough
luck.

The question I am about to answer is this: given twelve numbers: 100, 110,
120, 130, 140, 150, 160, 170, 180, 190, 200, 210 - in which order must we
add them to a binary search tree, to get the tree layout shown above?

We start off by looking at the left subtree:

ROOT
/
??? (right subtree censored for now)
/ \
??? ???
/ \ \
??? ??? ???

Here we see six values in the left subtree. Each of these values (and no
others) must be less than the value stored in the root. So they must be,
in some order, 100, 110, 120, 130, 140, 150. And the root value must be
160. The remaining values (170, 180, 190, 200, 210) belong in the right
subtree.

160
/
??? (right subtree censored for now)
/ \
??? ???
/ \ \
??? ??? ???

100, 110, 120, 130, 140, 150

We can think of this as the same problem all over, with a smaller tree:

current subtree root
/
??? (right subsubtree censored for now)
/ \
??? ???

Clearly the three nodes to the left must be 100, 110, 120, in some order,
giving 130 as the subtree root.

130
/
???
/ \
??? ???

100 110 120

We can think of this as the same problem all over, with a smaller tree:

current subsubtree root
/
??? (right subsubsubtree censored for now)

Clearly the node to the left must be 100, and the root is 110:

110
/
100

Now let's return to the next level up, which we left as:

130
/
???
/ \
??? ???

100 110 120

We now know it's

130
/
110
/ \
100 ???

120

so there's only one place left for the 120:

130
/
110
/ \
100 120

Let's go one more level up:

160
/
130 (right subtree censored for now)
/ \
110 ???
/ \ \
100 120 ???

140, 150

You should have no trouble working out where 140 and 150 go.

Then we have to consider the right subtree of the (ultimate) root:

160
/ \
130 ???
/ \ / \
110 140 ??? ???
/ \ \ / /
100 120 150 ??? ???

170, 180, 190, 200, 210

Using exactly the same technique on the right subtree, we conclude that the
ultimate tree looks like this:

160
/ \
130 190
/ \ / \
110 140 180 210
/ \ \ / /
100 120 150 170 200


So - in what order must they be added? Well, there are lots of orders that
will work, probably millions, but not *all* orders will work.

Certainly we have to start off with the root node, 160. That has to be
first.

The best way to describe the rest is to say that, to get that shape tree,
and after placing the 160 value at the root:

130 must be added BEFORE 100, 110, 120, 140, 150, but apart from that it
doesn't matter;
190 must be added BEFORE 170, 180, 200, 210, but apart from that it doesn't
matter;
110 must be added BEFORE 100 and 120, but apart from that it doesn't
matter;
140 must be added BEFORE 150, but apart from that it doesn't matter;
180 must be added BEFORE 170, but apart from that it doesn't matter;
210 must be added BEFORE 200, but apart from that it doesn't matter.

So, for example, this order will work: 160 130 190 180 170 210 110 200 100
140 150 120 - but it is not the only order that will work.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
.

Relevant Pages

  • Re: insert number in binary tree
    ... does anyone know how do we insert numbers in a binary tree? ... If this subtree is empty, ... promoting the right successor of the root will fix this: ...
    (comp.programming)
  • Copy-on-write tree data structure
    ... Let Node be a suitably defined data structure. ... // A call to this function should take the tree rooted at root and set ... // its nth child to be the tree rooted at subtree. ...
    (comp.lang.c)
  • Copy-on-write tree data structure
    ... Let Node be a suitably defined data structure. ... // A call to this function should take the tree rooted at root and set ... // its nth child to be the tree rooted at subtree. ...
    (comp.lang.cpp)
  • Re: Creating a keytab with ktpass under a Computer account
    ... tree, right click and select New -> Query. ... root, select subtree and type a query like ...
    (comp.protocols.kerberos)
  • Re: Part 1 (of 3): What are major aspects of evolutionary theory?
    ... >>4) by assuming monophyly of two divisions of the tree ... >>each of these is a clade and that the root lies between them. ... which is commonly rooted by outgroup. ...
    (talk.origins)