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.
0 Replies