We can construct a binary tree if we are given at least two traversal results. The first traversal must be the **in-order traversal** and the second can be either **pre-order** or **post-order traversal.**

The in-order traversal result will be used to determine the left and the right child nodes, and the

pre-order/post-order can be used to determine the root node. For example, consider the traversal results given below:

**Inorder-INFORMATION**

**Postorder-INOFMAINOTR**

**Pre–order Traversal: A B D E C F G**

**In–order Traversal: D B E A F C G**

Here, we have the in-order traversal sequence and pre-order traversal sequence. Follow the steps given below to construct the tree:

**Step 1** Determine Root

In Pre-Order the first element, in Post-Order the last element is the root node.

PreOrder-Root node ←A B D E C F G

PostOrder-INOFMAINOTR→ Root node

**Step 2** Determine Subtree

Elements on the left side of the root node in the in-order traversal form the left sub-tree of the root node. Similarly, elements on the right side of the root node in the in-order traversal sequence form the right sub-tree of the root node.

(left subtree) **D B E** A **F C G** (right subtree)

(left subtree) **INFO **R **MATION**(right subtree)

**Step 3**

Preorder- Recursively select each element from pre-order traversal(make its parent node) , from left to right and create its left and right sub-trees from the in-order traversal.

Postorder- Recursively select each element from post-order traversal, from right to left and create its left and right sub-trees from in-order traversal.

**In–order Traversal: D B H E I A F J C G**

Post-order** Traversal: D H E B I J F G C **

***underlined letters are considered parent node**

Inorder- INFORMATION

Postorder- INOFMAINOTR

***underlined letters are considered parent node**

Thank you for reading

Tweet your queries and feedback to @PsychoCodes or leave a message on our Facebook page. You can also comment your questions below.

Also, don't forget to subscribe to our Newsletter.

If you like this article, then please share it and help us grow.

Preorder and Postorder Traversal of binary tree in Python

02 September 2018

Binary Tree in Python

02 September 2018

Image Sharpening by High Pass Filter using Python and OpenCV

17 August 2018

Explaining Register variables in C with examples

17 August 2018

C program to generate all combinations of N-Bit Binary String

10 July 2018

Data Autosave System using PHP, MySQL and AJAX

06 July 2018

3DAJAXAlgorithmsC programmingC ProgramsC TutorialsC-plusplusCMSComputer ScienceCSSData StructuresDjangoHackingHTMLInformation SecurityInterview QuestionsJavaJava ProgramsJava TutorialsJavascriptJavaScript TutorialsJSONOpenCVPHPProgrammingProgramming BooksPythonPython ProgramsSQLSteganographyTechnologyWeb DesigningWeb Development

## Share your thoughts