Data Structures - Tree ADT

<< Previous

Next >>

Tree is a simple and more useful data structure in which the average running time of most operation is O(log n).

Figure 1. Tree Structure

  • It used to implement the file system of computer system.
  • The mathematical expression is calculated by using trees data structure.
  • It supports searching operations in O(log n) average time.
  • Tree is defined as collection of n nodes, among that one node is the root node, and n-1 edges. In which every node has one parent except the root node.
  • It consists of a finite set of elements(called nodes) and a finite set of directed line(called branches or edges)


Various terms are used to describe the attributes of a tree as given below. These terms have been described based on Figure 2

Fig 2. A Tree


The first node is called root, in which indegree of root is zero. Root node is A


It is the connected structure below the root node.


Leaf is any node in which outdegree of the node is zero. Leaf nodes are D, E, and G


A node is parent if it has successor nodes. Parent nodes are B, C, and F


The node is a child if it has a one predecessor. B and C are the Child nodes of A.


Two or more nodes with same parent. D and E are siblings


It is any node in the path from root to that node. The ancestors of node D are B and A


All the nodes in the path from a given node to a leaf node. The descendents of node C are F and G


It is a sequence of nodes in which each node is adjacent to the next one. For reaching D, AB and BD these two branches should be added. Path is ABD


The number of lines associated with a node is called degree of the node. Degree of node B = 3
Degree of the node = Indegree + Outdegree


Number of branches directed towards the node. Indegree of node B = 1


The branch is directed away from the node. Outdegree of node B = 2


It is a distance from root node is that root node is at level 0, its next child is at level 1, and its grandchild is at level 2 and so on.
Level 0 node A
Level 1 nodes B and C
Level 2 nodes D, E and F

Height of the tree

The height of the tree is the level of the leaf in the longest path from root plus one.
The height of the tree is 4 (i.e. it has 3 levels (3+1))

Length of the path

It is the number of edges on that path. The length of the path from A to F is 2


The depth of the node is the length of unique path from root to that specific node. The depth of node G is 3

Height of the node

The height of the node is the longest path from that node to leaf. The height of node C is 2

<< Previous

Next >>

Learn C Progamming © 2017