How to implement Binary Tree in Python
This Python tutorial helps you to understand what is Binary tree and how to implements Binary Tree in Python. First, we will learn what is Binary Tree.
Definition:- A tree in which every node can have a maximum of two children is called Binary Tree. Since each element has at most two children, we name them as the left child and right child.
A Binary Tree mainly consists of three parts. Those are:-
- Root or Data
- Left Child
- Right Child
Binary Tree is a non-linear data structure and has the following properties. Those are:-
- One node is always marked as the root node.
- Node other than the root node is associated with one parent node
- Every parent node can have a maximum of two children.
Advantages of Binary Tree
- Searching in Binary Tree becomes faster.
- Minimum and Maximum elements can be searched and picked up very easily.
- This data structure is used for graph traversals and to convert an expression to postfix and prefix forms.
Algorithm for Binary Tree Insertion
When a node is inserted in Binary Tree, the new node always checks with its parent node. If the new node is less than the value of parent node, the new node will be placed on the left side of the parent otherwise the new node will be placed on the right side of the tree.
Implementation of Binary Tree Insertion in Python
Source Code: Binary Tree in Python
class Tree: def __init__(self, data): self.left = None self.right = None self.data = data def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Tree(data) else: self.left.insert(data) elif data > self.data: if self.right is None: self.right = Tree(data) else: self.right.insert(data) else: self.data = data def getTree(self): if self.left: self.left.getTree() print( self.data), if self.right: self.right.getTree() root = Tree(20) root.insert(11) root.insert(25) root.insert(10) root.insert(30) root.insert(19) root.getTree()
- Create a class called Tree and initialize a constructor for passing the root value.
- Then create a function in the class called insert for taking new nodes as input.
- Now, the new input node checks with root value. The new input node 11 is less than 20, so it moves towards the left side of 20.
- Another new input node 25 is greater than 20, so it moves towards the right side of 20.
10 11 19 20 25 30
You can also read,
- How to implement Breadth First Search algorithm in Python
- How to implement Depth First Search algorithm in Python