0

I'm given a sequence of characters that are from a pre-order traversal of a binary tree. I'm not given the binary but I need to draw the binary tree based on the sequence of characters from the traversals

From this binary tree, Pre-order traversal:

NZLADRUGBY

In-order traversal:

ALDZNURYBG

My thought was that pre-order traversal sequence would be the easiest to derive a binary tree from and I found that the tree had a height of 3 and from the pre-order traversal I can see that the root will be N and it's left sub tree will be Z but after that I'm unsure what to do as there's the possibility that one sub tree could be empty etc.

Is there any easier way to do this?

jn025
  • 989

2 Answers2

1

From the pre-order sequence you know that the root is N. The in-order sequence then tells you that A, L, D, and Z are in the left subtree, and U, R, Y, B, and G are in the right subtree. Now go back to the pre-order sequence: it tells you that Z is the root of the left subtree. The in-order sequence then tells you that all three of the other nodes of the left subtree are to the left of Z. Thus, Z has no right child, and the pre-order sequence tells you that L is its left child. Both sequences then confirm that A is the left child and D the right child of L, and the pre-order sequence tells you that R is the root of the right subtree. At that point you have this much of the tree:

                            N  
                           / \  
                          Z   R  
                         /  
                        L  
                       / \  
                      A   D

Continue in the same way, and you can finish building the tree without too much trouble.

Brian M. Scott
  • 616,228
  • So am I correct in saying that the left sub tree of R is U and right sub tree of R is G. Then U does not have any left or right sub tree and the left sub tree of G is B and right is Y? I wasn't 100% sure if B was left and Y was right – jn025 Apr 30 '15 at 03:06
  • 1
    @joe: Not quite. You have U and G correct, but the in-order sequence tells you that Y and B are both to the left of G. On the other hand, the pre-order sequence tells you that G precedes B and Y in pre-order. The only way to reconcile these facts is to make B the left child of G and Y the left child of B; G has no right child. – Brian M. Scott Apr 30 '15 at 03:17
  • One other thing, I thought the tree had a height of 3? using (log 10 / log 2) to get the height given the number of nodes (10) With the right subtree, the tree then has a height of 4? – jn025 Apr 30 '15 at 06:21
  • 1
    @joe: Yes, the height is $4$. A binary tree with $10$ nodes can have a height as large as $9$; the formula that you have in mind gives you the minimum possible height. – Brian M. Scott Apr 30 '15 at 06:29
0

If you turn the letters into numbers you will see the relation.

First you should note that a binary search tree with an in-order representation will give an ordered array. So for your second representation of the tree you have the mapping: $$NZLADRUGBY \rightarrow 0123456789$$

Now the first representation will be $4310265987$, if you start with 4 and continue to insert the numbers into the binary search tree the final tree will be the original one upon substitution of the numbers by the corresponding letters.

Another way of looking at it is to put parenthesis in the first representation keeping in mind that all the numbers greater than $n$ must be the right branch of $n$ and all the numbers lesser than $n$ must be the left branch. $$4(3102)(65987)$$ $$4(3(102)())(6(5)(987))$$ $$4(3(1(0)(2))())(6(5)(9(87)()))$$ $$4(3(1(0)(2))())(6(5)(9(8(7)())()))$$ And the final tree is: $$N(Z(L(A)(D))())(R(U)(G(B(Y)())()))$$

Alvaro Fuentes
  • 823
  • 7
  • 21