The tree data structure is a hierarchical data structure. A tree consists of nodes organized in the parent-child relationship. In a tree, each node can have more than one child but only a single parent.
A tree can also be called a special case of a graph where each node is connected and there is not a cycle. The most common example of a tree is the file system of Linux.
A tree node consists of data and references of children nodes. Given below is a node with n children. It consists of data and references to n nodes.
You can see how the tree is structured. We only have the reference to the top node which is called the root node. With that one reference, we traverse the whole tree which we will see later on. For simplicity, we have shown nodes as circles.
Termonologies Of Trees
Let’s see some of the common terminologies we use while using a tree data structure.
Edge: An Edge is a link between two consecutive nodes.
Root Node: It is the top node that does not have any parent.
Leaf Nodes or Terminal Nodes: These are the nodes that do not have any child node. C, D, E, G, and H are the leaf nodes.
Path: The sequence of consecutive edges is known as a path.
Ancestors: Any node in the path from the root to that node. For example, the ancestors of H are F and A.
Siblings: Nodes that belong to the same parent are called siblings. B, E, and F are siblings.
Degree: The degree of a node is the number of children the node has The degree of node A is 3. A leaf node has a degree of 0.
Height: The height of a node in a tree is the length of the maximum path from the node to the leaf node. The height of the tree is the height of the root node.
Depth: The depth of a node in a tree is the length of the path from the node to the root node. The height of a tree is the maximum height of leaf nodes in the tree.
Levels: In a tree, the leaf node is at level 0 and it increases at each step downwards. For example in the tree above, the root node is at level 0, Nodes B, E, F are at level 1, Nodes C, D, G, and H are level 2.
Sub Tree: Any tree which is a child of a node. T1, T2, and T3 are the subtrees.
Forest: A forest is set of disjoint trees. Here the set consisting of T1, T2 and T3 is forest.
Applications Of Tree In Data Structure
- The file system in Linux operating system uses a tree.
- In HTML, the DOM(Document Object Model) is a tree.
- The BST which is a type of tree is used for effective sorting and searching of elements.
- Compilers use a syntax tree to validate the syntax of every program you write.
- Trees are also used by most common databases to store data.