Introduction to Trees

Introduction to Trees

Definition of Tree : Tree is a non‒linear data structure in which ‒

i) There is a specially designated node called root.

ii) The remaining nodes are partitioned into n>=0 disjoint sets T₁, T₂, T₃,... T_n

where T₁, T₂, T₃, ...,T_n are called the sub‒trees of the root.

The concept of tree is represented by following Fig. 6.1.1.

Basic Terminologies

Let us get introduced with some of the definitions or terms which are normally used.

From Fig. 6.1.2,

1. Root

Root is a unique node in the tree to which further subtrees are attached. For above given tree, node 10 is a root node.

2. Parent node

The node having further sub‒branches is called parent node. In Fig. 6.1.3 the 20 is parent node of 40, 50 and 60.

3. Child nodes

The child nodes in above given tree are marked as shown below.

4. Leaves

These are the terminal nodes of the tree.

For example

5. Degree of the node

The total number of sub‒trees attached to that node is called the degree of a node.

For example

6. Degree of tree

The maximum degree in the tree is degree of tree.

7. Level of the tree

The root node is always considered at level zero.

The adjacent nodes to root are supposed to be at level 1 and so on.

8. Height of the tree

The maximum level is the height of the tree. In Fig. 6.1.8 the height of tree is 3. Sometimes height of the tree is also called depth of tree.

9. Predecessor

While displaying the tree, if some particular node occurs previous to some other node then that node is called predecessor of the other node.

For example : While displaying the tree in Fig. 6.1.8 if we read node 20 first and then if we read node 40, then 20 is a predecessor of 40.

10. Successor

Successor is a node which occurs next to some node.

For example : While displaying tree in Fig. 6.1.8 if we read node 60 after reading node 20 then 60 is called successor of 20.

11. Internal and external nodes

Leaf node means a node having no child node. As leaf nodes are not having further links, we call leaf nodes external nodes and non leaf nodes are called internal nodes.

12. Sibling

The nodes with common parent are called siblings or brothers.

For example

Review Question

1. Explain the terms ‒ root, leaves, degree of tree and internal and external nodes.