A binary tree is a tree in which every node has at most two children: left and right. Binary trees underlie search trees, heaps and expression trees. We covered the terms and traversals of a general tree in the previous topic; now we implement a binary tree and study its properties.

Three kinds of binary trees: full, complete and perfect
Three kinds of binary trees: full, complete and perfect

The node class and in-order

A node has value, left and right; a missing child is None. In-order traversal: the left subtree, the node, the right subtree. It is possible only for a binary tree, and in a binary search tree it yields the values in sorted order.

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

def sample():
    return Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))

def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

print(inorder(sample()))
text
[4, 2, 5, 1, 3, 6]

Height, node count, diameter

We take the height of an empty tree as -1: then a leaf gives 1 + max(-1, -1) = 0. The diameter is the number of edges in the longest path of the tree. The longest path through a node equals left height + right height + 2 (with the -1 height convention). It is computed in a single pass, O(n).

python
def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

def count(node):
    if node is None:
        return 0
    return 1 + count(node.left) + count(node.right)