Tree Data Structure

We have all watched trees from our childhood. It has roots, stems,
branches and leaves.
Hence tree structure was used to explain hierarchical relationships,
e.g. family tree, animal kingdom classification, etc.
The tree is a nonlinear hierarchical data structure and comprises a
collection of entities known as nodes.

A tree is also one of the data structures that represent hierarchical

data.
OR
A tree is a finite set of elements called nodes and a finite set of
directed lines called branches,which connect the nodes.
In real life tree,their root in bottom and branches and leaves are top,but
here tree concept of data structure,in root is top and branches and
leaves are bottom of the tree.

Real Life Tree

Let's understand some key points of the Tree data structure.
● A tree data structure is defined as a collection of objects or
entities known as nodes that are linked together to represent a
hierarchy.
● It's a non linear data structure as it does not store data in a
sequential manner, but stores in a hierarchical fashion.
● In the Tree data structure, the first node is known as a root node
i.e. from which the tree originates. Each node contains some data
and also contains references to child nodes. A root node can
never have a parent node.
Types Of Trees in Data Structure

General tree: In the general tree, each node has either 0 or n number
of nodes. In this tree, there is no limitation to the number of nodes. It
starts with a root node and the children of the parent node make
another general sub tree.

Binary Tree: In a binary tree, each node can have at most 2 children
(i.e. either 0, 1, 2). There is no restriction as to what data will be in the
left child or right child.
Binary Search Tree: A binary search tree just like a binary tree can
have at most 2 children. It can have n nodes and also each node can be
defined as a data part that holds the data, left child and the right node.

Tree Data Structure Terminologies

● Root: The root node is the topmost node in the tree hierarchy. In
other words, the root node is the one that doesn't have any
parent. In the above structure, node A is the root node of the
tree. If a node is directly linked to some other node, it would be
called a parent-child relationship.
● Child node: If the node is a descendant of any node, then the
node is known as a child node.
● Parent: If the node contains any sub-node, then that node is said
to be the parent of that sub-node.
● Sibling: The nodes that have the same parent are known as
siblings.
● Leaf Node: The node of the tree, which doesn't have any child
node, is called a leaf node. A leaf node is the bottom-most node
of the tree. There can be any number of leaf nodes present in a
general tree. Leaf nodes can also be called external nodes.
● Internal nodes: A node has at least one child node known as an
internal
● Ancestor node: An ancestor of a node is any predecessor node
on a path from the root to that node. The root node doesn't have
any ancestors. In the tree shown in the above image, nodes A, C,
and G are the ancestors of node K.
● Descendant: The immediate successor of the given node is
known as a descendant of a node. In the above figure, K is the
descendant of node G.

Properties of Tree data structure

● Recursive data structure: The tree is also known as a recursive
data structure. A tree can be defined as recursively because the
distinguished node in a tree data structure is known as a root
node. The root node of the tree contains a link to all the roots of
its subtrees.
● Number of edges: If there are n nodes, then there would be n-1
edges. Each arrow in the structure represents the link or path.
Each node, except the root node, will have at least one incoming
link known as an edge. There would be one link for the
parent-child relationship.
● Depth of node x: The depth of node x can be defined as the
length of the path from the root to the node x. One edge
contributes one-unit length in the path. So, the depth of node x
can also be defined as the number of edges between the root
node and the node x. The root node has 0 depth.
● Height of node x: The height of node x can be defined as the
longest path from the node x to the leaf node.

Based on the properties of the Tree data structure, trees are

classified into various categories.

Binary Trees
A binary tree is a tree-type non-linear data structure with a
maximum of two children for each parent.
A tree in which every root has either one or two nodes is called a
binary tree. The root component of a binary tree is having two
nodes. One is the right tree and the other is the left tree. It is called a
sub-tree.

Properties of Tree
● A binary tree is a special case of tree as defined in the preceding
section, in which no node of a tree can have a degree of more
than 2.
● Therefore, a binary tree is a set of zero or more nodes T such that:
○ (i) There is a specially designated node called the root of the
tree
○ (ii) The remaining nodes are partitioned into two disjoint
sets, T1, and T2, each of which is a binary tree.
● T1 is called the left sub tree and T2 is called the right subtree, or
vice-versa. A binary tree is shown in Figure

Implementation of Binary Tree

There are two traditional techniques that are used to maintain a binary
tree in memory. These are :

● Sequential representation
Using total number of nodes by array
● Linked representation
In this representation, each node requires three fields, one
for the link of the left child, second field for representing the
information associated with the node and the third field
representing the link of the right child.

Tree Traversal Techniques

Traversal
● One of the most common operations performed on tree
structures is that of traversal.
● This is a procedure by which each node in the tree is processed
exactly once in a systematic manner. The three main ways of
traversing a binary three are:
○ Pre order
○ In order
○ Post order
● For Inorder, you traverse from the left subtree to the root then
to the right subtree.
● For Preorder, you traverse from the root to the left subtree then
to the right subtree.
● For Post order, you traverse from the left subtree to the right
subtree then to the root.

Here is another way of representing the information above:

Inorder => Left, Root, Right.
Preorder => Root, Left, Right.
Post order => Left, Right, Root.
In-order Traversal
● In this traversal method, the left subtree is visited first, then the
root and later the right subtree. We should always remember that
every node may represent a subtree itself.

● If a binary tree is traversed in-order, the output will produce

sorted key values in an ascending order.

We start from A, and following in-order traversal, we move to its left

subtree B. B is also traversed in-order. The process goes on until all the
nodes are visited. The output of inorder traversal of this tree will be −
D→B→E→A→F→C→G

Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit the root node.
Step 3 − Recursively traverse the right subtree.
Pre-order Traversal
● In this traversal method, the root node is visited first, then the left
subtree and finally the right subtree.

We start from A, and following pre-order traversal, we first visit A itself

and then move to its left subtree B. B is also traversed pre-order. The
process goes on until all the nodes are visited. The output of pre-order
traversal of this tree will be −
A→B→D→E→C→F→G

Algorithm
Until all nodes are traversed −
Step 1 − Visit the root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse the right subtree.
Post-order Traversal
● In this traversal method, the root node is visited last, hence the
name. First we traverse the left subtree, then the right subtree
and finally the root node.

We start from A, and following Post-order traversal, we first visit the

left subtree B. B is also traversed post-order. The process goes on until
all the nodes are visited. The output of post-order traversal of this tree
will be −
D→E→B→F→G→C→A

Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse the right subtree.
Step 3 − Visit the root node.
Example
#include <stdio.h>
#include <stdlib.h>
struct node
{
int item;
struct node* left;
struct node* right;
};

// Inorder traversal
void inorderTraversal(struct node* root)
{
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ->", root->item);
inorderTraversal(root->right);
}

// Preorder traversal
void preorderTraversal(struct node* root)
{
if (root == NULL) return;
printf("%d ->", root->item);
preorderTraversal(root->left);
preorderTraversal(root->right);
}

// Postorder traversal
void postorderTraversal(struct node* root)
{
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ->", root->item);
}

// Create a new Node

struct node* createNode(value)
{
struct node* newNode = malloc(sizeof(struct node));
newNode->item = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Insert on the left of the node

struct node* insertLeft(struct node* root, int value)
{
root->left = createNode(value);
return root->left;
}

// Insert on the right of the node

struct node* insertRight(struct node* root, int value)
{
root->right = createNode(value);
return root->right;
}

int main()
{
struct node* root = createNode(1);
clrscr();
insertLeft(root, 2);
insertRight(root, 3);
insertLeft(root->left, 4);

printf("Inorder traversal \n");

inorderTraversal(root);

printf("\nPreorder traversal \n");

preorderTraversal(root);

printf("\nPostorder traversal \n");

postorderTraversal(root);
}