Trees

Trees in C++

As we are already familiar with linear data structures like arrays, linked lists, stacks & queues. Tree, on the other hand, is a non-linear data structure. Before understanding the hook & nook about trees, it’s important to know where they are used and implemented.

All the above-mentioned data structures are different ways to store data, access the information and insert or delete as per requirement. Similarly, trees are also a method of storing, accessing, sorting the information.

Trees can also be called a hierarchical data structure as it saves the data/ information in the form of a natural hierarchy. It is a collection of nodes connected by edges.

e.g.

The topmost node is called the root of the tree. The elements directly under the node are called its children. The nodes having same parent are called sibling nodes.

In the above-shown pic of a tree, ‘home’ is the root of the tree. The elements hanging down are called left or the right child. A tree can be either empty with no nodes or may have multiple child nodes. However, a node can have multiple children but it can have only one parent node.

Hence, ‘secondary’ and ‘grad’ are children nodes of parent node ‘home’. In the same way, grad has one child node as ‘course’ which further has three children nodes, CS, DS & OS and these three are the sibling nodes.

Thus, the element directly above a node is its parent node and the nodes with no children are called ‘leaves’. 

Terminology of a Tree

Root Node: It is the topmost node of a tree. There is only one root node in a tree.

Parent node: Any node that is connected by an edge is a parent node. A parent node may or may not have children nodes.

Leaf nodes: The nodes with no children are called leaf nodes.

Sub-tree: It is the descendants of a node when the root is not null.

Keys: It is the value of the node.

Levels: It represents the generation of the node. Root node is level 0, and then its child node is level 1 and so on.

Path: It is sequence of successive edges; in above pic path to CS is home-🡪grad-🡪course-🡪CS.

Degree:  Degree of node is the number of children it has. Course node has a degree of 3 and secondary node has a degree of 0.

Main applications of a Tree

• Access/manipulate hierarchical data
• Make information easy to search via tree traversal
• Manipulate/maintain sorted lists of data
• Multi-stage decision making and is optimum for systems that read large blocks of data. Generally used in databases and file systems.
• A tree is implemented using pointers.

Some facts that put trees above other contemporary data structures are

• Trees are quicker than linked lists and provide moderate access/ search.
• Trees do not have an upper limit on the number of nodes as nodes are linked using pointers, unlike arrays.

Different types of trees

Binary Tree: These trees are special cases where every node in the tree has a maximum of two children.

 

Binary Search Tree: An ordered type of binary tree is called a Binary Search Tree or BST. In a BST, nodes to the left are less than the root node while nodes to the right are either equal to greater to the root node.

To conclude, we can say that trees have multiple ways to traverse it, unlike linear data structures which have only one way to traverse a list-making trees more efficient and less time consuming than its counterparts.