Question

the following lists the nodes in a binary tree in two different orders:

Preorder : A B C D E F G H I J K L M

Inorder : C E D F B A H J I K G M L

Draw the binary tree

Answer 1

Answer:

In order to draw a binary tree from Preorder and Inorder traversals. We have to know some basics.

• First element in Preorder will be the root of the tree.
• Now search that element in Inorder, say you find it at position i, once you find it. make note of elements which are left to i ( this will construct the left sub tree ) and elements which are right to i ( this will construct the right subtree )
• See the step above and recursively construct left subtree and recursively construct right subtree until you get a binary tree.

Given Preorder and Inorder traversals

• Preorder = A B C D E F G H I J K L M
• Inorder = C E D F B A H J I K G M L

First element in preorder is A. So A is root node. Search that element in Inorder.

From A -> Left we have ( C E D F B )

From A -> Right we have ( H J I K G M L)

                                               

Call recursively until you get the binary tree.

                                                         

The Fina binary tree will be

Thank you. Please ask me if you hav any doubt and upvote my answer if you like it.