Binary Tree implementation in Python

In this tutorial, we will learn about what binary trees are and we will study underlying concepts behind binary tree data structure. We will also implement them using classes in python.

What is a Binary Tree?

A Binary tree is a data structure in which there is a parent object and each object can have zero, one or two children. Generally we call the object a Node and each node consists of a data field, a reference to a left child and a reference to a right child.

As we can see the structure above, a node will have it’s own data, and it will also have references to two nodes, one on the left and other on the right side. To implement the above structure, we can define a class and assign values to data and reference to left child and right child.

class BinaryTreeNode:
  def __init__(self, data):
    self.data = data
    self.leftChild = None
    self.rightChild=None

Here the constructor takes the data value as input, creates an object of BinaryTreeNode type and initializes the data field equal to given input and initializes the references of left child and right child to None.

Basic Terminologies in Binary Trees

Now we will take an example of a binary tree and look at the terminologies related to it. Suppose we have been given the below binary tree.

• Root Node: The topmost node of the binary tree is called its root node. It is the first node created during the creation of the tree. In the above example, 10 is the root node.
• Parent Node: The parent of a node is the node whose leftChild reference or rightChild reference is pointing to the current node. For example, 10 is the parent node of 15.
• Child Node: Node at which a parent node is pointing is called its child node. Here 15 is a child node of 10.
• Edge: An edge is a link connecting any two nodes in the tree.
• Internal Nodes: Internal Nodes are the nodes that have at least one child. In our example, nodes containing data 10,15, and 20 are internal nodes.
• Leaf Node or External Nodes: These are nodes in the binary tree which have no children. Their both leftChild and rightChild refer to None. In the above example, nodes with data 60, 14, 25, and 6 are leaf nodes or external nodes.

Implementing a Binary Tree in Python

Now we will try to implement the binary tree given in the above example in the following code:

class BinaryTreeNode:
  def __init__(self, data):
    self.data = data
    self.leftChild = None
    self.rightChild = None
    
a1=BinaryTreeNode(10)
a2=BinaryTreeNode(15)
a3=BinaryTreeNode(20)
a4=BinaryTreeNode(60)
a5=BinaryTreeNode(14)
a6=BinaryTreeNode(25)
a7=BinaryTreeNode(6)

a1.leftChild=a2
a1.rightChild=a3
a2.leftChild=a4
a2.rightChild=a5
a3.leftChild=a6
a3.rightChild=a7

print("Root Node is:")
print(a1.data)

print("left child of node is:")
print(a1.leftChild.data)

print("right child of node is:")
print(a1.rightChild.data)

print("Node is:")
print(a2.data)

print("left child of node is:")
print(a2.leftChild.data)

print("right child of node is:")
print(a2.rightChild.data)

print("Node is:")
print(a3.data)

print("left child of node is:")
print(a3.leftChild.data)

print("right child of node is:")
print(a3.rightChild.data)

print("Node is:")
print(a4.data)

print("left child of node is:")
print(a4.leftChild)

print("right child of node is:")
print(a4.rightChild)

print("Node is:")
print(a5.data)

print("left child of node is:")
print(a5.leftChild)

print("right child of node is:")
print(a5.rightChild)

print("Node is:")
print(a6.data)

print("left child of node is:")
print(a6.leftChild)

print("right child of node is:")
print(a6.rightChild)

print("Node is:")
print(a7.data)

print("left child of node is:")
print(a7.leftChild)

print("right child of node is:")
print(a7.rightChild)

Output:

Root Node is:
10
left child of node is:
15
right child of node is:
20
Node is:
15
left child of node is:
60
right child of node is:
14
Node is:
20
left child of node is:
25
right child of node is:
6
Node is:
60
left child of node is:
None
right child of node is:
None
Node is:
14
left child of node is:
None
right child of node is:
None
Node is:
25
left child of node is:
None
right child of node is:
None
Node is:
6
left child of node is:
None
right child of node is:
None

As you can see, In the above code, we have first created objects of the BinaryTreeNode class defined in the example. Then we have assigned the root of the tree and then we have added children to the root node and so on. Then we have printed the data in each node and data in their children node.

Conclusion:

In this article, we looked at the theoretical concepts behind a binary tree and then we implemented the binary tree on the basis of the concepts. Stay tuned for more informative tutorials.

Happy Learning!