Tree Data Structure in Python

Python is a very rich language in terms of features and data structures. It has a lot of inbuilt data structures like python dictionary, list, tuple, set, frozenset, etc. Apart from that, we can also create our own custom data structures using Classes. In this article, we will learn about Binary tree data structure in Python and will try to implement it using an example.

What is a Tree Data Structure in Python?

A Tree is a Data structure in which data items are connected using references in a hierarchical manner. Each Tree consists of a root node from which we can access each element of the tree. Starting from the root node, each node contains zero or more nodes connected to it as children. A simple binary tree can be depicted as seen in the following figure.

Parts of a Tree Data structure

A tree consists of a root node, leaf nodes and internal nodes. Each node is connected to its chile via a reference, which is called an edge. 

Root Node: Root node is the topmost node of a tree. It is always the first node created while creating the tree and we can access each element of the tree starting from the root node. In the above example, the node containing element 50 is the root node.

Parent Node: The parent of any node is the node which references the current node. In the above example, 50 is the parent of 20 and 45, 20 is parent of 11, 46 and 15. Similarly 45 is the parent of 30 and 78.

Child Node: Child nodes of a parent node are the nodes at which the parent node is pointing using the references. In the example above, 20 and 45 are children of 50. The nodes 11, 46, and 15 are children of 20 and 30 and 78 are children of 45.

Edge: The reference through which a parent node is connected to a child node is called an edge. In the above example, each arrow that connects any two nodes is an edge.

Leaf Node: These are those nodes in the tree which have no children. In the above example, 11, 46, 15, 30, and 78 are leaf nodes.

Internal Nodes: Internal Nodes are the nodes which have at least one child. In the above example, 50, 20 and 45 are internal nodes.

What is a Binary Tree?

A binary tree is a tree data structure in which each node can have a maximum of 2 children.  It means that each node in a binary tree can have either one, or two or no children. Each node in a binary tree contains data and references to its children. Both the children are named as left child and the right child according to their position. The structure of a node in a binary tree is shown in the following figure.

We can define a node of the structure shown above in python using classes as follows.

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

Here the constructor of the node 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 to the children to None. The children can be assigned to the nodes later. An example of a binary tree is shown in the figure below.

We can implement the above binary tree in python as follows.

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


node1 = BinaryTreeNode(50)
node2 = BinaryTreeNode(20)
node3 = BinaryTreeNode(45)
node4 = BinaryTreeNode(11)
node5 = BinaryTreeNode(15)
node6 = BinaryTreeNode(30)
node7 = BinaryTreeNode(78)

node1.leftChild = node2
node1.rightChild = node3
node2.leftChild = node4
node2.rightChild = node5
node3.leftChild = node6
node3.rightChild = node7

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Output:

Root Node is:
50
left child of the node is:
20
right child of the node is:
45
Node is:
20
left child of the node is:
11
right child of the node is:
15
Node is:
45
left child of the node is:
30
right child of the node is:
78
Node is:
11
left child of the node is:
None
right child of the node is:
None
Node is:
15
left child of the node is:
None
right child of the node is:
None
Node is:
30
left child of the node is:
None
right child of the node is:
None
Node is:
78
left child of the node is:
None
right child of the node is:
None

Conclusion

In this article, we have discussed tree data structure and binary tree data structure in Python. To learn more about data structures in Python, you can read this article on Linked list in python.