Make delicious recipes!

Construct tree from InOrder and PreOrder traversals


PreOrder is DLR and InOrder is LDR

That means, first element of PreOrder is the root of the tree.

However, in InOrder, root is found after all its left subtree has been traversed.

This implies that left part from start to root in InOrder is the left subtree.

From PreOrder, take same number of characters after root.

These two smaller subsequences from pre-order and in-order can be used to form a left subtree and similarly the right subtree.


Example:

Inorder sequence: D B E A F C

Preorder sequence: A B D E C F


So, root is A

InOrder left subtree has 3 characters - DBE

Take similar number of characters from InOrder - BDE

Form subtree for these two and make it left child.

Remaining part is FC from InOrder and CF from PreOrder.

Follow the recursion to form right subtree.








Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal