Drawing Binary Tree: Exploring Pre-Order & In-Order Traversal

[evinda]

Hi! (Smile)

I am looking at the following exercise:

It is given a binary tree with 8 nodes and keys 2,4,6,8,10,12,14,16.The in-order tree traversal gives this order: 2,4,6,8,10,12,14,16.
The pre-order traversal gives the order: 10,8,2,6,4,16,14,12. Draw the tree. Explain how you drawed it.

That's what I have tried:

View attachment 3608

In a pre-order sequence, the leftmost element is the root of the tree.
By searching the root in the in-order sequence, we can find which elements are on the left side of the root, in the left subtree and which are on the right side of the root, in the right subtree. Could you tell me if it is right? (Thinking)

 

[I like Serena]

Hi! (Smile)

I am looking at the following exercise:

It is given a binary tree with 8 nodes and keys 2,4,6,8,10,12,14,16.The in-order tree traversal gives this order: 2,4,6,8,10,12,14,16.
The pre-order traversal gives the order: 10,8,2,6,4,16,14,12. Draw the tree. Explain how you drawed it.

That's what I have tried:

View attachment 3608

In a pre-order sequence, the leftmost element is the root of the tree.
By searching the root in the in-order sequence, we can find which elements are on the left side of the root, in the left subtree and which are on the right side of the root, in the right subtree. Could you tell me if it is right? (Thinking)

Hey! (Wave)

I believe the in-order of that tree is: 2, 8, 4, 6, 10, 14, 16, 12... but that is not what was given! (Worried)

 

[johng1]

View attachment 3611
You know the root is 10. Now find 10 in the in order sequence. You then know the left subtree has nodes 2,4,6,8 and the right has 12,14. Do it again. The left subtree has root 8. Find 8 in the inorder sequence 2,4,6,8. So you know the left sub tree from 8 has nodes 2,4,6 and the right subtree from 8 is empty. Continue.
It's a standard easy exercise to formalize the above and write a recursive algorithm to construct a binary tree given the in order and pre order sequences. I suggest writing such.

 

[evinda]

So, is this the binary tree? (Thinking)

View attachment 3613

Could you give me also two other orders, for example post-order and in-order, so that I find the binary tree? (Thinking)

 

[johng1]

Sorry, in my previous post I left out 16.

Given the in order sequence and the post order sequence, the idea is very similar to the in order and pre order. Here's an algorithm, actual C code:

/*  Builds the unique binary tree with n nodes given the inorder and post
order traversal sequences of keys in arrays in and post.  Return is
pointer to the tree.
*/
node *build(int *in,int *post,int n)
{
    node *p;
    int i;
    if (!n) {
      return(0);
    }
    p=getNode();
    p->key=post[n-1];
    for (i=0;in[i] != post[n-1];i++)
        ;
    p->left_child=build(in,post,i);
    p->right_child=build(in+i+1,post+i,n-i-1);
    return(p);
}

I repeat. I think you should write such an algorithm for pre order and in order. What about pre order and post order?

 

[evinda]

Sorry, in my previous post I left out 16.
Given the in order sequence and the post order sequence, the idea is very similar to the in order and pre order.

Could you explain me the steps we follow, in order to find the binary tree?
Since $2$ is at the first position of the post-order, it means that it is the leftmost leaf, right? How do we continue? (Thinking)

 

[I like Serena]

So, is this the binary tree? (Thinking)

View attachment 3613

Could you give me also two other orders, for example post-order and in-order, so that I find the binary tree? (Thinking)

Yep! That's it! Good! (Nod)

How about a tree with post-order 8 5 3 1 6 6 8 7 9 5, and in-order 1 8 3 5 6 5 6 9 7 8? (Wondering)

 

[evinda]

Yep! That's it! Good! (Nod)

How about a tree with post-order 8 5 3 1 6 6 8 7 9 5, and in-order 1 8 3 5 6 5 6 9 7 8? (Wondering)

Is this one possible tree? (Thinking)

View attachment 3617

 

[I like Serena]

Is this one possible tree? (Thinking)

https://www.physicsforums.com/attachments/3617

Yep!
And I believe it's the only one! (Party)

 

[evinda]

Yep!
And I believe it's the only one! (Party)

Nice! (Happy) So, couldn't we consider that the root $5$ corresponds to the $5$ of the $4^{th}$ position from the in-order traversal? (Thinking)

 

[I like Serena]

So, couldn't we consider that the root $5$ corresponds to the $5$ of the $4^{th}$ position from the in-order traversal? (Thinking)

Huh? (Wondering)

 

[evinda]

Huh? (Wondering)

We know that $5$ is the root and so we found it at the in-order to see which of the elements are at the left subtree and which of the right, like that:

View attachment 3618

But, there is two times the number $5$.

So, couldn't we also do it like that? (Thinking)

View attachment 3619

 

[I like Serena]

We know that $5$ is the root and so we found it at the in-order to see which of the elements are at the left subtree and which of the right, like that:

But, there is two times the number $5$.

So, couldn't we also do it like that? (Thinking)

Maybe.
Can we? (Wondering) (Thinking) (Sweating)

 

[evinda]

Maybe.
Can we? (Wondering) (Thinking) (Sweating)

I think that we can't do this, because then it will be like that:

View attachment 3621

We will have to put the number $5$ but there isn't one left... Or am I wrong? (Thinking)

 

[I like Serena]

I think that we can't do this, because then it will be like that:

https://www.physicsforums.com/attachments/3621

We will have to put the number $5$ but there isn't one left... Or am I wrong? (Thinking)

I believe you're quite right. (Mmm)
We won't be able to fit in the numbers that are left in the thought balloon. (Angry)