Linked Implementation of Binary Trees

Binary tree has a natural implementation in a linked storage. Each node of a binary tree has both a left and a right subtree.

Each node will have three fields—Lchild, Data, and Rchild.

In this node structure, Lchild and Rchild are the two link fields to store the addresses of left child and right child of a node; data is the information content of the node.

 

Here, 0 (zero) stored at Lchild or Rchild fields represents that the respective child is not present.

Advantages

The merits of representing binary trees through liked representations are as follows:

1. Like sequential representation, memory is not wasted.

2. Insertion and deletion operations are more efficient.

3. It is useful for dynamic data.

Disadvantages

The demerits of representing binary trees through linked representation are as follows:

1. In this representation, there is no direct access to any node. It has to be traversed from the root to reach to a particular node.

2. Having two link fields require more memory of node.

3. The programming languages not supporting dynamic memory management would not be useful for this representation.

Insertion of a node in Binary tree

The node to be inserted could be a branch node or a leaf node.

The insertion procedure is a two-step process:

1. Search for the node whose child node is to be inserted. This is a node will be parent node at level i, and a node is to be inserted at the level i + 1 as either its left child or right child.

2. Link a new node to the node that becomes its parent node, that is, either the Lchild or the Rchild.

Ex: Insertion of node G as the Rchild of node F