What are binary trees and implementation in python
2 min read

What are binary trees and implementation in python

Binary trees will be used in decision trees classifiers and regressors. However, instead of writing a whole article on how to code a decision tree from scratch, I chose to split up each small step in independent articles.

In the meantime, here is a very short article on binary trees.

If you're on this page you probably want to learn about binary trees. If you already know about them and are just interested in the code, scroll down !

Basic explanation, what is a binary tree ?

A binary tree is structure made up of nodes, each node can have up to two children and every node has one parent except for the root node. Here are some examples of binary trees :

2 binary trees

The red nodes are the root nodes and the green nodes are the leaves. We can define :

  • Root nodes : nodes that do not have a parent
  • Leaves : nodes that do not have children

      Each node may also hold a value, for instance :

      Alright, so to implement binary trees in python, we need to :

      • Create nodes that are connected in a certain way
      • Assigning values to the nodes
      • Bonus : We might want to retrieve a value from a certain node

      So, how should we do that ?

      Implementing a binary tree in python

      There are two main ways to represent a binary tree : With a list (array) (which I won't go into in this article because I'll go over the other one) and creating each node, which has its own value stored and each of its children's adress stored as well. Here, I'll talk about the second way. This can be achieved very simply :

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

      And just like that, we can create a binary tree. For example, to create the tree just above this is what we'd have to do :

      root = Node(7)
      root.left = Node(10)
      root.right = Node(4)
      root.left.right = Node(18)
      root.right.left = Node(20)
      root.right.right = Node(1)

      Not that hard ! To get a value from a node we just have to use the value variable, for instance :

      x = root.right.left.value
      y = root.left.value
      print(x)
      print(y)
      
      Output : 20
                 10

      In the next article, I'll show some operations on the trees (Switch between list and class format, get all leaves, get a node from a path, etc...).