Python Data Structure: Binary Trees

A tree represents nodes connected by edges. It is a nonlinear data structure. It has the following properties –

• One node is labeled the root node.

• Each node, except the root node, is associated with a parent node.

• Each node can have any number of children.

We create a tree data structure in Python by using the concept of OS nodes discussed earlier. We designate a node as the root node and then add more nodes as children. Below is the program to create the root node.

Creating the Root Node

We simply create a Node class and assign a value to the node. This creates a tree with a single root node.

Example

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

root = Node(10)
root.PrintTree()

Output

When the above code is executed, it produces the following output –

10

Inserting into the Tree

To insert into the tree, we use the same Node class created above and add an Insert class to it. The Insert class compares the value of the node with the parent node and decides whether to add it as the left or right node. Finally, we use the PrintTree class to print the tree.

Example

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

   def insert(self, data):
#Compare the new value with the parent node
      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

# Print the tree
   def PrintTree(self):
      if self.left:
         self.left.PrintTree()
      print(self.data),
      if self.right:
         self.right.PrintTree()

# Use the insert method to add nodes
root= Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.PrintTree()

Output

When the above code is executed, it produces the following output –

3 6 12 14

Traversing a Tree

A tree can be traversed by deciding the order in which to visit each node. We can clearly see that we can start from a node and visit the left subtree first and then the right subtree. Or we can visit the right subtree first and then the left subtree. Hence, these tree traversal methods have different names.

Tree Traversal Algorithms

Traversal is the process of visiting all the nodes of a tree and also printing their values. Because all nodes are connected by edges (links), we always start from the root (head) node. This means we can’t randomly access a node in the tree. There are three ways to traverse a tree.

• In-order traversal

• Pre-order traversal

• Post-order traversal

In-order traversal

In this traversal method, the left subtree is visited first, followed by the root, and finally the right subtree. We should always remember that each node may represent a subtree itself.

In the following Python program, we use the Node class to create a root node and placeholders for the left and right nodes. We then create an insert function to add data to the tree. Finally, we implement the in-order traversal logic by creating an empty list and first adding the left node, followed by the root or parent node.

Finally, add the node on the left to complete the in-order traversal. Note that this process is repeated for each subtree until all nodes have been traversed.

Example

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
#InsertNode
   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)
         else data > self.data:
            if self.right is None:
               self.right = Node(data)
            else:
               self.right.insert(data)
      else:
         self.data = data
# Print the Tree
   def PrintTree(self):
      if self.left:
         self.left.PrintTree()
      print(self.data),
      if self.right:
         self.right.PrintTree()
# Inorder traversal
# Left -> Root -> Right
   def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))

Output

When the above code is executed, it produces the following output –

[10, 14, 19, 27, 31, 35, 42]

Pre-order Traversal Method

In this traversal method, the root node is visited first, followed by the left subtree, and finally the right subtree.

In the following Python program, we use the Node class to create the root node and placeholders for the left and right nodes. We then create an insert function to add data to the tree. Finally, we implement the pre-order traversal logic by creating an empty list and adding the root node first, followed by the left node.

Finally, the right node is added to complete the pre-order traversal. Note that this process is repeated for each subtree until all nodes have been traversed.

Example

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
#InsertNode
   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
# Print the Tree
   def PrintTree(self):
      if self.left:
         self.left.PrintTree()
      print(self.data),
      if self.right:
         self.right.PrintTree()
# Preorder traversal
# Root -> Left -> Right
   def PreorderTraversal(self, root):
res = []
if root:
res.append(root.data)
res = res + self.PreorderTraversal(root.left)
res = res + self.PreorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))

Output

When the above code is executed, it produces the following output –

[27, 14, 10, 19, 35, 31, 42]

Post-order traversal

In this traversal method, the root node is visited last, hence the name. First, we traverse the left subtree, then the right subtree, and finally the root node.

In the following Python program, we use the Node class to create the root node and the storage locations for the left and right nodes. Then, we create an insert function to add data to the tree. Finally, we implement the post-order traversal logic by creating an empty list and adding the left node first, then the right node.

Finally, the root node, or parent node, is added, completing the post-order traversal. Note that this process is repeated for each subtree until all nodes have been traversed.

Example

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
#InsertNode
   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)
         else if data > self.data:
            if self.right is None:
               self.right = Node(data)
            else:

               self.right.insert(data)
      else:
         self.data = data
# Print the Tree
   def PrintTree(self):
      if self.left:
         self.left.PrintTree()
print(self.data),
if self.right:
self.right.PrintTree()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))

Output

When the above code is executed, it produces the following output –

[10, 19, 14, 31, 42, 35, 27]