8.3BINARY TREE

A binary tree is a collection of nodes where each node contains three parts: the left child address, right child address, and the data item. The left child address stores the memory location of the top node of the left sub-tree and the right child address stores the memory location of the top node of the right sub-tree. The topmost element of the binary tree is known as a root node. The root stores the memory location of the root node. As the name suggests, a binary tree can have at most two children, that is, a parent can have zero, one, or at most two children. If root = NULL, then it means that the tree is empty. Figure 8.9 represents a binary tree.

In the following figure, A represents the root node of the tree. B and C are the children of root node A. Nodes B, D, E, F, and G constitute the left sub-tree. Similarly, nodes C, H, I, and J constitute the right sub-tree. Now, nodes G, E, F, I, and J are the terminal/leaf nodes of the binary tree, as they have no children...