Learn tree in Python- data structure, programs with code examples. Know more about Python tree, how to create it and traverse using pre and post order.

What is a tree in Python?

Trees are non-linear data structures representing nodes connected by edges. Each tree consists of a root or main node known as the Parent node and the left node and right node as Child nodes. It is used for searching and data organization.

Does Python have Tree?

No, Python does not have any trees built-in. On the other hand, you can easily construct by subclassing a Node type from list and writing the traversal methods. We will discuss this later in the article.

Introduction to Python Tree

A binary tree node contains the following components- Data, Left Child, Right Child. The important terms related to a binary tree are:

  1. Node – The simplest unit of a binary tree.
  2. Root – It is the topmost element. There is mostly one root in a binary tree.
  3. Parent – It is the node that is one level upward of the node.
  4. Child – They are the nodes that are one level downward of the node.
  5. Leaf – Leaves of a binary tree are the nodes that have no children.
  6. Level – It is the generation of the node.

For example, a root has level 0, the children of the root node is at level 1 and the grandchildren of the root node is at level 2.

How Tree is implemented in Python? Tree program in Python

To implement and create a tree in Python, we first create a Node class that will represent a single node. The node class will have 3 variables- the left child, the second variable data containing the value for that node and the right child.

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

Now, initializing a tree:

root = Node(10)

root.left = Node(34)
root.right = Node(89)
root.right.left = Node(45)
root.right.right = Node(50)

As a result, the output tree looks like this:

          10
        /    \
       34      89
             /    \ 
            45    50

If you create an object of class Node, the __init__ constructor is called, and all the variables inside that constructor will get initialized. The root holds the root node of the tree has a value of 10. We insert the left child with the value 34 and the right child with the value 89. As it is a binary tree, every node can contain a maximum of two nodes. Further, we insert two more nodes to the tree as in 45 and 50. They are the children for node 89.

Note: We can insert any number of nodes we want inside a tree, depending upon the type of tree being created.

How to print tree elements | Traverse a Tree in Python

Since we have created a tree, so we need to traverse the tree to print the tree elements. Traversing means visiting every node in a tree. Every node in a tree is visited three times. There are three types of traversals in a binary tree: in-order traversal, pre-order traversal, and post-order traversal.

In-order Traversal

In this case, we first visit the left child and perform recursion, then we visit the same node for the second time to print that node. It is further followed by the parent node, then followed by recursion on the right child.
The given tree is:


      10
      / \
   34    89
   / \   / \
  20 45 56 54
def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)

As a result, the output is:
20 34 45 10 56 89 54

Pre-order Traversal

In this case, while traversing a python tree, we see the root node for the first time and print it. It is then followed by recursion on the left and the right child.
The given tree is:


      10
      / \
   34    89
   / \   / \
  20 45 56 54
def preorder(node):
    if node:
        print(node.data)
        preorder(node.left)
        preorder(node.right)

As a result, the output is:
10 34 20 45 89 56 54

Post-order Traversal

In this case, while traversing a tree, we do recursion on the left node and the right node. Then we come to the root node to print it.
The given tree is:


      10
      / \
   34    89
   / \   / \
  20 45 56 54
def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data)

As a result, the output is:
20 45 34 56 54 89 10

Using the Insert Method

To use the insert method in the same node class, we add an insert class to it. This insert class compares the value of the node to the parent node and decides to add it as a left node or a right node. Further, the PrintTree class prints the tree.
Example:

class Node:

    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 = Node(data) 
                else: 
                    self.left.insert(data) 
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()
root = Node(30)
root.insert(15)
root.insert(40)
root.insert(35)
root.insert(12)
root.insert(20)
root.PrintTree()

As a result, the output is:
12 15 20 30 35 40

Conclusion & Practical Application

Using trees in Python can be fun, as we saw in the above examples. These are widely used in different software and applications. A strong grip on this topic can be very beneficial for interview purposes and give you an extra edge. After understanding the principles of a tree, practice some problem sets to test your knowledge of trees in python.

You can also learn about

Like this article? Follow us on Facebook and LinkedIn.