Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide to Stacks and Queues Data Structures

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 11

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 12

All You Need to Know About Linear Search Algorithm

Lesson - 13

All You Need to Know About Breadth-First Search Algorithm

Lesson - 14

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 15

The Best Tutorial to Understand Trees in Data Structure

Lesson - 16

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 17

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 18

All You Need to Know About Tree Traversal in Data Structure

Lesson - 19

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 20

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 21

Your One-Stop Solution for Graphs in Data Structures

Lesson - 22
The Best Tutorial to Understand Trees in Data Structure

You must have observed the different parts of trees, from your childhood. A tree has roots, stems, branches, and leaves. And each leaf in a tree linked through roots via a unique path. Hence, similarly, a tree in data structures possesses hierarchical relationships, e.g. family tree, Document Object Model (DOM) in HTML, etc.

Introduction to Tree in Data Structures

The tree is a nonlinear hierarchical data structure and comprises a collection of entities known as nodes. It connects each node in the tree data structure using "edges”, both directed and undirected.

The image below represents the tree data structure. The blue-colored circles depict the nodes of the tree and the black lines connecting each node with another are called edges.

You will understand the parts of trees better, in the terminologies section.

what-is-tree

After learning the introduction to a tree in data structures, you will see why you need a tree in data structures.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

The Necessity for a Tree in Data Structures

Other data structures like arrays, linked-list, stacks, and queues are linear data structures, and all these data structures store data in sequential order. Time complexity increases with increasing data size to perform operations like insertion and deletion on these linear data structures. But it is not acceptable for today's world of computation.

The non-linear structure of trees enhances the data storing, data accessing, and manipulation processes by employing advanced control methods traversal through it. You will learn about tree traversal in the upcoming section.

 But before that, understand the tree terminologies.

Tree Node

A node is a structure that contains a key or value and pointers in its child node in the tree data structure.

In the tree data structure, you can define the tree node as follows.

struct node

{

 int data;

 struct node *leftchild;

 struct node *rightchild;

}

root-node-of-the-tree.

Continuing with this tutorial, you will see some key terminologies of the tree in data structures.

Tree Terminologies

Root

  • In a tree data structure, the root is the first node of the tree. The root node is the initial node of the tree in data structures.
  • In the tree data structure, there must be only one root node.

Root-node.

Edge 

  • In a tree in data structures, the connecting link of any two nodes is called the edge of the tree data structure.
  • In the tree data structure, N number of nodes connecting with N -1 number of edges.

edges-of-tree-in-data

Parent 

In the tree in data structures, the node that is the predecessor of any node is known as a parent node, or a node with a branch from itself to any other successive node is called the parent node.

parent-node-of-tree-data-structure.

Child

  • The node, a descendant of any node, is known as child nodes in data structures.
  • In a tree, any number of parent nodes can have any number of child nodes.
  • In a tree, every node except the root node is a child node.

Child-node-of-tree-data-structure

Siblings

In trees in the data structure, nodes that belong to the same parent are called siblings.

sibling-of-tree-data-structure1

Leaf 

  • Trees in the data structure, the node with no child, is known as a leaf node.
  • In trees, leaf nodes are also called external nodes or terminal nodes.

leaf-node-of-tree-data-structure

Internal nodes

  • Trees in the data structure have at least one child node known as internal nodes.
  • In trees, nodes other than leaf nodes are internal nodes.
  • Sometimes root nodes are also called internal nodes if the tree has more than one node.

/internal-nodes-in-tree-data

Degree

  •  In the tree data structure, the total number of children of a node is called the degree of the node.
  • The highest degree of the node among all the nodes in a tree is called the Degree of Tree.

degree-of-tree-data-structure

Level

In tree data structures, the root node is said to be at level 0, and the root node's children are at level 1, and the children of that node at level 1 will be level 2, and so on.

level-of-tree-data-structure

Height

  • In a tree data structure, the number of edges from the leaf node to the particular node in the longest path is known as the height of that node.
  • In the tree, the height of the root node is called "Height of Tree".
  • The tree height of all leaf nodes is 0.

height-of-tree-data-structure

Depth

  • In a tree, many edges from the root node to the particular node are called the depth of the tree.
  • In the tree, the total number of edges from the root node to the leaf node in the longest path is known as "Depth of Tree".
  • In the tree data structures, the depth of the root node is 0.

depth-of-tree-data-structure.

Path

  • In the tree in data structures, the sequence of nodes and edges from one node to another node is called the path between those two nodes.
  • The length of a path is the total number of nodes in a path.zx

Path-of-tree-data-structure.

Subtree

In the tree in data structures, each child from a node shapes a sub-tree recursively and every child in the tree will form a sub-tree on its parent node.

subtree-in-tree-data-structure

Now you will look into the types of trees in data structures.

Types of Tree in Data Structures

Here are the different kinds of tree in data structures:

General Tree

The general tree is the type of tree where there are no constraints on the hierarchical structure.

Properties

  • The general tree follows all properties of the tree data structure.
  • A node can have any number of nodes.

Trees-Soni/general-tree

Binary Tree

A binary tree has the following properties:

Properties

  • Follows all properties of the tree data structure.
  • Binary trees can have at most two child nodes.
  • These two children are called the left child and the right child.

Trees-Soni/binary-tree.

Add Another Star to Your Performance Evaluation

Learn from industry experts for FREEStart Learning
Add Another Star to Your Performance Evaluation

Binary Search Tree 

A binary search tree is a type of tree that is a more constricted extension of a binary tree data structure.

Properties

  • Follows all properties of the tree data structure.
  • The binary search tree has a unique property known as the binary search property. This states that the value of a left child node of the tree should be less than or equal to the parent node value of the tree. And the value of the right child node should be greater than or equal to the parent value.

Trees-Soni/binary-search-tree1.

AVL Tree 

An AVL tree is a type of tree that is a self-balancing binary search tree.

Properties

  • Follows all properties of the tree data structure.
  • Self-balancing.
  • Each node stores a value called a balanced factor, which is the difference in the height of the left sub-tree and right sub-tree.
  • All the nodes in the AVL tree must have a balance factor of -1, 0, and 1.

Trees-Soni/AVL-TREE.

Red-Black Tree

  • A red-black tree is a self-balancing binary search tree, where each node has either the color of red or black.
  • The colors of the nodes are used to make sure that the tree remains approximately balanced during insertion and deletion.

Properties

  • Follow all properties of binary tree data structure.
  • Self-balancing.
  • Each node is either red or black.
  • The root and leaves nodes are black.
  • If the node is red, then both children are black.
  • Every path from a given node to any of its nodes must go through the same number of black nodes.

/RED-BLACK-TREE

Splay Tree

A splay tree is a self-balancing binary search tree.

Properties

  • Follows properties of binary tree data structure.
  • Self-balancing.
  • Recently accessed elements are quicker to access again.

After you perform operations such as insertion and deletion, the splay tree acts, which is called splaying. Here it rearranges the tree so that the particular elements are placed at the root of the tree.

SPLAY-TREE

Treap Tree

The Treap tree is made up of a tree, and the heap is a binary search tree.

Properties

  • Each node has two values: a key and a priority.
  • Follows a binary search tree property.
  • Priority of the treap tree follows the heap property.

TREAP-TREE.

Tree Traversal

Traversal of the tree in data structures is a process of visiting each node and prints their value. There are three ways to traverse tree data structure.

  • Pre-order Traversal
  • In-Order Traversal
  • Post-order Traversal

In-Order Traversal

In the in-order traversal, the left subtree is visited first, then the root, and later the right subtree.

Algorithm:

Step 1- Recursively traverse the left subtree

Step 2- Visit root node

Step 3- Recursively traverse right subtree

/INORDER-TRAVERSAL

Pre-Order Traversal

In pre-order traversal, it visits the root node first, then the left subtree, and lastly right subtree.

Algorithm:

Step 1- Visit root node

Step 2- Recursively traverse the left subtree

Step 3- Recursively traverse right subtree

PREORDER-TRAVERSAL

Post-Order Traversal

It visits the left subtree first in post-order traversal, then the right subtree, and finally the root node.

Algorithm:

Step 1- Recursively traverse the left subtree 

Step 2- Visit root node

Step 3- Recursively traverse right subtree

POSTORDER-TRAVERSAL


#include <stdio.h>

#include <stdlib.h>

struct node {

  int data;

  struct node* left;

  struct node* right;

};

void inorder(struct node* root) {

  if (root == NULL) return;

  inorder(root->left);

  printf("%d ->", root->data);

  inorder(root->right);

}

void preorder(struct node* root) {

  if (root == NULL) return;

  printf("%d ->", root->data);

  preorder(root->left);

  preorder(root->right);

}

void postorder(struct node* root) {

  if (root == NULL) return;

  postorder(root->left);

  postorder(root->right);

  printf("%d ->", root->data);

}

struct node* createNode(item) {

  struct node* newNode = malloc(sizeof(struct node));

  newNode->data = item;

  newNode->left = NULL;

  newNode->right = NULL;

  return newNode;

}

struct node* insertLeft(struct node* root, int item) {

  root->left = createNode(item);

  return root->left;

}

struct node* insertRight(struct node* root, int item) {

  root->right = createNode(item);

  return root->right;

}

int main() {

  struct node* root = createNode(7);

  insertLeft(root, 12);

  insertRight(root, 29);

  insertLeft(root->left, 15);

  insertRight(root->left, 26);

  printf("Inorder  \n");

  inorder(root);

  printf("\nPreorder \n");

  preorder(root);

  printf("\nPostorder  \n");

  postorder(root);

}

Application of Tree in Data Structures

  • Binary Search Tree (BST) is used to check whether elements present or not.
  • Heap is a type of tree that is used to heap sort.
  • Tries are the modified version of the tree used in modem routing to information of the router.
  • The widespread database uses B-tree.
  • Compilers use syntax trees to check every syntax of a program.

With this, you’ve come to the end of this tutorial about the tree in data structures.

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Next Step

"Graphs in data structure" can be your next topic. As a tree data structure, the graph data structure is also a nonlinear data structure consisting of nodes and edges.

If you are interested in building a career in the field of software development, then feel free to explore Simplilearn's Courses that will give you the work-ready software development training you need to succeed today. Are you perhaps looking for a more comprehensive training program in the most in-demand software development skills, tools, languages used today? If yes, our Post Graduate Program in Full Stack Development should prove to be just the right thing for your career. Explore the course and enroll soon.

If you have any questions regarding the “tree in data structures tutorial”, please let us know in the comment section below. Our experts will get back to you ASAP.

Happy learning!

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.