Open

Binary tree from in-order and level-order traversals?

Can we prove that one can unambiguously construct a binary tree from its in-order and level-order traversals?

I am thinking of a proof by induction on number of levels.

Base case: trees with 1 or 2 levels. These cases are clear.

Assume that this holds for trees with l levels. That is: one can unambiguously construct a binary tree with l levels from its in-order and level-order traversals.

Inductive case: prove that this holds for trees with l+1 levels. Not clear how to proceed in this case. Any help will be appreciated.