Binary trees

A binary tree is a collection of nodes, where the nodes in the tree can have zero, one, or two child nodes. A simple binary tree has a maximum of two children, that is, the left child and the right child.

For example, in the binary tree shown in Figure 6.2, there is a root node that has two children (a left child, a right child):

Figure 6.2: Example of a binary tree

The nodes in the binary tree are organized in the form of the left subtree and right subtree. For example, a tree of five nodes is shown in Figure 6.3 that has a root node, R, and two subtrees, i.e. left subtree, T1, and right subtree, T2:

Figure 6.3: An example binary tree of five nodes

A regular binary tree has no other rules as to how elements are arranged in the tree. It should only satisfy the condition that each node should have a maximum of two children.

A tree is called a full binary tree if all the nodes of a binary tree have either zero or two children, and if there...