How to make a binary tree Python

Create a binary tree in Python with a step-by-step example: learn how to use classes, set up nodes, and traverse a tree.

Building a Binary Tree in Python

A binary tree is a hierarchical data structure which consists of nodes connected to each other in a parent-child relationship. Each node consists of a left and right child, and a data element. The first node is called the root node, and each node after that is called a child node. Nodes can also have multiple children, called siblings.

In this tutorial, we will be building a binary tree in Python. We will be using the Tree class from the tree module. This class provides a convenient way to store and manipulate nodes in a tree structure.

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

The Tree class has three instance variables: data, left, and right. The data variable stores the data element of the node, and the left and right variables store references to the left and right child nodes. If the node does not have a left or right child, the left and right variables will be set to None.

To create a new node, we can instantiate the Tree class and pass in a data element. The following code creates a new node with the data element "root":

root = Tree("root")

To add a left or right child to a node, we can use the set_left and set_right functions. These functions take a Tree object as an argument and set the left and right instance variables to the argument.

def set_left(self, node):
    self.left = node

def set_right(self, node):
    self.right = node

For example, the following code creates two new nodes and adds them as the left and right children of the root node:

node1 = Tree("node1")
node2 = Tree("node2")

root.set_left(node1)
root.set_right(node2)

The resulting tree looks like this:

  root
 /   
node1  node2

Now that we have a basic understanding of how to create and manipulate nodes in a tree, we can write a function that prints out the data elements of the tree in a pre-order traversal. A pre-order traversal visits each node in the tree before its children. The following function prints out the data elements in a pre-order traversal:

def pre_order_traversal(node):
    if node is None:
        return

    print(node.data)
    pre_order_traversal(node.left)
    pre_order_traversal(node.right)

To use this function, we can pass in the root node of the tree as an argument:

pre_order_traversal(root)

This will print out the following:

root
node1
node2

We can also write a post-order traversal function that visits each node after its children. This function is similar to the pre-order traversal function, but the print statement is moved to the end of the function:

def post_order_traversal(node):
    if node is None:
        return

    post_order_traversal(node.left)
    post_order_traversal(node.right)
    print(node.data)

Now, when we call the post_order_traversal function, we get the following output:

node1
node2
root

We have now seen how to create and manipulate nodes in a binary tree, and how to traverse the tree in pre-order and post-order traversals. This will allow us to build more complex data structures and algorithms that use binary trees.