Interview Question
- 0of 0 votes
AnswerAssume the numbers 1 through n are stored in a binary tree T. For the pre-
- inevitablekris September 29, 2014 in United States
order, postorder and inorder traversals the output of a preorder
traversal of T with 5 nodes can be something like 2; 3; 1; 5; 4. We can think of
this output as the \preorder traversal signature" of the tree. Clearly, we can do
the same for both the postorder and inorder traversals.
a. Is the preorder traversal signature of a tree T unique? That is, are there
two trees storing the numbers 1 through n with the same preorder traversal
signature? How about the postorder traversal signature? the inorder traversal
signature? If your answer is yes to any of these questions, provide an expla-
nation.| Report Duplicate | Flag | PURGE
Algorithm
Email me when people comment.
Email me when people comment.
Loading...
An error occurred in subscribing you.
Email me when people comment.
Email me when people comment.
Loading...
An error occurred in subscribing you.
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
The trees aren't specified as binary SEARCH trees, so no. The traversal signatures do not uniquely identify the trees.
For example, with 1, 2, 3. The following signatures would be identical for pre order:
Likewise, inorder
And post-order
Now, if the trees were balanced or binary search trees, I think the traversal would be unique.
- zortlord October 03, 2014