October 11th, 2009 12:05 PM
Binary Tree Traversal Questions
I was given the preorder sequence --> * + / a b c - d e
I was told to draw a binary expression tree which I completed and received the following tree
I was then asked two questions about the tree. Is this tree unique?
/ \ / \
- c d e
unique defined as --> A tree for a sequence is not unique if given that (here, preorder) sequence it is possible to generate a different tree
Do preorder traversal's generate unique trees? why or why not.
The same thing was asked about inorder traversals , but given the following sequence.
a - b * e + c + b
Pay attention to operator precedence, if applicable.
The expression tree I got was as follows
Is this tree unique?
Do inorder sequences produce unique trees? why or why not.
I have no clue whether the trees are really unique, because I can find another tree that will generate the same value, but will not have the same preorder sequence.
Any input is well appreciated, THANK YOU.
Click Here to Expand Forum to Full Width