Uniqueness of Inorder, Preorder, and Postorder traversal with null elements

Question

We all know that different binary trees can have the same inorder, preorder, or postorder traversal. But if we were to include null elements into a preorder traversal, then result of the traversal would be unique as long as the trees are unique. Consider these two trees:

  3                      3
 /                        \
4            vs.           4

Their normal preorder traversal would be {3,4} for both, but if we were to include null elements, then their traversal would be {3,4,null,null,null} and {3,null,4,null,null} respectively, making the traversal unique.

My question is, would this be true for inorder and postorder traversals as well? And how can we prove it?

score 28 · Accepted Answer · answered Aug 25 '17 at 00:09

28

It is true for a postorder traversal, because that's just the reverse of the preorder traversal of the reversed tree.

It is NOT true for an inorder traversal, which would always start with null, end with null, and alternate between nulls and nodes.

E.g., these trees:

  B          D    
 / \        / \
A   D      B   E
   / \    / \
  C   E  A   C

both produce

null, A, null, B, null, C, null, D, null, E, null

answered Aug 25 '17 at 00:09

Matt Timmermans

53,709
3
46
87

Can there be one formal convincing proof for the same? – Rohit Singh Sep 25 '22 at 05:57
Easily done by induction from the leaves, but no good reason to do it. Anyone who would be convinced by such a proof, but not by this demonstration, is just looking for long words and smart-sounding language. – Matt Timmermans Sep 25 '22 at 12:38
Yes, agree with you. But such proofs are often required for theoretical examinations. That's why was interested in them. – Rohit Singh Sep 25 '22 at 12:56

score 0 · Answer 2 · edited Oct 28 '22 at 03:13

The inorder is not right.
e.g.:

      2                     2
     / \                   / \
    2   n                 n   2
   / \                       / \
  n   n                     n   n

They are both [n, 2, n, 2, n]

Preorder and postorder are right because with 2 null, we can determine a parent, and this parent must be a child of other node, and so on. We can always determine a unique parent node. But this is not true for inorder.

Uniqueness of Inorder, Preorder, and Postorder traversal with null elements

2 Answers2

Linked