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?Code:* / \ + - / \ / \ - c d e / \ a b
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?Code:+ / \ + b / \ - c / \ a * / \ b e
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.


Reply With Quote
Bookmarks