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 :
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
- 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
Each node may also hold a value, for instance :
Alright, so to implement binary trees in python, we need to :
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
valuevariable, for instance :
x = root.right.left.value y = root.left.value print(x) print(y)Output :
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...).