Which node satisfies this property?

[evinda]

Hi! (Smirk)

It is a given binary tree $T$, for each node $ n$ of which , all the keys of the nodes of the left subtree of $n$ are greater than the key of $n$ and all the keys of the nodes of the right subtree of $n$ are smaller than the key of $n$.

We suppose that $T$ contains the nodes $3,5,7,9,11,13,15,17$ and we are given that the pre-order traversal of the tree, gives as result the numbers in this row: $9,17,11,15,13,5,7,3$.
I have to draw the tree.

How can I find the first node $n$, which satisfies the first property? (Thinking)

 

[I like Serena]

Hi! (Smirk)

It is a given binary tree $T$, for each node $ n$ of which , all the keys of the nodes of the left subtree of $n$ are greater than the key of $n$ and all the keys of the nodes of the right subtree of $n$ are smaller than the key of $n$.

We suppose that $T$ contains the nodes $3,5,7,9,11,13,15,17$ and we are given that the pre-order traversal of the tree, gives as result the numbers in this row: $9,17,11,15,13,5,7,3$.
I have to draw the tree.

How can I find the first node $n$, which satisfies the first property? (Thinking)

Hey! (Happy)

A pre-order visits first the root of each node, then the left subtree (beginning with its root), and then the right subtree. (Nerd)

So we can already tell that $9$ is the root of the tree.
To which subtree will $17$ belong? (Wondering)

 

[evinda]

Hey! (Happy)

A pre-order visits first the root of each node, then the left subtree (beginning with its root), and then the right subtree. (Nerd)

So we can already tell that $9$ is the root of the tree.
To which subtree will $17$ belong? (Wondering)

So, does this means that $17$ and $11$ will be the children of $9$?
If so, can we conclude from a pre-order which will be the left child and which the right? (Thinking)

 

[I like Serena]

So, does this means that $17$ and $11$ will be the children of $9$?
If so, can we conclude from a pre-order which will be the left child and which the right? (Thinking)

$17$ will definitely be a child of $9$.
What does the problem statement say about whether it should be left or right? (Wondering)

As for $11$, that comes later, but I don't think it can be a child of $9$. (Shake)

 

[evinda]

$17$ will definitely be a child of $9$.
What does the problem statement say about whether it should be left or right? (Wondering)

Since the keys of the nodes of the left subtree are greater than the key, does this mean that 17 is the left child of 9?

As for $11$, that comes later, but I don't think it can be a child of $9$. (Shake)

How can we find then the right child of 9?

What do we conclude then from the fact that 11 is at the third position of the pre-order? (Thinking)

 

[I like Serena]

Since the keys of the nodes of the left subtree are greater than the key, does this mean that 17 is the left child of 9?

Yes. (Nod)

How can we find then the right child of 9?

What do we conclude then from the fact that 11 is at the third position of the pre-order? (Thinking)

Suppose we look at the tree:

    9
  /   \
17     11

What is then its pre-order? (Wondering)
Does the tree satisfy the problem statement criteria?

Can you think of another tree that has the same pre-order? (Wondering)

 

[evinda]

Suppose we look at the tree:

    9
  /   \
17     11

What is then its pre-order? (Wondering)

It is 9,17,11, right? (Thinking)

Does the tree satisfy the problem statement criteria?

Yes, the problem statement criteria are satisfied.. (Nod) Or am I wrong? (Thinking)

Can you think of another tree that has the same pre-order? (Wondering)

Isn't this the only one? (Thinking)

 

[I like Serena]

It is 9,17,11, right? (Thinking)

Yep! (Nod)

and all the keys of the nodes of the right subtree of $n$ are smaller than the key of $n$.

Yes, the problem statement criteria are satisfied.. (Nod) Or am I wrong? (Thinking)

Since $11$ is in the right sub tree of $9$, is it smaller? (Wondering)

Isn't this the only one? (Thinking)

How about:

     9
    /
  17
 /
11

Or:

     9
    /
  17
    \
    11

(Wondering)

 

[evinda]

Since $11$ is in the right sub tree of $9$, is it smaller? (Wondering)

Oh no! I am sorry! (Blush)

How about:

     9
    /
  17
 /
11

Or:

     9
    /
  17
    \
    11

(Wondering)

Oh yes, you are right! (Tmi)

 

[evinda]

So, the first number of the pre-order is always the root, right? (Thinking)
Then, do we know that the next two numbers are the children of the root?
Or do we know this only for the second one? Or for none of them? (Thinking)

 

[I like Serena]

Oh yes, you are right! (Tmi)

Which of these satisfies the criteria of the problem statement? (Wondering)

 

[evinda]

Which of these satisfies the criteria of the problem statement? (Wondering)

This:

     9
    /
  17
    \
    11

satisfies the criteria of the problem statement, right? (Thinking)

 

[I like Serena]

This:

     9
    /
  17
    \
    11

satisfies the criteria of the problem statement, right? (Thinking)

Yep! (Nod)

 

[evinda]

Yep! (Nod)

Nice! And 15 will be now the left child of 11? Or am I wrong? (Thinking)

 

[evinda]

So, will the tree be like that?

View attachment 3579

Or am I wrong? (Thinking)

 

[I like Serena]

So, will the tree be like that?

Yep! (Party)

 

[evinda]

Yep! (Party)

Great! (Party) And this is the only tree, that can be found, right? (Thinking)

 

[I like Serena]

Great! (Party) And this is the only tree, that can be found, right? (Thinking)

When you were building up the tree, did you have any choices to make? (Wondering)

 

[evinda]

When you were building up the tree, did you have any choices to make? (Wondering)

No (Shake) So, it is the only possible tree, right? (Smile)

 

[I like Serena]

No (Shake) So, it is the only possible tree, right? (Smile)

Yes! (Nod)

 

[evinda]

Yes! (Nod)

Nice, thank you very much! (Smirk)