Tree Data Structure

A tree is a nonlinear hierarchical data structure that consists of nodes

connected by edges.

Tree

Why Tree Data Structure?

Other data structures such as arrays, linked list, stack, and queue are
linear data structures that store data sequentially. In order to perform
any operation in a linear data structure, the time complexity increases
with the increase in the data size. But, it is not acceptable in today's
computational world.

Different tree data structures allow quicker and easier access to the
data as it is a non-linear data structure.

Tree Terminologies
Node
A node is an entity that contains a key or value and pointers to its
child nodes.
The last nodes of each path are called leaf nodes or external
nodes that do not contain a link/pointer to child nodes.
The node having at least a child node is called an internal node.
Edge
It is the link between any two nodes.

Nodes and edges of a tree

Root
It is the topmost node of a tree.

Height of a Node
The height of a node is the number of edges from the node to the
deepest leaf (ie. the longest path from the node to a leaf node).

Depth of a Node
The depth of a node is the number of edges from the root to the node.

Height of a Tree
The height of a Tree is the height of the root node or the depth of the
deepest node.
 Height and depth of each node in a tree
Degree of a Node
The degree of a node is the total number of branches of that node.

Forest
A collection of disjoint trees is called a forest.

Creating forest from a tree

Tree Representation
If you recall a linked list representation, we store each item in a linked
list in a structure called Node having two or three fields (depending
on whether the list is singly or doubly). A node in a doubly linked list
stores a data field, a reference to the previous node and a reference to
the next node in the sequence. There are maximum two fields that
have a reference to the other nodes.
Like the linked list, we store each item in a tree in a node
with data field. The only difference from the linked list representation
is that a tree node can have more than 2 references that point to its
children nodes. If a node has degree 3, it has 3 reference fields. In
general, if a degree of a tree is n, we need n reference fields in each
node of the tree. Figure 1 shows the visual representation of a node in
a tree.

Fig 1: Visual representation of a node of a tree

Figure 2 shows a tree and corresponding representation using the

design discussed above.
Fig 2: Tree representation using the nodes that point to all of its children
While this representation is easy to implement and easy to understand, it is
only useful for representing a tree that has a small degree e.g. binary tree
where a maximum degree is 2. You can see in Figure 2 that most of the
reference fields are empty. If a tree has one node with a large degree and
other nodes with a small degree, we may waste a lot of memory.
Fortunately, there exists another method of representing a tree that takes
only O(n) space. This method is called left-child, right-sibling
representation. In this representation, each node has only three fields. One
is for storing data and pointers:

1. left-child points to the leftmost child of the node

2. right-sibling points to the sibling of the immediately to its right.

Figure 3 shows the structure of a node with only three fields.

Fig 3: Visual representation of node with three fields

Figure 3 clearly shows that no matter how many children a node has, it
stores only two pointers. Using these scheme, the tree in Figure 2 can be
represented as given in Figure 4.
 Fig 4: The left-child, right sibling representation

Binary Tree
A binary tree is a tree data structure in which each parent node can have at
most two children. Each node of a binary tree consists of three items:

● data item

● address of left child

● address of right child

 Properties of a Binary tree
● The maximum number of nodes at any level ‘L’ in a binary tree is 2

● The minimum number of nodes in a binary tree of height H is H + 1

● The maximum number of nodes in a binary tree of height H is 2H+1 – 1
● Total Number of leaf nodes in a Binary Tree = Total Number of nodes
with two children + 1
● The maximum number of nodes at each level of i is 2i.
● Searching operation takes O(log2N)
Binary trees can be divided into the following types:
● Perfect binary tree: Every internal node has two child nodes. All the leaf
nodes are at the same level.
● Full binary tree: Every parent node or an internal node has either exactly
two children or no child nodes.
● Complete binary tree: All levels except the last one are full of nodes.
● Degenerate binary tree: All the internal nodes have only one child.
● Balanced binary tree: The left and right trees differ by either 0 or 1.

Binary Tree Representations

A binary tree data structure is represented using two methods. Those methods are as follows...

1. Array Representation
2. Linked List Representation

Consider the following binary tree...

1. Array Representation of Binary Tree
In array representation of a binary tree, we use one-dimensional array (1-D Array) to
represent a binary tree.
Consider the above example of a binary tree and it is represented as follows...

To represent a binary tree of depth 'n' using array representation, we need one
dimensional array with a maximum size of 2n + 1.

2. Linked List Representation of Binary Tree

We use a double linked list to represent a binary tree. In a double linked list, every node
consists of three fields. First field for storing left child address, second for storing actual
data and third for storing right child address.
In this linked list representation, a node has the following structure...

The above example of the binary tree represented using Linked list representation is
shown as follows...
Binary Tree Traversal in Data Structure
The tree can be defined as a non-linear data structure that stores data in the
form of nodes, and nodes are connected to each other with the help of
edges. Among all the nodes, there is one main node called the root node,
and all other nodes are the children of these nodes.

In any data structure, traversal is an important operation. In the traversal

operation, we walk through the data structure visiting each element of the
data structure at least once. The traversal operation plays a very important
role while doing various other operations on the data structure like some of
the operations are searching, in which we need to visit each element of the
data structure at least once so that we can compare each incoming element
from the data structure to the key that we want to find in the data structure.
So like any other data structure, the tree data also needs to be traversed to
access each element, also known as a node of the tree data structure.

There are different ways of traversing a tree depending upon the order in
which the tree's nodes are visited and the types of data structure used for
 traversing the tree. There are various data structures involved in traversing a
tree, as traversing a tree involves iterating over all nodes in some manner.

As from a given node, there could be more than one way to traverse or visit
the next node of the tree, so it becomes important to store one of the nodes
traverses further and store the rest of the nodes having a possible path for
backtracking the tree if needed. Backtracking is not a linear approach, so we
need different data structures for traversing through the whole tree. The
stack and queue are the major data structure that is used for traversing a
tree.

Traversal is a technique for visiting all of a tree's nodes and printing their
values. Traversing a tree involves iterating over all nodes in some manner.
We always start from the root (head) node since all nodes are connected by
edges (links). As the tree is not a linear data structure, there can be more
than one possible next node from a given node, so some nodes must be
deferred, i.e., stored in some way for later visiting.

Types of Traversal of Binary Tree

There are three types of traversal of a binary tree.
1. Inorder tree traversal
2. Preorder tree traversal
3. Postorder tree traversal

Inorder Tree Traversal

The left subtree is visited first, followed by the root, and finally the right
subtree in this traversal strategy. Always keep in mind that any node might
be a subtree in and of itself. The output of a binary tree traversal in order
produces sorted key values in ascending order.

C Code

Let's write a basic C program for Inorder traversal of the binary search tree.

1. //C Program for Inorder traversal of the binary search tree

2.
3. #include<stdio.h>
4. #include<stdlib.h>
5.
6. struct node
7. {
8. int key;
9. struct node *left;
10. struct node *right;
11. };
12.
13. //return a new node with the given value
14. struct node *getNode(int val)
15. {
16. struct node *newNode;
17.
18. newNode = malloc(sizeof(struct node));
19.
20. newNode->key = val;
21. newNode->left = NULL;
22. newNode->right = NULL;
23.
24. return newNode;
25. }
26.
27. //inserts nodes in the binary search tree
28. struct node *insertNode(struct node *root, int val)
29. {
30. if(root == NULL)
31. return getNode(val);
32.
33. if(root->key < val)
34. root->right = insertNode(root->right,val);
35.
36. if(root->key > val)
37. root->left = insertNode(root->left,val);
38.
39. return root;
40. }
41.
42. //inorder traversal of the binary search tree
43. void inorder(struct node *root)
44. {
45. if(root == NULL)
46. return;
47.
48. //traverse the left subtree
49. inorder(root->left);
50.
51. //visit the root
52. printf("%d ",root->key);
53.
54. //traverse the right subtree
55. inorder(root->right);
56. }
57.
58. int main()
59. {
60. struct node *root = NULL;
61.
62.
63. int data;
64. char ch;
65. /* Do while loop to display various options to select from to decid
e the input */
66. do
67. {
68. printf("\nSelect one of the operations::");
69. printf("\n1. To insert a new node in the Binary Tree");
70. printf("\n2. To display the nodes of the Binary Tree(via Inorder
Traversal).\n");
71.
72. int choice;
73. scanf("%d",&choice);
74. switch (choice)
75. {
76. case 1 :
77. printf("\nEnter the value to be inserted\n");
78. scanf("%d",&data);
79. root = insertNode(root,data);
80. break;
81. case 2 :
82. printf("\nInorder Traversal of the Binary Tree::\n");
83. inorder(root);
84. break;
85. default :
86. printf("Wrong Entry\n");
87. break;
88. }
89.
90. printf("\nDo you want to continue (Type y or n)\n");
91. scanf(" %c",&ch);
92. } while (ch == 'Y'|| ch == 'y');
93.
94. return 0;
95. }

Output:
Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree (via Inorder
Traversal).
1

Enter the value to be inserted

12

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Inorder
Traversal).
1

Enter the value to be inserted

98

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Inorder
Traversal).
1

Enter the value to be inserted

23

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Inorder
Traversal).
1

Enter the value to be inserted

78

Do you want to continue (Type y or n)

y
 Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Inorder
Traversal).
1

Enter the value to be inserted

45

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Inorder
Traversal).
1

Enter the value to be inserted

87

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Inorder
Traversal).
2

Inorder Traversal of the Binary Tree::

12 23 45 78 87 98
Do you want to continue (Type y or n)
n
Preorder Tree Traversal
In this traversal method, the root node is visited first, then the left subtree,
and finally the right subtree.
Code
Let's write a C code for the Preorder traversal of the binary search tree.
1. /*
2. * Program: Preorder traversal of the binary search tree
3. * Language: C
4. */
5.
6. #include<stdio.h>
7. #include<stdlib.h>
8.
9. struct node
10.{
11. int key;
12. struct node *left;
13. struct node *right;
14.};
15.
16.//return a new node with the given value
17. struct node *getNode(int val)
18.{
19. struct node *newNode;
20.
21. newNode = malloc(sizeof(struct node));
22.
23. newNode->key = val;
24. newNode->left = NULL;
25. newNode->right = NULL;
26.
27. return newNode;
28.}
29.
30.//inserts nodes in the binary search tree
31. struct node *insertNode(struct node *root, int val)
32.{
33. if(root == NULL)
34. return getNode(val);
35.
36. if(root->key < val)
37. root->right = insertNode(root->right,val);
38.
39. if(root->key > val)
40. root->left = insertNode(root->left,val);
41.
42. return root;
43. }
44.
45. //preorder traversal of the binary search tree
[Link] preorder(struct node *root)
47. {
48. if(root == NULL)
49. return;
50.
51. //visit the root
52. printf("%d ",root->key);
53.
54. //traverse the left subtree
55. preorder(root->left);
56.
57. //traverse the right subtree
58. preorder(root->right);
59. }
60.
61. int main()
62.{
63. struct node *root = NULL;
64.
65. int data;
66. char ch;
67. /* Do while loop to display various options to select from to decid
e the input */
68. do
69. {
70. printf("\nSelect one of the operations::");
71. printf("\n1. To insert a new node in the Binary Tree");
72. printf("\n2. To display the nodes of the Binary Tree(via Preorder Traversal).\
n");
73.
74. int choice;
75. scanf("%d",&choice);
76. switch (choice)
77. {
78. case 1 :
79. printf("\nEnter the value to be inserted\n");
80. scanf("%d",&data);
81. root = insertNode(root,data);
82. break;
83. case 2 :
84. printf("\nPreorder Traversal of the Binary Tree::\n");
85. preorder(root);
86. break;
87. default :
88. printf("Wrong Entry\n");
89. break;
90. }
91.
92. printf("\nDo you want to continue (Type y or n)\n");
93. scanf(" %c",&ch);
94. } while (ch == 'Y'|| ch == 'y');
95.
96. return 0;
97. }
Output:
Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted

45

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted

53

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted

1

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted

2

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted

97

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted

22

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
2

Preorder Traversal of the Binary Tree::

45 1 2 22 53 97
Do you want to continue (Type y or n)
y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted

76

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted

30

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted

67

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1
 Enter the value to be inserted
4

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
2

Preorder Traversal of the Binary Tree::

45 1 2 22 4 30 53 97 76 67
Do you want to continue (Type y or n)
n
Postorder Tree Traversal
The root node is visited last in this traversal method, hence the name. First,
we traverse the left subtree, then the right subtree, and finally the root node.
Code
Let's write a program for Postorder traversal of the binary search tree.
1. /*
2. * Program: Postorder traversal of the binary search tree
3. * Language: C
4. */
5.
6. #include<stdio.h>
7. #include<stdlib.h>
8.
9. struct node
10.{
11. int key;
12. struct node *left;
13. struct node *right;
14.};
15.
16.//return a new node with the given value
17. struct node *getNode(int val)
18.{
19. struct node *newNode;
20.
21. newNode = malloc(sizeof(struct node));
22.
23. newNode->key = val;
24. newNode->left = NULL;
25. newNode->right = NULL;
26.
27. return newNode;
28.}
29. //inserts nodes in the binary search tree
[Link] node *insertNode(struct node *root, int val)
31. {
32. if(root == NULL)
33. return getNode(val);
34.
35. if(root->key < val)
36. root->right = insertNode(root->right,val);
37.
38. if(root->key > val)
39. root->left = insertNode(root->left,val);
40.
41. return root;
42.}
43.
44.//postorder traversal of the binary search tree
45. void postorder(struct node *root)
46.{
47. if(root == NULL)
48. return;
49.
50. //traverse the left subtree
51. postorder(root->left);
52.
53. //traverse the right subtree
54. postorder(root->right);
55.
56. //visit the root
57. printf("%d ",root->key);
58.}
59. int main()
60.{
61. struct node *root = NULL;
62.
63.
64. int data;
65. char ch;
66. /* Do while loop to display various options to select from to decide the input *
/
67. do
68. {
69. printf("\nSelect one of the operations::");
70. printf("\n1. To insert a new node in the Binary Tree");
71. printf("\n2. To display the nodes of the Binary Tree(via Postorde
r Traversal).\n");
72.
73. int choice;
74. scanf("%d",&choice);
75. switch (choice)
76. {
77. case 1 :
78. printf("\nEnter the value to be inserted\n");
79. scanf("%d",&data);
80. root = insertNode(root,data);
81. break;
82. case 2 :
83. printf("\nPostorder Traversal of the Binary Tree::\n");
84. postorder(root);
85. break;
86. default :
87. printf("Wrong Entry\n");
88. break;
89. }
90.
91. printf("\nDo you want to continue (Type y or n)\n");
92. scanf(" %c",&ch);
93. } while (ch == 'Y'|| ch == 'y');
94.
95. return 0;
96.}
Output:
Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

12

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

31

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
24
Wrong Entry

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

24

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

88

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

67

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

56

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

90

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

44

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

71

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

38
 Do you want to continue (Type y or n)
y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

29

Do you want to continue (Type y or n)

y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
2

Postorder Traversal of the Binary Tree::

29 24 38 44 56 71 67 90 88 31 12
Do you want to continue (Type y or n)
n
We have seen the different C programs to implement inorder, preorder, and postorder
traversal of the nodes of the Binary tree. Now let us write a code to perform all three
types of traversal in a single program.
Code
1. //Binary tree traversal:
2.
3. #include <stdio.h>
4. // #include <conio.h>
5. #include <malloc.h>
6. struct node
7. {
8. struct node *left;
9. int data;
10. struct node *right;
11. };
12.
13. void main()
14.{
15. void insert(struct node **,int);
16. void inorder(struct node *);
17. void postorder(struct node *);
18. void preorder(struct node *);
19.
20. struct node *ptr = NULL;
21. int no,i,num;
22.
23. // ptr = NULL;
24. // ptr->data=0;
25.
26. int data;
27. char ch;
28. /* Do while loop to display various options to select from to decide the input *
/
29. do
30. {
31. printf("\nSelect one of the operations::");
32. printf("\n1. To insert a new node in the Binary Tree");
33. printf("\n2. To display the nodes of the Binary Tree(via Preorder
Traversal).");
34. printf("\n3. To display the nodes of the Binary Tree(via Inorder Traversal).");
35. printf("\n4. To display the nodes of the Binary Tree(via Postorde
r Traversal).\n");
36.
37. int choice;
38. scanf("%d",&choice);
39. switch (choice)
40. {
41. case 1 :
42. printf("\nEnter the value to be inserted\n");
43. scanf("%d",&data);
44. insert(&ptr,data);
45. break;
46. case 2 :
47. printf("\nPreorder Traversal of the Binary Tree::\n");
48. preorder(ptr);
49. break;
50. case 3 :
51. printf("\nInorder Traversal of the Binary Tree::\n");
52. inorder(ptr);
53. break;
54. case 4 :
55. printf("\nPostorder Traversal of the Binary Tree::\n");
56. postorder(ptr);
57. break;
58. default :
59. printf("Wrong Entry\n");
60. break;
61. }
62.
63. printf("\nDo you want to continue (Type y or n)\n");
64. scanf(" %c",&ch);
65. } while (ch == 'Y'|| ch == 'y');
66.
67.
68. // printf("\nProgram for Tree Traversal\n");
69. // printf("Enter the number of nodes to add to the tree.<BR>\n");
70. // scanf("%d",&no);
71.
72. // for(i=0;i<no;i++)
73. // {
74. // printf("Enter the item\n");
75. // scanf("%d",&num);
76. // insert(&ptr,num);
77. // }
78.
79. // //getch();
80. // printf("\nINORDER TRAVERSAL\n");
81. // inorder(ptr);
82.
83. // printf("\nPREORDER TRAVERSAL\n");
84. // preorder(ptr);
85.
86. // printf("\nPOSTORDER TRAVERSAL\n");
87. // postorder(ptr);
88.
89. }
90.
91. void insert(struct node **p,int num)
92.{
93. if((*p)==NULL)
94. {
95. printf("Leaf node created.");
96. (*p)=malloc(sizeof(struct node));
97. (*p)->left = NULL;
98. (*p)->right = NULL;
99. (*p)->data = num;
100. return;
101. }
102. else
103. {
104. if(num==(*p)->data)
105. {
106. printf("\nREPEATED ENTRY ERROR VALUE REJECTED\n");
107. return;
108. }
109. if(num<(*p)->data)
110. {
111. printf("\nDirected to left link.\n");
112. insert(&((*p)->left),num);
113. }
114. else
115. {
116. printf("Directed to right link.\n");
117. insert(&((*p)->right),num);
118. }
119. }
120. return;
121. }
122.
123. void inorder(struct node *p)
124. {
125. if(p!=NULL)
126. {
127. inorder(p->left);
128. printf("%d ",p->data);
129. inorder(p->right);
130. }
131. else
132. return;
133. }
134.
135. void preorder(struct node *p)
136. {
137. if(p!=NULL)
138. {
139. printf("%d ",p->data);
140. preorder(p->left);
141. preorder(p->right);
142. }
143. else
144. return;
145. }
146.
147. void postorder(struct node *p)
148. {
149. if(p!=NULL)
150. {
151. postorder(p->left);
152. postorder(p->right);
153. printf("%d ",p->data);
154. }
155. else
156. return;
157. }
Output:
Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

2
Leaf node created.
Do you want to continue (Type y or n)
y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

5
Directed to right link.
Leaf node created.
Do you want to continue (Type y or n)
y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

7
Directed to right link.
Directed to right link.
Leaf node created.
Do you want to continue (Type y or n)
Y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

9
Directed to right link.
Directed to right link.
Directed to right link.
Leaf node created.
Do you want to continue (Type y or n)
y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

31
Directed to right link.
Directed to right link.
Directed to right link.
Directed to right link.
Leaf node created.
Do you want to continue (Type y or n)
y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted

78
Directed to right link.
Directed to right link.
Directed to right link.
Directed to right link.
Directed to right link.
Leaf node created.
Do you want to continue (Type y or n)
y
Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
2

Preorder Traversal of the Binary Tree::

2 5 7 9 31 78
Do you want to continue (Type y or n)
y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
3

Inorder Traversal of the Binary Tree::

2 5 7 9 31 78
Do you want to continue (Type y or n)
y

Select one of the operations::

1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
4

Postorder Traversal of the Binary Tree::

78 31 9 7 5 2
Do you want to continue (Type y or n)
n