title: Binary tree from in-order and level-order traversals?
body: <p>Can we prove that one can unambiguously construct a binary tree from its in-order and level-order traversals?</p>
  
  <p>I am thinking of a proof by induction on number of levels.</p>
  
  <p>Base case: trees with 1 or 2 levels. These cases are clear.</p>
  
  <p>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.</p>
  
  <p>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.</p>