# Data Structures - Tree ADT

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

- 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**