Binary Tree Methods in Python
In this post I show you a class for creating binary trees (and a cool way to display them!), as well as some methods for analyzing binary trees. Enjoy!
In this article you will learn about:
- What binary trees are and what they are good for
- How to build them from scratch in Python
- How to insert into a binary tree
- How to find the depth of a tree
- How to traverse the tree in different ways
- How to find the maximum value in a tree
- What a balanced tree is, and how to balance one that is unbalanced
- What binary heaps are and how to use them in Python
Table of Contents
Introduction: What are Binary Trees?
A binary tree is a data structure where each node has at most two children, as shown in the diagram above. Binary Trees are incredibly useful in certain applications because they’re intuitive and can perform fast search operations. Because the structure is repeating, the code necessary to execute tasks on binary trees is often compact and recursive.
Creating and Inserting into Binary Tree
To follow along with this code, you can clone the binary_tree Node class from this Github repo: Binary Trees
A binary tree can be created fairly easily by declaring the following class:
Note that althought the smallest element will always be at index 0, the rest of the list isn’t necessarily sorted. That being said, the heapq.heappop() method will always pop the smallest element (removed the element from the list)
Removing from the heap
>>> heapq.heappop(h) 1 >>> heapq.heappop(h) 6 >>> heapq.heappop(h) 12 >>> heapq.heappop(h) 14 >>> heapq.heappop(h) 14 >>> heapq.heappop(h) 29 >>> h [44, 56, 88]Adding to the heap
>>> heapq.heappush(h,16) >>> h [16, 44, 88, 56]Summary
That’s it! in this post we covered the following topics:
- Creating binary trees in Python.
- What binary trees are and what they are good for.
- How to build them from scratch in Python.
- How to insert into a binary tree.
- How to find the depth of a tree.
- How to traverse the tree in different ways.
- How to find the maximum value in a tree.
- What a balanced tree is, and how to balance one that is unbalanced.
- What binary heaps are and how to use them in Python.
I hope you enjoyed this post!