[Math] Drawing a binary tree based on a traversal sequence

trees

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?

Best Answer

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.

Related Question