https://gist.github.com/bgoonz/c6ddd80d7ae24eca670f5fbebb7795f0#file-bst-ipynb
There are lots of different types of tree data structures. A binary tree is a specific type of tree. It is called a binary tree because each node in the tree can only have a maximum of two child nodes. It is common for a node's children to be called either left or right.
Here is an example of a what a class for a binary tree node might look like:
class BinaryTreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
With this simple class, we can now build up a structure that could be visualized like so:
A "perfect" tree has all of its levels full. This means that there are not any missing nodes in each level.
"Perfect" trees have specific properties. First, the quantity of each level's nodes doubles as you go down.
Second, the quantity of the last level's nodes is the same as the quantity of all the other nodes plus one.
These properties are useful for understanding how to calculate the height of a tree. The height of a tree is the number of levels that it contains. Based on the properties outlined above, we can deduce that we can calculate the tree's height with the following formula:
In the formula above, n is the total number of nodes. If you know the tree's height and want to calculate the total number of nodes, you can do so with the following formula:
We can represent the relationship between a perfect binary tree's total number of nodes and its height because of the properties outlined above.