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?
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