Search code examples
binary-treeinorder

Is it possible to uniquely reconstruct a binary tree with just inorder traversal with null makers?


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


Solution

  •   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