Binary Tree Traversal Algorithms

Binary Trees are complex non-linear data structures that have wide-reaching uses. A common use case is a Binary Search Tree where data is arranged in a specific order and allows for very quick searching and sorting. This is mainly what we will be looking at today. Other uses could be in the implementation of a Heap data structure, or some compression algorithms.

Trees also relate to my previous post on renaming files in a directory. This is because directories lend themselves naturally to the structure of a tree. We used library functions to traverse a tree of files and rename them, but today we’ll be looking at how this traversal can be achieved manually.

Today we are going to be covering:

How to create a simple class to implement a Binary Search Tree in Python
Various different depth-first/breadth-first traversal methods and visualisations including:
Calculating the height (maximum length from root to leaf) of a tree
Various other calculations/algorithms with the tree

There is a lot of recursion today which is one reason I wanted to cover this topic. Recursion can be quite difficult to follow but is an incredibly important tool for coding algorithms. I recommend reading up on it a little if you are new to it but I’ll try to explain things as I go!

Various methods of traversing binary trees
Photo by Pearly85

Terminology

I think it would be useful to first cover the keywords and terminology used for discussing trees. The main concepts are:

Tree: A graph that has no loops, ie. any two points are connected by exactly one path.
Rooted Tree: A tree where one node has been singled out as the ‘root’, ie. the starting point.
Leaf: A node that has no children.
Internal Node: A node that has at least one child.
Height: The longest path from the root to a leaf.

Creating a Simple Binary Tree in Python

Python does not include an implementation of a tree by default. We could find a library to make one for us but that’s no fun!

To start with let’s just define the simplest starting point for a tree class.

1class Tree:
2    def __init__(self, value):
3        self.value = value
4        self.leftChild = None
5        self.rightChild = None

It turns out this is enough code to build a full tree! We can now use this to manually build up each node by hand. For example, here is some code that produces a tree, and then under it I have made a graphical representation of that tree.

1class Tree:
2    def __init__(self, value):
3        self.value = value
4        self.leftChild = None
5        self.rightChild = None
6 
7if __name__ == '__main__':
8    rootNode = Tree(50)
9    rootNode.leftChild = Tree(30)
10    rootNode.rightChild = Tree(70)
11    rootNode.leftChild.leftChild = Tree(20)
12    rootNode.leftChild.rightChild = Tree(40)

Well that was easy! However this is not a particularly useful way of building up trees because it requires us to manually enter which node is a child of which parent and thus it will get very messy very quickly. Instead, we can add a method to our ‘Tree’ class that takes a node’s value as input and positions it in the appropriate place in the tree. Since we are trying to make a binary search tree we have a couple of rules to satisfy when positioning a new node:

Starting at the root, check if the new value is greater than or less than the root’s value.
If greater then move to the right child, if lesser then move the the left child.
Repeat this check on the child we moved to, moving left or right from there depending on size of the new node’s value compared to the child’s value.
Continue this process until we find an empty child on the correct side of a node.

For example if I wanted to insert 32 into our tree above, we’d start at 50, move left to 30 (since 32 < 50), move right to 40 (since 32 > 30), and then position 32 as the left child of 40 (since 32 < 40 and this child is currently empty).

So here is an algorithm to implement this process automatically. Take note of the recursive calls.

1class Tree:
2    def __init__(self, value):
3        self.value = value
4        self.leftChild = None
5        self.rightChild = None
6 
7    def insertChild(self, node, value):
8        if node is None:
9            return Tree(value)
10        if value < node.value:
11            node.leftChild = self.insertChild(node.leftChild, value)
12        elif value > node.value:
13            node.rightChild = self.insertChild(node.rightChild, value)
14        return node

So (assuming we pass in the root node) we start at the top of the tree and do this greater/lesser check and traverse down the tree on the right/left side of the current node, respectively. We then re-call the function on the next node that we come to and it does exactly the same check. Eventually a node will have a child that has value ‘None’ and this will end our recursive calls and position our new node in that position.

So let’s build up a tree automatically!

1class Tree:
2    def __init__(self, value):
3        self.value = value
4        self.leftChild = None
5        self.rightChild = None
6 
7    def insertChild(self, node, value):
8        if node is None:
9            return Tree(value)
10        if value < node.value:
11            node.leftChild = self.insertChild(node.leftChild, value)
12        elif value > node.value:
13            node.rightChild = self.insertChild(node.rightChild, value)
14        return node
15 
16if __name__ == '__main__':
17    rootNode = Tree(50)
18    rootNode.insertChild(rootNode, 30)
19    rootNode.insertChild(rootNode, 20)
20    rootNode.insertChild(rootNode, 40)
21    rootNode.insertChild(rootNode, 32)
22    rootNode.insertChild(rootNode, 70)
23    rootNode.insertChild(rootNode, 60)
24    rootNode.insertChild(rootNode, 80)
25    rootNode.insertChild(rootNode, 75)
26    rootNode.insertChild(rootNode, 85)

This will produce a tree that looks like this:

Binary tree with numbers automatically placed in the correct position

I’ve had to make this graphic by hand. Unfortunately there’s no nice way to view trees we create in Python (without using extra libraries), or even an easy way of printing the elements out. We need to code this ourselves so that we can actually check the tree we have created.

Trees are non-linear data structures so there is no single right way to traverse one. There are two main approaches we can take: depth-first or breadth-first traversal.

Depth-first will search all the way to the bottom of the tree first before working its way back up. It will then do the same thing on the next branch it finds. Breadth-first will visit every node on the current level of the tree, then every node on the next level down, and so on.

Let’s start by implementing a depth-first traversal.

Depth-First Tree Traversal

Strangely there are actually three standard subcategories of depth-first traversals: Pre-order, In-order, and Post-order. These describe the order at which we visit the three elements of each immediate subtree, ie. the root, the left node, and the right node. As a very quick overview we could summarise them as follows.

Given the subtree below…

Binary tree consisting of just a root, left node and right node

Here is the order each traversal method would visit the nodes:

Pre-Order: root -> left -> right
In-Order: left -> root -> right
Post-Order: left -> right -> root

This is useful information for coding each traversal but doesn’t help us understand them. Let’s look closer.

Visualising Depth-First Traversal

Imagine walking around the tree in an anti-clockwise loop, starting and ending at the root, and passing by every node. For the tree we built earlier, your path would look something like the grey line here:

Binary tree with continuous grey line traversing past each node

It turns out this is a really useful way of visualising how pre-order, in-order, and post-order visit each node. We do this by putting a spot to the left/bottom/right of each node, respectively, and noticing the order the grey line passes through these spots.

For pre-order traversal, the spot goes on the left of each node like so:

Binary tree with visual preorder traversal

Tracking the order that the line passes through each node’s spot produces the following sequence: 50, 30, 20, 40, 32, 70, 60, 80, 75, 85. This is the pre-order traversal of the tree!

Similarly for in-order traversal, the spot goes on the bottom of each node:

Binary tree with visual inorder traversal

The order we pass through the spots this time gives the sequence: 20, 30, 32, 40, 50, 60, 70, 75, 80, 85. This is the in-order traversal of the tree.

Finally, placing the spot on the right of each node will give the post-order traversal:

This time the sequence is: 20, 32, 40, 30, 60, 75, 85, 80, 70, 50.

This is a useful method for figuring out visually how each method traverses the tree. Now let’s look at coding them!

Pre-Order Traversal

If we think about how we want the code to work, a recursive solution appears the most natural. On each subtree we come to, we want to first visit the root, then the left child, then the right child. If one of the children is not a leaf (ie. it has its own children), we recursively call again with this child as the new root.

So code for this traversal could be as follows:

1class Tree:
2    def __init__(self, value):
3        self.value = value
4        self.leftChild = None
5        self.rightChild = None
6 
7    def insertChild(self, node, value):
8        if node is None:
9            return Tree(value)
10        if value < node.value:
11            node.leftChild = self.insertChild(node.leftChild, value)
12        elif value > node.value:
13            node.rightChild = self.insertChild(node.rightChild, value)
14        return node
15 
16    def preOrderTraversal (self, root):
17        if root is not None:
18            print(root.value)
19            self.preOrderTraversal(root.leftChild)
20            self.preOrderTraversal(root.rightChild)
21        else:
22            return

Note that the initial quick summary I gave that describes the order the traversals visit nodes is more useful for implementation than the section on visualisation. For pre-order, if the node is not ‘None’, we know to first visit the root, then the left, then the right. This is performed in the if-statement. Otherwise, if the root is none, the recursion ends and the function just returns ‘None’.

So let’s build our tree again, and see what this function prints.

1class Tree:
2    def __init__(self, value):
3        self.value = value
4        self.leftChild = None
5        self.rightChild = None
6 
7    def insertChild(self, node, value):
8        if node is None:
9            return Tree(value)
10        if value < node.value:
11            node.leftChild = self.insertChild(node.leftChild, value)
12        elif value > node.value:
13            node.rightChild = self.insertChild(node.rightChild, value)
14        return node
15 
16    def preOrderTraversal (self, root):
17        if root is not None:
18            print(root.value)
19            self.preOrderTraversal(root.leftChild)
20            self.preOrderTraversal(root.rightChild)
21        else:
22            return
23 
24if __name__ == '__main__':
25    rootNode = Tree(50)
26    rootNode.insertChild(rootNode, 30)
27    rootNode.insertChild(rootNode, 20)
28    rootNode.insertChild(rootNode, 40)
29    rootNode.insertChild(rootNode, 32)
30    rootNode.insertChild(rootNode, 70)
31    rootNode.insertChild(rootNode, 60)
32    rootNode.insertChild(rootNode, 80)
33    rootNode.insertChild(rootNode, 75)
34    rootNode.insertChild(rootNode, 85)
35     
36    rootNode.preOrderTraversal(rootNode)

Printout of the nodes from a preorder traversal

This matches what we found when we visualised the traversal by hand!

This is the only traversal method that visits parents before it visits children. Hence it is best used for cloning a given tree. If we are trying to clone a tree, we need each parent to exist first before we can give it children. This traversal allows us to visit the parent first so is the best choice for this use case.

In-Order Traversal

Our code solution here will be incredibly similar to what we’ve written for pre-order traversal. The only difference is that for each subtree we want to now visit the left child first, then the root, then the right child. All we need to change is the order of the statements in the if-statement:

1class Tree:
2    def __init__(self, value):
3        self.value = value
4        self.leftChild = None
5        self.rightChild = None
6 
7    def insertChild(self, node, value):
8        if node is None:
9            return Tree(value)
10        if value < node.value:
11            node.leftChild = self.insertChild(node.leftChild, value)
12        elif value > node.value:
13            node.rightChild = self.insertChild(node.rightChild, value)
14        return node
15 
16    def inOrderTraversal (self, root):
17        if root is not None:
18            self.inOrderTraversal(root.leftChild)
19            print(root.value)
20            self.inOrderTraversal(root.rightChild)
21        else:
22            return

As we can see the code now reflects this new order for visiting nodes. Applied to our example tree in the same way as before, it prints:

Printout of the nodes from an inorder traversal

Again it matches our manual attempt to create the sequence.

For a binary search tree, In-order traversal will always print out the elements in non-decreasing order. This is useful for fairly obvious reasons – we tend to like it when things are sorted! If we wanted a non-increasing order of elements we could modify the code to visit the right child, then the root, then the left child.

Post-Order Traversal

As before, only a minor modification to the code is required to implement a post-order traversal. We simply reorder the statements so that we visit the left child first, then the right child, then the root.

1class Tree:
2    def __init__(self, value):
3        self.value = value
4        self.leftChild = None
5        self.rightChild = None
6 
7    def insertChild(self, node, value):
8        if node is None:
9            return Tree(value)
10        if value < node.value:
11            node.leftChild = self.insertChild(node.leftChild, value)
12        elif value > node.value:
13            node.rightChild = self.insertChild(node.rightChild, value)
14        return node
15     
16    def postOrderTraversal (self, root):
17        if root is not None:
18            self.postOrderTraversal(root.leftChild)
19            self.postOrderTraversal(root.rightChild)
20            print(root.value)
21        else:
22            return

Applied to our example tree, it prints:

Printout of the nodes from a postorder traversal

Looks correct again!

Post order visits all the children before it visits their parent node. This makes it a really good choice for deleting a binary tree. When we delete, we clearly want to first remove the children before the parent and this let’s us do that.

Breadth-First Traversal

We’ve had a good look at depth-first traversal methods so now we can turn our attention to the other main way of traversing a tree: breadth-first. This isn’t separated into three subcategories like before; breadth-first traversal exists on its own.

The key here is to visit every node at a particular level of the tree before moving on to the next level. By ‘level’ I’m referring to all the nodes that are at the same distance from the root. Let’s look at our example tree again to see this:

Binary tree with the level numbers annotated

So initially we’ll print 50. Then we’ll print 30, 70. Then we’ll print 20, 40, 60, 80. Finally, we’ll print 32, 75, 85.

For the code, I think the easiest way to implement it will be using a queue data structure. For those unfamiliar, it works exactly the same as a queue in the real world. Items can only join the queue at the back, and leave from the front. That’s really all there is to it.

So when we’re on a particular level of the tree, for each node we encounter we will print it’s value and then add it’s children to a queue. This will build a complete queue holding all the children of the current level. We then recursively call the function on each child in the queue (removing the child from the queue as we do this) until it’s empty. Here is an implementation of the breadth-first traversal.

1from queue import Queue
2 
3queue = Queue()
4 
5class Tree:
6    def __init__(self, value):
7        self.value = value
8        self.leftChild = None
9        self.rightChild = None
10 
11    def insertChild(self, node, value):
12        if node is None:
13            return Tree(value)
14        if value < node.value:
15            node.leftChild = self.insertChild(node.leftChild, value)
16        elif value > node.value:
17            node.rightChild = self.insertChild(node.rightChild, value)
18        return node
19 
20    def breadthFirstTraversal (self):
21        print(self.value)
22 
23        if self.leftChild is not None:
24            queue.put(self.leftChild)
25        if self.rightChild is not None:
26            queue.put(self.rightChild)
27         
28        while queue.empty() is False:
29            queue.get().breadthFirstTraversal()
30 
31if __name__ == '__main__':
32    rootNode = Tree(50)
33    rootNode.insertChild(rootNode, 30)
34    rootNode.insertChild(rootNode, 20)
35    rootNode.insertChild(rootNode, 40)
36    rootNode.insertChild(rootNode, 32)
37    rootNode.insertChild(rootNode, 70)
38    rootNode.insertChild(rootNode, 60)
39    rootNode.insertChild(rootNode, 80)
40    rootNode.insertChild(rootNode, 75)
41    rootNode.insertChild(rootNode, 85)
42     
43    rootNode.breadthFirstTraversal()

First note that I have imported a Python implementation of a queue. Second, our exit condition for ending the recursion is a little more subtle because there’s no return statements here (in Python, leaving no return statement will implicitly return ‘None’). We only add children to the queue if they pass the if-statement, ie. the child is not ‘None’. At the bottom of the tree all the children will be ‘None’ so nothing will be added to the queue. This means the while-loop will terminate immediately because the queue is empty, ending the recursion.

This code outputs:

Printout of the nodes from a breadth first traversal

This is consistent with what I said it should be! Our implementation seems correct.

One quick note to bear in mind is that breadth-first traversal uses much more memory than depth-first because you have to store all the nodes at the level that you’re on. For us this is okay but for enormous trees with multiple orders of magnitude more nodes per level it might become a concern. A solution for this circumstance could be to parallelise the algorithm over distributed-memory machines, but we will not go into that here.

Uses for this could be for finding people of a particular generation in a family tree, or returning files at a given level in a directory.

Finding the Height of a Tree

We’ve covered all the standard methods of traversing a tree which is the main goal I wanted to achieve, however if you’re interested in getting a little more exposure to trees I’m going to carry on adding a few extra methods to our class. The first will be finding the height of the tree. As a reminder the height is the longest path from the root to a leaf. It is equivalent to the number of levels we have in the tree. From the figure above we can see that there are four levels in the tree so the height of this tree is four.

The algorithm once again lends itself to a recursive implementation. At each node we can call the function again on both of its children. We terminate the recursion when we reach a leaf (ie. no further children exist). As we work back up the recursive stack, we’re clearly only interested in the child that gave us the largest depth to a leaf so we take the maximum value out of the left depth and the right depth. Then we need to also increment by one to account for the root node we are starting from.

Here is a possible implementation.

1class Tree:
2    def __init__(self, value):
3        self.value = value
4        self.leftChild = None
5        self.rightChild = None
6 
7    def insertChild(self, node, value):
8        if node is None:
9            return Tree(value)
10        if value < node.value:
11            node.leftChild = self.insertChild(node.leftChild, value)
12        elif value > node.value:
13            node.rightChild = self.insertChild(node.rightChild, value)
14        return node
15 
16    def calculateHeight(self, node):
17        if node is None:
18            return 0
19        else:
20            leftDepth = self.calculateHeight(node.leftChild)
21            rightDepth = self.calculateHeight(node.rightChild)
22            return max(leftDepth, rightDepth) + 1

Our exit condition is of course the case when no further children exist, meaning we are at a leaf so we just return 0 (the distance from a leaf to itself is 0).

Let’s check this on our example tree:

1class Tree:
2    def __init__(self, value):
3        self.value = value
4        self.leftChild = None
5        self.rightChild = None
6 
7    def insertChild(self, node, value):
8        if node is None:
9            return Tree(value)
10        if value < node.value:
11            node.leftChild = self.insertChild(node.leftChild, value)
12        elif value > node.value:
13            node.rightChild = self.insertChild(node.rightChild, value)
14        return node
15 
16    def calculateHeight(self, node):
17        if node is None:
18            return 0
19        else:
20            leftDepth = self.calculateHeight(node.leftChild)
21            rightDepth = self.calculateHeight(node.rightChild)
22            return max(leftDepth, rightDepth) + 1
23 
24if __name__ == '__main__':
25    rootNode = Tree(50)
26    rootNode.insertChild(rootNode, 30)
27    rootNode.insertChild(rootNode, 20)
28    rootNode.insertChild(rootNode, 40)
29    rootNode.insertChild(rootNode, 32)
30    rootNode.insertChild(rootNode, 70)
31    rootNode.insertChild(rootNode, 60)
32    rootNode.insertChild(rootNode, 80)
33    rootNode.insertChild(rootNode, 75)
34    rootNode.insertChild(rootNode, 85)
35     
36    print(rootNode.calculateHeight(rootNode))

Outputs:

As expected!

Summing Along the Path from the Root to a Leaf

This is an interesting problem to end on because it requires a couple of different ideas to make it work. It’s not too difficult though! Basically we want to allow the user to input a number and, if that number exists as a leaf in the tree, then we will output the sum of all the nodes we pass through on a path from the root to that leaf. We will incorporate some error handling to make sure the number entered is a leaf in the tree.

To start with, we’ll make the function for summing along the path to the leaf. It will be a recursive solution once again and we’ll exploit the main property of the binary search tree. That is to say, we can easily navigate to the required leaf by checking whether the leaf’s value is greater than or less than the node we are currently at. As an example, if the leaf’s value is greater than that of the current node, we’ll recursively call the function again on the right child of the current node. This approach will continue down to the target leaf which will simply return its own value.

Here is the implementation:

1class Tree:
2    def __init__(self, value):
3        self.value = value
4        self.leftChild = None
5        self.rightChild = None
6 
7    def insertChild(self, node, value):
8        if node is None:
9            return Tree(value)
10        if value < node.value:
11            node.leftChild = self.insertChild(node.leftChild, value)
12        elif value > node.value:
13            node.rightChild = self.insertChild(node.rightChild, value)
14        return node
15     
16    def rootToLeafSum (self, node, leaf):
17        totalSum = node.value
18        if node.value == leaf:
19            return leaf
20        elif leaf < node.value:
21            totalSum += self.rootToLeafSum(node.leftChild, leaf)
22        elif leaf > node.value:
23            totalSum += self.rootToLeafSum(node.rightChild, leaf)
24        return totalSum

As a reminder, here is our tree:

So lets test the code, inputting the leaf as 75.

1class Tree:
2    def __init__(self, value):
3        self.value = value
4        self.leftChild = None
5        self.rightChild = None
6 
7    def insertChild(self, node, value):
8        if node is None:
9            return Tree(value)
10        if value < node.value:
11            node.leftChild = self.insertChild(node.leftChild, value)
12        elif value > node.value:
13            node.rightChild = self.insertChild(node.rightChild, value)
14        return node
15     
16    def rootToLeafSum (self, node, leaf):
17        totalSum = node.value
18        if node.value == leaf:
19            return leaf
20        elif leaf < node.value:
21            totalSum += self.rootToLeafSum(node.leftChild, leaf)
22        elif leaf > node.value:
23            totalSum += self.rootToLeafSum(node.rightChild, leaf)
24        return totalSum
25 
26if __name__ == '__main__':
27    rootNode = Tree(50)
28    rootNode.insertChild(rootNode, 30)
29    rootNode.insertChild(rootNode, 20)
30    rootNode.insertChild(rootNode, 40)
31    rootNode.insertChild(rootNode, 32)
32    rootNode.insertChild(rootNode, 70)
33    rootNode.insertChild(rootNode, 60)
34    rootNode.insertChild(rootNode, 80)
35    rootNode.insertChild(rootNode, 75)
36    rootNode.insertChild(rootNode, 85)
37     
38    print(rootNode.rootToLeafSum(rootNode, 75))

This outputs:

Sum of the values along the path from the root to the leaf with value 75

Since 75 + 80 + 70 + 50 = 275, this output seems correct!

But error checking is a very important part of this implementation because if the leaf we input isn’t actually a leaf in the tree then our recursion will never terminate. To handle error checking, we need to generate a list holding all the leaves and then check the user’s input against this list.

The function to produce the list of leaves will borrow very similar ideas from other functions we’ve created so far. Given a node in the tree, we will recursively call the function on its children and continue doing this until both of a node’s children are ‘None’. Then we will add this node to our list of leaves.

Here is the code:

1class Tree:
2    def __init__(self, value):
3        self.value = value
4        self.leftChild = None
5        self.rightChild = None
6 
7    def insertChild(self, node, value):
8        if node is None:
9            return Tree(value)
10        if value < node.value:
11            node.leftChild = self.insertChild(node.leftChild, value)
12        elif value > node.value:
13            node.rightChild = self.insertChild(node.rightChild, value)
14        return node
15 
16    def findLeaves(self, node):
17        leaves = []
18        if node is None:
19            return []
20        elif (node.leftChild == None) & (node.rightChild == None):
21            leaves.append(node.value)
22        else:
23            leaves = leaves + self.findLeaves(node.leftChild)
24            leaves = leaves + self.findLeaves(node.rightChild)
25        return leaves
26 
27if __name__ == '__main__':
28    rootNode = Tree(50)
29    rootNode.insertChild(rootNode, 30)
30    rootNode.insertChild(rootNode, 20)
31    rootNode.insertChild(rootNode, 40)
32    rootNode.insertChild(rootNode, 32)
33    rootNode.insertChild(rootNode, 70)
34    rootNode.insertChild(rootNode, 60)
35    rootNode.insertChild(rootNode, 80)
36    rootNode.insertChild(rootNode, 75)
37    rootNode.insertChild(rootNode, 85)
38     
39    print(rootNode.findLeaves(rootNode))

This outputs:

Referring to the above image of our tree, we can confirm that this is a correct list of leaves.

So now before we try to sum along the path to the given leaf, we’ll just quickly check that that leaf is valid. I’ve added a new class to handle the exception and also added some extra code to continue asking the user for a number until they give a valid one.

Here is everything all together:

1class LeafNotInTreeError(Exception):
2    pass
3 
4class Tree:
5    def __init__(self, value):
6        self.value = value
7        self.leftChild = None
8        self.rightChild = None
9 
10    def insertChild(self, node, value):
11        if node is None:
12            return Tree(value)
13        if value < node.value:
14            node.leftChild = self.insertChild(node.leftChild, value)
15        elif value > node.value:
16            node.rightChild = self.insertChild(node.rightChild, value)
17        return node
18     
19    def rootToLeafSum (self, node, leaf):
20        totalSum = node.value
21        if node.value == leaf:
22            return leaf
23        elif leaf < node.value:
24            totalSum += self.rootToLeafSum(node.leftChild, leaf)
25        elif leaf > node.value:
26            totalSum += self.rootToLeafSum(node.rightChild, leaf)
27        return totalSum
28 
29    def findLeaves(self, node):
30        leaves = []
31        if node is None:
32            return []
33        elif (node.leftChild == None) & (node.rightChild == None):
34            leaves.append(node.value)
35        else:
36            leaves = leaves + self.findLeaves(node.leftChild)
37            leaves = leaves + self.findLeaves(node.rightChild)
38        return leaves
39 
40 
41if __name__ == '__main__':
42    rootNode = Tree(50)
43    rootNode.insertChild(rootNode, 30)
44    rootNode.insertChild(rootNode, 20)
45    rootNode.insertChild(rootNode, 40)
46    rootNode.insertChild(rootNode, 32)
47    rootNode.insertChild(rootNode, 70)
48    rootNode.insertChild(rootNode, 60)
49    rootNode.insertChild(rootNode, 80)
50    rootNode.insertChild(rootNode, 75)
51    rootNode.insertChild(rootNode, 85)
52 
53    treeLeaves = rootNode.findLeaves(rootNode)
54    while True:
55        try:
56            leaf = int(input("Enter a leaf: "))
57            if leaf not in treeLeaves:
58                raise LeafNotInTreeError()
59            break
60        except LeafNotInTreeError:
61            print("That leaf doesn't exist in the tree!")
62        except Exception as e:
63            print("Please enter an integer")
64 
65    print("The sum from the root to %d is: %d" % (leaf, rootNode.rootToLeafSum(rootNode, leaf)))

I will first input a string, then a float, then an integer that isn’t a leaf. This will check the error handling. I will then enter a valid leaf to check if the sum works. Here is the output code from this testing:

Demonstration of the error checking working as well as correctly summing root to leaf

Everything has worked as intended, including the sum to the leaf with value 20!

Summary

I will leave all the code for the entire class here, along with the code to form the tree we have been using as an example throughout.

1from queue import Queue
2 
3queue = Queue()
4 
5class LeafNotInTreeError(Exception):
6    pass
7 
8class Tree:
9    def __init__(self, value):
10        self.value = value
11        self.leftChild = None
12        self.rightChild = None
13 
14    def insertChild(self, node, value):
15        if node is None:
16            return Tree(value)
17        if value < node.value:
18            node.leftChild = self.insertChild(node.leftChild, value)
19        elif value > node.value:
20            node.rightChild = self.insertChild(node.rightChild, value)
21        return node
22 
23    def inOrderTraversal (self, root):
24        if root is not None:
25            self.inOrderTraversal(root.leftChild)
26            print(root.value)
27            self.inOrderTraversal(root.rightChild)
28        else:
29            return
30 
31    def preOrderTraversal (self, root):
32        if root is not None:
33            print(root.value)
34            self.preOrderTraversal(root.leftChild)
35            self.preOrderTraversal(root.rightChild)
36        else:
37            return
38     
39    def postOrderTraversal (self, root):
40        if root is not None:
41            self.postOrderTraversal(root.leftChild)
42            self.postOrderTraversal(root.rightChild)
43            print(root.value)
44        else:
45            return
46 
47    def breadthFirstTraversal (self):
48        print(self.value)
49 
50        if self.leftChild is not None:
51            queue.put(self.leftChild)
52        if self.rightChild is not None:
53            queue.put(self.rightChild)
54         
55        while queue.empty() is False:
56            queue.get().breadthFirstTraversal()
57 
58    def calculateHeight(self, node):
59        if node is None:
60            return 0
61        else:
62            leftDepth = self.calculateHeight(node.leftChild)
63            rightDepth = self.calculateHeight(node.rightChild)
64            return max(leftDepth, rightDepth) + 1
65     
66    def rootToLeafSum (self, node, leaf):
67        totalSum = node.value
68        if node.value == leaf:
69            return leaf
70        elif leaf < node.value:
71            totalSum += self.rootToLeafSum(node.leftChild, leaf)
72        elif leaf > node.value:
73            totalSum += self.rootToLeafSum(node.rightChild, leaf)
74        return totalSum
75 
76    def findLeaves(self, node):
77        leaves = []
78        if node is None:
79            return []
80        elif (node.leftChild == None) & (node.rightChild == None):
81            leaves.append(node.value)
82        else:
83            leaves = leaves + self.findLeaves(node.leftChild)
84            leaves = leaves + self.findLeaves(node.rightChild)
85        return leaves
86 
87 
88if __name__ == '__main__':
89    rootNode = Tree(50)
90    rootNode.insertChild(rootNode, 30)
91    rootNode.insertChild(rootNode, 20)
92    rootNode.insertChild(rootNode, 40)
93    rootNode.insertChild(rootNode, 32)
94    rootNode.insertChild(rootNode, 70)
95    rootNode.insertChild(rootNode, 60)
96    rootNode.insertChild(rootNode, 80)
97    rootNode.insertChild(rootNode, 75)
98    rootNode.insertChild(rootNode, 85)

So today we’ve explored how to make a basic tree in Python, how to traverse it in multiple ways, and covered some extra functions on the tree!

Some possible extensions for you to implement yourself could be:

Return all the children on just one particular level of the tree.
Given a number, return true if there exists a path from root to a leaf that sums to this number. False otherwise.
Create the equivalent of this class for a tree with arbitrarily many children per node.

You can also download this code from GitHub here.

I hope you’ve enjoyed learning about trees!

≺ Back to Posts