Constructing Binary Tree from Preorder and Inorder Traversal

0
votes

I'm trying to make the postorder of binary tree from its preorder and inorder traversal. but i don't have any idea how am i suppose to do that and what should be the structure of my code. any help can be useful.

for example :

input:

preorder : 6 2 1 4 3 5 7 9 8

inorder : 1 2 3 4 5 6 7 8 9

output:

post-order:1 3 5 4 2 8 9 7 6

1
pythondata-structuresbinary-treetree-traversal
Hi @abolfazl, welcome to stackoverflow. It sounds like you should first understand the algorithm: How would you do that with pen and paper? Study your textbook, or whatever, until you can do that. Then you can start transforming your steps to Python, and you can come back here if you are stumped with specific steps. - alexis

1 Answers

0
votes
  • Select first element from preorder list and increment the preorder index.
  • Create a Binary tree node (new_node) and set the value as selected preorder list value.
  • Find the selected element index(inorder_index) in Inorder list.
  • Call recursive function again with left side of inorder_index items in inorder list and set as the left child of new_node.
  • Call recursive function again with right side of inorder_index items in inorder list and set as the right child of new_node.
  • return new_node

Source:http://simpletechtalks.com/construct-a-binary-tree-from-inorder-and-preorder-traversal/#:~:text=Let%E2%80%99s%20look%20into%20the%20algorithm%20to%20construct%20the,the%20selected%20element%20index%20%28inorder_index%29%20in%20Inorder%20list.