# 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).

• 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)

### Terminology

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

#### Root

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

#### Subtree

It is the connected structure below the root node.

#### Leaf

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

#### Parent

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

#### Child

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

#### Siblings

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

#### Ancestor

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

#### Descendant

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

#### Path

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

#### Degree

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

#### Indegree

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

#### Outdegree

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

#### Level

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

#### Depth

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