Techiio-author
Started by Ronald RauheSep 14, 2021

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

0 VIEWES 0 LIKES 0 DISLIKES SHARE
0 LIKES 0 DISLIKES 0 VIEWES SHARE

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

You must be Logged in to reply
Techiio-logo

Techiio is on the journey to build an ocean of technical knowledge, scouring the emerging stars in process and proffering them to the corporate world.

Follow us on:

Subscribe to get latest updates

You can unsubscribe anytime from getting updates from us
Developed and maintained by Wikiance
Developed and maintained by Wikiance