Data Structures


Study Material


A tree is a finite set of one or more nodes such that -
i)  Root node: It is a specially designated node.
ii) There are remaining n nodes which can be partitioned into disjoint sets A1, A2, A3 ... An where  A2, A3... An are called subtrees of the root.

Fig 1

Some definitions


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

Parent node

The node haviog further sub-branches is called parent node. In Fig. 2 , 20  is parent node of 40, 50 and 60. 

tree with parent node

                                                               Fig 2



Child Nodes

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


tree with child nodes

                                                                                   Fig 3


These are the terminal nodes of the tree. 


Degree of the node
The total number of sub-trees attached to that node is called the degree of a node
For example
degree of node
                                                                            Fig 4 
Degree of tree
The maximum degree in the tree is degree of tree.
maximum dgree of tree



                                                                            Fig 5



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.
level of tree
                                                               Fig 6
Height of the tree
The maximum level is the height of the tree. In fig 6 given above   the height of tree is 3. Sometimes height of the tree is also called depth of tree.
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  if we read node 20 first and then if we read node 40, Ihen 20 is a predecessor of 40.
Successor is a node which occurs next to some node.
For example: While displaying tree in Fig. 6  if we read node 60 after reading node 20 then 60 is called successor of 20.