Page 205 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Linked representation of binary trees

Binary trees can be represented by links, where each node contains the address of the left child
and the right child. These addresses are nothing but kinds to the left and right child respectively.

!
Caution A node that does not have a left or a right child contains a NULL value in its link
fields.
Linked structures uses space more efficiently and provides more flexibility. In order to implement
a binary tree using a linked structure, each node should have:
A data component

Two link components:
left, pointing to the left child
right, pointing to the right child

Figure 12.5: Linked Structure of a Binary Tree

Source: http://www.cs.tut.fi/~prog2/material/Lec8.pdf
The linked representation is shown as below:

Figure 12.6: Linked Representation

Source: http://www.cs.tut.fi/~prog2/material/Lec8.pdf

198 LOVELY PROFESSIONAL UNIVERSITY