What is a Binary Tree and how do you create one in Python?

What’s a Binary Tree?

A binary tree is a data structure that allows two nodes to be linked together by a path from the root to the leftmost child, and from the leftmost child to the rightmost child. The path is called a path from the root to the leftmost child, and from the leftmost child to the rightmost child.

This sounds confusing. Show me some code

Here you go.

Okay. I bet you’re even more confused now. Let’s make it simple. Shall we?

Take this list of integers:

>> 1, 2, 3, 4, 5, 6, 7

We want to represent this list as a Binary Tree. This is what it would look like:

This is it. This is a basic Binary Tree. We have a root node with two children. The left child’s value is smaller than the value of the node while the right child’s value is bigger. The same principle is repeated for each of the child nodes. Let’s use the BinaryTree class that we saw earlier on this list. We’ll initialize the object with the root node first.

>> tree = BinaryTree(4)

Note that we started with the middle value. That is because we want to keep this tree balanced. There are other forms of trees that balance themselves but these are out of the scope of this post. We will cover them in the future. Let’s add two new nodes to this tree.

>> tree.add_node(BinaryTree(2))

>> tree.add_node(BinaryTree(6))

Note that we’re adding the nodes the way we see them in the figure above. If we did not follow this, our tree would be an unbalanced mess. Also, note that we provide a BinaryTree object to the add_node method of our tree. This might be confusing but a simple way to think about this is that any sub node within this tree can be considered a Binary Tree in itself.

We’re gonna add some more nodes

>> tree.add_node(BinaryTree(1))

>> tree.add_node(BinaryTree(3))

>> tree.add_node(BinaryTree(5))

>> tree.add_node(BinaryTree(7))

Our Binary Tree is now complete.

Okay. This is pretty cool. What else can we do with this?

A Binary Tree can be traversed in the following ways:

Inorder
Preorder
Postorder

Inorder Traversal

The simplest way to think about this with our example is that traversing our tree in order would give us an ordered list:

>> 1, 2, 3, 4, 5, 6, 7

This is the algorithm:

Recursively traverse the left node.
Visit root.
Recursively traverse the right node.

The corresponding method for this in our BinaryTree class is traverse_in_order

Preorder Traversal

This is when the root is traversed before the children. This traversal method can be useful for creating a copy of the original tree. The output of this method would be the following:

>> 4, 2, 1, 3, 6, 5, 7

This is the algorithm:

Visit root.
Recursively traverse the left node.
Recursively traverse the right node.

The corresponding method for this in our BinaryTree class is traverse_pre_order

Postorder Traversal

You guessed it. This is when the children are traversed before the root. Postorder traversal can be used to delete the tree. The output of this method would be the following:

>> 1, 3, 2, 5, 7, 6, 4