A tree is a non-linear data structure that organizes data in a hierarchical structure and this is a recursive definition. It is a set of one or more nodes, with one node identified as the tree’s root and all remaining nodes partitionable into non-empty sets, each of which is a subtree of the root.
Since it is a non-linear data structure, different tree data structures provide for faster and easier access to the data.
A node is a unit of data that contains a key or value as well as pointers to its child nodes.
The connecting link between two nodes is called a link.
The topmost node in a tree is called the root node. This is where the tree is originated from.
A parent node or ancestor is a node that has a branch from it to another node.
A child node (descendant or successor) is a node that is a descendent of another node.
Nodes that have the same parent are called sibling nodes.
Leaf Node and Internal Node
The node which does not have any child is called a leaf node or terminal node. The nodes having at least a child node is called an internal node.
Level of a Tree
Each step from top to bottom in a tree is referred to as the level of a tree.
The total number of children of a node is the degree of a node. The number of edges arriving at that node is called the in-degree of a node. The number of edges leaving that node is the out-degree of a node.
The highest degree of a node among all the nodes in the tree is referred to as the degree of the tree.
The total number of edges from the root node to a particular node is called the depth of that node.
The height of a node is the total number of edges that lie on the longest path from the node to any leaf node.
The height of a tree is the height of the root node.
Types of Tree
- Binary Tree
- Binary Search Tree
- AVL Tree
- Expression trees
- Tournament trees
Applications of Tree
- To search an element in a set quickly, Binary Search Trees(BSTs) are used.
- Heap sort is done by a kind of tree called Heap.
- Tries are modified version of trees used to store routing informations in routers.
- Compiler use a syntax tree to parse program you write.
- Shortest path trees and spanning Trees are used in bridges and routers.