A tree is a hierarchical data Structure. A tree is defined as a finite set of one or more data items (node) such that,
- There is a special node called the root of the tree.
- The remaining nodes are partitioned into n>=0 disjoint subsets, each of which is itself a tree, and they are called sub-trees.
A tree data structure can be defined recursively as a collection of finite nodes where each node is a data structure consisting of some information together with a list of references to nodes with the constraints that no reference is duplicated, and none points to the root.
In the figure above, the nodes are shown in circles and these nodes are connected through lines or arcs. Node A is the root of the tree. Node B is the successor node of A. A is the predecessor of node A. Node A is also called the father or parent of node B and node B is the son or child of node A. Nodes B and C are the children of node A. Similarly, node C is the father of nodes F and G, and nodes F and G are children of node C. Nodes B and C are siblings as both nodes have a common parent.
Nodes B, C, D, E, and C are internal nodes as they have a child or children. Nodes D, H, F, and G are external nodes and are also called terminal nodes as they have no successor.
The level of a node is defined as :
- The root of a tree is at level 0.
- The level of any node is more than the level of its predecessor.
In the above figure, the following observations can be made –
- The root A is at level 0
- The nodes B and C are at level 1.
- The nodes D,E,F and G are at level 2
- The node H is at level 3
The depth/height of a tree is one more than the largest level. In this case, the depth of the tree is 3+1 = 4.
The tree is further categorized into the following types which we are going to deal with in other articles.
Types of Trees in Data Structure–
- Binary Tree
- Binary Search Tree
- AVL Tree
- B-Tree
The tree is one of the very useful data structures as it has a lot of useful applications that include –
- Binary Search Trees(BSTs) are used to quickly check whether an element is present in a set or not.
- Heap is a kind of tree that is used for heap sort.
- A modified version of a tree called Tries is used in modern routers to store routing information.
- Most popular databases use B-Trees and T-Trees, which are variants of the tree structure we learned above to store their data
- Compilers use a syntax tree to validate the syntax of every program you write.
Try these Quizzes
