A binary tree is a type of tree where each node can have at most 2 children. The children of a node in a binary tree are usually referred to as the left and right nodes of the parent.

Variations

Perfect Binary Tree

A perfect binary tree is any binary tree in which every node but the leaf nodes are full (that is they all have 2 children nodes), and all the leaf nodes are on the same level.

Properties

Each level of a perfect binary tree has exactly nodes where is the current level. Additionally, the total number of nodes in the total tree are where is the height of the tree of which are leaf nodes.

Complete Binary Tree

A complete binary tree is any binary tree in which the following conditions are met:

1. Every leaf node is in the bottom two levels.
2. The second to last level is completely filled in, (that is there are no nodes with less than two children) on the third to last level).
3. The leave nodes on the bottom level are as far to the left as possible (that is there are no gaps).

Full Binary Tree

A full binary tree is any binary tree in which all nodes either have two children or are leaf nodes.

Traversal

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

        self.left = left
        self.right = right


def in_order_traverse(root, visit):
    if root is None:
        return

    in_order_traverse(root.left, visit)
    
    visit(root.value)

	in_order_traverse(root.right, visit)