Is it possible to uniquely reconstruct a binary tree with just in-order traversal and null makers?
For example, for the tree:
A
/ \
B C
The inorder traversal with null markers is: null, B, null, A, null, C, null
A C
/ \ / \
B C A D
\ /
D B
It seems these trees both gives: null, B, null, A, null C, null D, null.
But it's possible to save a binary tree of depth N in array of size 2N-1.
A C
/ \ / \
B C A D
/ \ / \ / \ / \
N N N D B N N N
null, B, null, A, C, null, D
B, A, null, C, D, null, null