|
-
October 11th, 2009, 12:05 PM
#1
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
Code:
*
/ \
+ -
/ \ / \
- c d e
/ \
a b
I was then asked two questions about the tree. Is this tree unique?
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
Code:
+
/ \
+ b
/ \
- c
/ \
a *
/ \
b e
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.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|