Page 201 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes As you can see, the top most element is called the “root”. The nodes with no children are called
“Leaf” nodes. Here, if we say “D” is representing you then “E” becomes your sibling; “B”
becomes your parent; “A” becomes your ancestor (grand parent) and “C” is sibling of your
parent. If we call A as the root then B onwards is one sub tree and C onwards is another.

Did u know? A sub-tree can have zero or more sub-trees in it.
Every tree has a depth and height factor associated. These factors are associated with every node
in the tree. The depth of a particular node tells you how many generations down, that node is
from the Root. Similarly, height of a particular node tells you its distance from the deepest leaf
(or leaves) in that branch (or sub tree).

Example: In Figure 12.1, D and E are at height = 0; C is at height = 0; and A is at
height = 2.
The height of a Tree is nothing but the height of its root. Both of these factors have their own
importance at times.

Task Compare and contrast root node and internal node.

Self Assessment

Fill in the blanks:
1. ............................... is a data structure which allows you to associate a parent–child
relationship between various pieces of data.
2. A ............................... is a structure which may contain a value, a condition, or represent a
separate data structure.

3. Nodes that do not have any children are called ...............................
4. ............................... is the node at which operations on the tree commonly begin.
5. A .................................... of a tree T is a tree consisting of a node in T and all of its descendants
in T.
6. The ............................... of a particular node tells you how many generations down, that
node is from the Root.

12.2 Binary Tree

Any Tree whose nodes can have at the most two children is called a Binary tree or a tree with
order 2. Every node in a Binary tree has a structure like this:
Struct NODE
{
struct NODE *leftchild;
Int nodevalue; /*this can be of any type*/
struct NODE *rightchild;
}

194 LOVELY PROFESSIONAL UNIVERSITY