3
$\begingroup$

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?

  1. preorder and postorder
  2. inorder and postorder
  3. preorder and inorder
  4. level order and postorder

I've read that inorder is necessary to draw unique tree, well, I drawn the different tree with given options. I concluded that option $(2)$ and $(3)$ is true.

Can you explain formally please, why is tree not uniquely possible with given preorder and postorder traversal ?

$\endgroup$
7
$\begingroup$

Consider the trees shown below:

                    1                      1  
                   /                      /  
                  2                      2  
                 /                        \  
                3                          3

Both have preorder $123$, and both have postorder $321$, but they’re not the same binary tree. More generally, if a node has only one child, preorder and postorder do not contain enough information to determine whether that child is a left child or a right child.

$\endgroup$
  • $\begingroup$ @Mithlesh: You're welcome. $\endgroup$ – Brian M. Scott Nov 17 '15 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.