Types of Binary Tree: In-order, Pre-order, and Post-order Implementation Using Python

The tree data structure is one of the most important topics as far as the interview preparation for competitive exams are concerned, we are going to learn about binary trees, their uses, and their implementation using python. 

 

Below are the list of topic that we are going to cover-:

 

1. Binary Tree

2. Full/strict Binary Tree

3. Complete Binary Tree

4. Tree Traversal Methods

5. In-order

6. Pre-order

7. Post-order

 

(Must read: Python to represent output)

 

 

Binary Tree 

 

Binary trees are simple trees that can have at most two children, The topmost node in a binary tree is known as root or parent node, the nodes that are derived from a root is known as child nodes

---

Binary tree

---

In the figure represented above, the 1 node is the root or parent node for 2 and 3, whereas 2 is a root for 4 and 5. The last level nodes that are not connected with any nodes below their level are known as leaf nodes.

 

Some examples of binary trees-:

---

Simple binary tree

---

All the above diagrams come under the binary tree, the definition states that at most two child nodes can be present, therefore, with one child node, or even with zero child node(i.e, even if the only root is present), it is still a binary tree.

 

Types of Binary tree

 

1. Full Binary tree/ strict binary tree

 

A full binary tree is also known as a strict binary tree and is one of the special types of a binary tree which comes with a restriction that it can have either 0 or 2 children, therefore, if a binary tree has only one child, it is still a binary tree but not a full binary tree, examples-:

---

Full binary tree or strict binary tree

---

 

We can observe that all the figures in the above binary tree have either one child node or two child nodes, therefore, all these figures are of a strict binary tree. The next type of binary tree is an almost complete binary tree (ACBT).

 

2. Almost Complete Binary Tree

 

ACBT is a very important concept as far as max heap and min heap is concerned, an almost complete binary tree grows from left to right, which means the left side of a tree must be completed, the right side may or may not be completed or in other words, for every root, we must make a left child first, then we may or may not go for the right child.

---

Almost complete binary tree

---

To fill up the left side is most important and the first rule of an almost complete binary tree, the second rule for the almost complete binary tree is that, do not jump to the next level before filling up every left child of the previous level. For example-:

---

ACBT Examples

---

The next important type under the binary tree is called a complete binary tree.

 

(Also Read: Python Tutorial on Partition and QuickSort Algorithm)

 

3. Complete Binary Tree

 

Complete binary tree as the name suggests is the most complete form of a binary tree, in this type, there must be either 0 or 2 child nodes and except for the last level, all the levels must be full, the only difference between full binary tree and the complete binary tree is that in the case of a full binary tree, there is no such restriction as to fill the whole level except the last one. Some of the examples are-:

---

Complete Binary Tree Examples

---

(Related blog: Linear search and binary search)

 

 

Tree Traversal Techniques

While implementing a tree data structure, we will not illustrate the diagram of a tree but we are going to traverse through each and every node in a way that we can cover the whole tree. Tree traversal techniques are methods to observe all the nodes of a tree in a way that we can represent the whole tree with the help of its nodes.

 

(Learn about: Dynamic Programming VS DAC)

 

The methods that are used to traverse a tree are-:

 

1. In-order

2. Pre-order

3. Post-order

 

Let’s begin with the In-order tree traversal method.

 

1. In-order Tree Traversal

 

The order in which the tree traversal happens in the case of In-order is that firstly, we have to visit the left node, after visiting the left node, we shall visit the root, and lastly, we shall visit the right node to traverse through the tree. In-order tree traversal examples are-:

---

In-order Example

---

In the above example of In-order tree traversal, we can observe that the left child is traversed first, then the root, and then the right child. The end product is an order of nodes which is 2, 1, 3.

 

Let’s understand with a more complex example-:

---

In-order Tree Traversal Example

---

The example we took this time had three levels and was a complete binary tree, we found that there are two sub-trees within the tree, one was left sub-tree and the other was right sub-tree, we solved both of them using our previous method, the In-order result of each sub-tree was written as one unit, therefore, at the end, we were again left with the representation that we already know.

 

(Also read: What is Stochastic Gradient Descent?)

 

In-order Tree Traversal Python Implementation

 

---

class node:

        def __init__(self,val):

            self.leftchild = None

            self.rightchild = None

            self.nodedata = val

    

root = node(1)

root.leftchild = node(2)

root.rightchild = node(3)

root.leftchild.leftchild = node(4)

root.leftchild.rightchild = node(5)

---

The above python code is nothing but a representation of a binary tree, which is also a strict binary tree, we are going to use this tree as an example for In-order, Pre-order, and Post-order tree traversal. Above is a code to make a tree that looks like-:

---

---

The in order of the above tree will be -: 4,2,5,1,3

---

---

The above representation shows a scribbled way of starting and traversing all the nodes in In-order tree traversal method.

---

 def inord(root):

    if root:

        inord(root.leftchild)

        print(root.nodedata)

        inord(root.rightchild)

inord(root)

 

The above code shows the working of an In-order tree traversal method, the function inord() takes the root as a parameter, we are applying recursion on the left sub-part of the tree, and then we are printing the root(because the root is one unique entity, we don’t need recursion), lastly, we are using recursion on the right sub-part of the tree.

 

2. Pre-Order Tree Traversal

 

Pre-order tree traversal is another method of traversing and representing a tree, it prints the root first, then move to the left child of the root and at last, it goes to the right child, let’s understand it with the help of an example-:

---

Pre-order Tree Traversal Example

---

 

(Related reading: Feature Scaling In Machine Learning Using Python)

 

Pre-order Tree Traversal Using Python

 

def preord(root):

    if root:

        print(root.nodedata)

        preord(root.leftchild)

        preord(root.rightchild)

preord(root)

 

The code is the same as the in-order with the only difference is the order in which the conditions are executed, firstly, the root is printed, then recursion is applied on the left child, and lastly, the recursion is applied on the right child.

 

3. Post-order Tree Traversal

 

Post-order tree traversal method is another tree traversal technique that starts with recursion on the right child, then with the left child, and at last it prints the root. Let us take an example to understand it clearly-:

---

Post-order tree traversal example

---

The above example of Post-order tree traversal is showcasing that we should always solve the sub-trees first, once the sub-tree is solved, consider the solution of that sub-tree as a child node and solve the rest of the tree. 

 

(Suggested article: DATA TYPES in Python)

 

Post-order Tree Traversal Using Python

 

def postord(root):

    if root:

        postord(root.rightchild)

        postord(root.leftchild)

        print(root.nodedata)

postord(root)

 

The above code portrays that firstly the right sub-tree will be solved recursively, then the left sub-tree will be solved recursively, and at the end we are printing the root. The implementation is the same as of pre-order and in-order but the difference is in the order of execution of nodes.

 

 

Conclusion

 

To conclude this blog, we have successfully learned about the implementation of in-order, post-order, and pre-order tree traversal method using python and illustration for better understandability, we have also discussed the binary tree and all of its major types such as strict/full binary tree, almost complete binary tree, and a complete binary tree with the help of an illustration.