3 Binary trees

A binary tree is a tree such that a parent can have at most two children. In other words, for a tree represented by (N,P), ∀n ∈ N : ≤ 2.

In many cases, it is important to differentiate the two children of a node. If this differentiation is necesary, we modify the representation of a general tree so that a binary tree is represented by a tuple (N,P_L,P_R), in which (a,b) ∈ P_L means that b is the left child of a, and (a,b) ∈ P_R means that b is the right child of a.

We need to redefine what a subtree is. Let T((N,P_L,P_R),n) be a subtree of (N,P_L,P_R) rooted at node n. Then T((N,P_L,P_R),n) = (N′,P_L′,P_R′), and

• The predicate A for a binary tree (N,P_L,P_R) needs to be redefined: ∀n,m ∈ N : ((∃(n,m) ∈ P_L)∨(∃(n,m) ∈ P_R)) ⇒ A(n,m). The recursive part is still the same: ∀a,b,c ∈ N : (A(a,b) ∧ A(b,c)) ⇒ A(a,c).
• n ∈ N′, ∀m ∈ N : A(n,m) ⇒ m ∈ N′.
• ∀(n,m) ∈ P_L : (n ∈ N′) ⇒ (n,m) ∈ P_L′.
• ∀(n,m) ∈ P_R : (n ∈ N′) ⇒ (n,m) ∈ P_R′.

Binary trees are special because they are the “smallest” trees. If a parent can have at most one child, then a tree degenerates to a linked list. In addition, a binary tree is very well suited to represent decision making, assuming each decision only has up to two alternative actions.

Last, but not least, many operators (multiply, divide and etc.) require up to two operands. This means a binary tree can also be used to represent operators and operands in an expression.