TREE DATA STRUCTURE

Objective

The main objective of this document is to provide a brief introduction to tree data structure and its applications. It also presents details of main types of tree data structure.

Data Structure

A data structure is a collection of data types or values stored and organized to allow efficient access and modification. The data structure is used to store large data sets such as employee salary, stock price, etc. There are several types of data structures depending on the data arrangement. The types include,

• Linear data structure: Arrays and lists
• Tree data structure: binary
• Hash data structure: distributed hash table, hash tree
• Graphs: decision, directed, acyclic

Tree data structure

A tree is a non-linear data structure often used to represent hierarchical data. For example, in an organization, the tree would represent various positions and employees. It might also include details of the employee such as their salaries. (Figure 1).

Figure 1: An organizational tree data structure

Another example of a tree structure is an HTML file system. The document object model (DOM) represents a tree structure (Figure 2).

Figure 2: A DOM tree data structure

Components of tree data structure

The tree data structure has various components as shown in Figure 3.

Figure 3: A schematic of tree data structure with all components

• Node: Each data point is called a node
• Edge: Edge the connection between two nodes.
• Root: The node on the top of the tree. There is only one root node in a given tree.
• Parent: A node one edge above a given node (except the root node)
• Child: A node one edge below a given node
• Leaf: The bottom-level node that does not have any child.
• Siblings: Nodes that are at the same levels
• Subtree: It is a descendant of a node
• Level: It represents the generation of a node. For example, the root node is level 0; the next child is level 1, the grandchild is level 2, and so on
• Height: Number of levels from the root node to the leaf node
• Depth: Number of labels between the root node and a given node.

Benefits of tree data structure

The tree data structure is beneficial for any hierarchical data structure.

• It shows the relationship between data
• It provides the hierarchical information in an efficient manner
• It also provides an efficient insertion and search option

Tree traversal

There are two main traversal paths for the tree data structure.

1. Depth-first traversal: This traversal starts with the root node and then moves to all nodes in one branch as deep as possible and then moves to the next branch. In Figure 3, the Depth-first traversal path will be A-B-D-H-I-E-J-C-F-G.
2. Breadth-first traversal: In this traversal, the path starts from a root node and then moves to all nodes at a level before moving to the next level. In Figure 3, the Breadth-first traversal path will be A-B-C-D-E-F-G-H-I-J.

Types of tree data structure

The most common types of tree data structures are:

N-ary Tree — A tree where the number of nodes can vary from 0 to N. If the number of nodes is 2, it will be a 2-ary tree known as a Binary tree.

Balanced Tree — A tree where almost all leaf nodes are on the same level.

Complete binary tree — A binary tree where all nodes are filed except the last level nodes. For the last level, all nodes on the left are filled.

Full binary tree — A binary tree where each node has two children except the leaf nodes.

Perfect binary tree — A binary tree where each node has two children and all interior nodes also have two children. A perfect binary tree will have the same depth for all leaves.

Binary search tree — A binary search tree is a binary tree where each node has a key and a value that allows for an efficient search and manipulation. In a binary search tree, the left subtree should have nodes with a value less than the parent node, and the right subtree should have nodes with a value greater than the parent node.

AVL tree — An AVL tree is a binary search tree where the height difference between the left and right subtree can only be -1, 0, and 1. If it is more than one, the tree has to be rebalanced by performing a rotation.

Applications

There are several applications of tree data structure. The most common usage is:

Decision making: The tree structure is commonly used to provide information about the next step in a process, for example, the next move in a game. The computer chess games are built with a large tree data structure. The game algorithm utilizes the data present to find out the next optimal move.

Networking: The network details are stored in a tree data structure. It provides the network routing details where the route for a given request is presented. The DOM is a good example of networking using the tree data structure. A user request is accessed using the routing path provided in the DOM object.

Organization: The document object handling is performed using the tree structure. The tree structure is often used to organize the files in the operating system. The organizational structure of a company is also a tree data structure.

Manipulation of hierarchical data: The tree data structure is a valuable tool for storing, searching, and manipulating Hierarchical data. The organizational structure is a good example of retrieving and manipulating data. The employee information could be efficiently added or rendered using this data structure.

Reference

https://java-questions.com/binary-tree-in-details.html#:~:text=Advantages%20of%20trees&text=Trees%20reflect%20structural%20relationships%20in,subtrees%20around%20with%20minumum%20effort

https://www.tutorialspoint.com/data_structures_algorithms/tree_data_structure.htm

https://towardsdatascience.com/4-types-of-tree-traversal-algorithms-d56328450846

https://www.educative.io/blog/data-structures-trees-java

http://www.pradipbobhate.com/article/show/application-of-trees#gsc.tab=0

https://www.w3schools.com/js/js_htmldom.asp