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-:
Binary Tree
Full/strict Binary Tree
Complete Binary Tree
Tree Traversal Methods
In-order
Pre-order
Post-order
(Must read: Python to represent output)
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.
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).
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)
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)
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-:
In-order
Pre-order
Post-order
Let’s begin with the In-order tree traversal method.
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?)
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.
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)
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.
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)
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.
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.
5 Factors Influencing Consumer Behavior
READ MOREElasticity of Demand and its Types
READ MOREAn Overview of Descriptive Analysis
READ MOREWhat is PESTLE Analysis? Everything you need to know about it
READ MOREWhat is Managerial Economics? Definition, Types, Nature, Principles, and Scope
READ MORE5 Factors Affecting the Price Elasticity of Demand (PED)
READ MORE6 Major Branches of Artificial Intelligence (AI)
READ MOREScope of Managerial Economics
READ MOREDijkstra’s Algorithm: The Shortest Path Algorithm
READ MOREDifferent Types of Research Methods
READ MORE
Latest Comments