Page 207 - DCAP407_DATA_STRUCTURE

Data Structure

Figure 11.1 represents a binary tree.

Figure 11.1: A Binary Tree

In the figure 11.1, node a is the root, node b and c are its child nodes. The nodes b and c form two sub-
trees. Node b forms the left sub-tree of node a while node c forms the right sub-tree. The nodes without
successors are called as terminal nodes or leaf nodes. The nodes d, e, f and g are terminal nodes.

The average depth of binary tree is 0(√n).

Consider the binary tree in figure 11.2 with nodes 10, 20, 30, 40, 50, 100, 50.

Figure 11.2: A Binary Tree

The binary tree of figure 11.2 is structured such that the successor node value sums up to the value of
root node.
In this example, the root node is 100. The two nodes 50 and 50 form the left and the right sub-trees.
Similarly, left tree 50 has two sub-trees 10 and 40, the right tree sub-tree 50 has two sub-trees 20 and
30.The tree ends with terminal nodes 10, 40, 20 and 30.

Since the terminal nodes 10, 40, 20 and 30 do not have any successor nodes, they are termed as leaves.

200 LOVELY PROFESSIONAL UNIVERSITY