Trees

Trees

Written by Richa Kiran on Jul 14th, 2021 Views Report Post

A Tree is a non linear data structure. Unlike the data structures that we've learned so far like - Linked Lists, Stacks, Queues, etc. In this type of data structure, one element can be linked to more than one element.

Tree data structure, just like the other data structures we've learned so far, is an example of abstract data type.

The tree data structure looks sort of like this - giphy.gif Just like a linked list, each of those circles or units that you can see in the above figure is called a "Node".

Basic Definitions

To be able to understand the Tree data structure perfectly, you'll need to pay a lot of attention towards the terminologies used in it.

Some of the basic terms used in it are - Root Node

In the above figure, the topmost node that you can see is called the "Root Node". The name is pretty much self explanatory, doesn't it look like the origin point of roots of a plant? rootnode.gif Edge

The lines that are connecting each pair of nodes in the above diagram is called an "Edge". edge.gif

Leaf Node

The node which is not connected to any other node below its level is called a "Leaf Node". LEAFNODE.gif

Child Node

Choose a random node in the above diagram. Does it have a Node above it? If it does, then it is a "Child Node" of the Node above it. If it doesn't then it is the root node. A root node can never be a child node. If we add a node above the root node, then it no longer remains the root node. childnode.gif

Parent Node

Again, choose a random node in the above diagram. Does it have a Node below it? If it does, then it is a "Parent Node" for the node(s) below itself. If it doesn't have anything below it, then it is a leaf node. A leaf node can never be a Parent Node. If you add a node below a leaf node, then it would no longer be a leaf node. parentnode.gif

Sibling Nodes

The nodes that have the same parent node are called "Sibling Nodes". sibling.gif

Degree of a Node

The number of Nodes a Node is connected to is called "Degree" of that Node. Figures_2.png

Types of Trees

Now that we know the basic terminologies of a Tree, let's talk about the types of trees you will come across in Data Structures.

1.Normal Tree

This type of tree is free of all constraints. The word "Constraints" here mean, how we insert and delete the nodes based on the values of the nodes of the tree, how we adjust the arrangements nodes of the tree after insertion or deletion, how many children a node can have in the tree and so on. images.png

2.Binary tree

In this type of tree, a node can not have more than 2 child nodes. binartree.jpeg

3.Binary Search Tree

This is also a binary tree but, here the left child node should have a smaller value than the parent node value and the right child node should have a value greater than the parent node. binary-search-tree-insertion-animation.gif

4.AVL Tree

It is a self balancing tree. It is also a type of Binary tree. We'll learn about the balance of a tree as we go deeper into this topic. AVL_Tree_Example.gif There are many more trees in Data Structures, but the above are the most common ones.

This is it

I hope you liked this article. Check out my other articles here.

Happy Learning!

Comments (0)