Tree – Terminology

In linear data structure data is organized in sequential order and in non-linear data structure data is

organized in random order. A tree is a very popular non-linear data structure used in a wide range of
applications. A tree data structure can be defined as follows...

Tree is a non-linear data structure which organizes data in hierarchical structure and this is a

recursive definition.

A tree data structure can also be defined as follows...

Tree data structure is a collection of data (Node) which is organized in hierarchical structure

recursively

In tree data structure, every individual element is called as Node. Node in a tree data structure stores

the actual data of that particular element and link to next element in hierarchical structure.

In a tree data structure, if we have N number of nodes then we can have a maximum of N-1 number of
links.

Example
Terminology

In a tree data structure, we use the following terminology...

1. Root

In a tree data structure, the first node is called as Root Node. Every tree must have a root node. We can

say that the root node is the origin of the tree data structure. In any tree, there must be only one root
node. We never have multiple root nodes in a tree.

2. Edge

In a tree data structure, the connecting link between any two nodes is called as EDGE. In a tree with 'N'
number of nodes there will be a maximum of 'N-1' number of edges.
3. Parent

In a tree data structure, the node which is a predecessor of any node is called as PARENT NODE. In

simple words, the node which has a branch from it to any other node is called a parent node. Parent
node can also be defined as "The node which has child / children".

4. Child

In a tree data structure, the node which is descendant of any node is called as CHILD Node. In simple

words, the node which has a link from its parent node is called as child node. In a tree, any parent node
can have any number of child nodes. In a tree, all the nodes except root are child nodes.
5. Siblings

In a tree data structure, nodes which belong to same Parent are called as SIBLINGS. In simple words,
the nodes with the same parent are called Sibling nodes.

6. Leaf
In a tree data structure, the node which does not have a child is called as LEAF Node. In simple words,

a leaf is a node with no child.

In a tree data structure, the leaf nodes are also called as External Nodes. External node is also a node
with no child. In a tree, leaf node is also called as 'Terminal' node.
7. Internal Nodes
In a tree data structure, the node which has atleast one child is called as INTERNAL Node. In simple

words, an internal node is a node with atleast one child.

In a tree data structure, nodes other than leaf nodes are called as Internal Nodes. The root node is also

said to be Internal Node if the tree has more than one node. Internal nodes are also called as 'Non-
Terminal' nodes.

8. Degree
In a tree data structure, the total number of children of a node is called as DEGREE of that Node. In

simple words, the Degree of a node is total number of children it has. The highest degree of a node

among all the nodes in a tree is called as 'Degree of Tree'

9. Level
In a tree data structure, the root node is said to be at Level 0 and the children of root node are at Level 1

and the children of the nodes which are at Level 1 will be at Level 2 and so on... In simple words, in a

tree each step from top to bottom is called as a Level and the Level count starts with '0' and

incremented by one at each level (Step).

10. Height
In a tree data structure, the total number of edges from leaf node to a particular node in the longest path

is called as HEIGHT of that Node. In a tree, height of the root node is said to be height of the tree. In

a tree, height of all leaf nodes is '0'.

11. Depth
In a tree data structure, the total number of egdes from root node to a particular node is called

as DEPTH of that Node. In a tree, the total number of edges from root node to a leaf node in the

longest path is said to be Depth of the tree. In simple words, the highest depth of any leaf node in a

tree is said to be depth of that tree. In a tree, depth of the root node is '0'.

12. Path
In a tree data structure, the sequence of Nodes and Edges from one node to another node is called

as PATH between that two Nodes. Length of a Path is total number of nodes in that path. In below

example the path A - B - E - J has length 4.

13. Sub Tree

In a tree data structure, each child from a node forms a subtree recursively. Every child node will form
a subtree on its parent node.

Tree Representations
A tree data structure can be represented in two methods. Those methods are as follows...

1. List Representation

2. Left Child - Right Sibling Representation

Consider the following tree...
1. List Representation

In this representation, we use two types of nodes one for representing the node with data called 'data

node' and another for representing only references called 'reference node'. We start with a 'data node'

from the root node in the tree. Then it is linked to an internal node through a 'reference node' which is
further linked to any other node directly. This process repeats for all the nodes in the tree.

The above example tree can be represented using List representation as follows...

2. Left Child - Right Sibling Representation

In this representation, we use a list with one type of node which consists of three fields namely Data

field, Left child reference field and Right sibling reference field. Data field stores the actual value of a

node, left reference field stores the address of the left child and right reference field stores the address
of the right sibling node. Graphical representation of that node is as follows...

In this representation, every node's data field stores the actual value of that node. If that node has left a

child, then left reference field stores the address of that left child node otherwise stores NULL. If that

node has the right sibling, then right reference field stores the address of right sibling node otherwise
stores NULL.
The above example tree can be represented using Left Child - Right Sibling representation as follows...

Binary Tree Data structure

• In a normal tree, every node can have any number of children. A binary tree is a special type of
tree data structure in which every node can have a maximum of 2 children. One is known as a
left child and the other is known as right child.

• A tree in which every node can have a maximum of two children is called Binary Tree.

• In a binary tree, every node can have either 0 children or 1 child or 2 children but not more than
2 children.

Example

There are different types of binary trees and they are

1. Strictly Binary Tree

• In a binary tree, every node can have a maximum of two children. But in strictly binary tree,
every node should have exactly two children or none. That means every internal node must have
exactly two children. A strictly Binary Tree can be defined as follows...
 • A binary tree in which every node has either two or zero number of children is called
Strictly Binary Tree

• Strictly binary tree is also called as Full Binary Tree or Proper Binary Tree or 2-Tree

2. Complete Binary Tree

• In a binary tree, every node can have a maximum of two children. But in strictly binary tree,
every node should have exactly two children or none and in complete binary tree all the nodes
must have exactly two children and at every level of complete binary tree there must be
2level number of nodes. For example at level 2 there must be 22 = 4 nodes and at level 3 there
must be 23 = 8 nodes.

• A binary tree in which every internal node has exactly two children and all leaf nodes are
at same level is called Complete Binary Tree.

• Complete binary tree is also called as Perfect Binary Tree

3. Extended Binary Tree

• A binary tree can be converted into Full Binary tree by adding dummy nodes to existing nodes
wherever required.

• The full binary tree obtained by adding dummy nodes to a binary tree is called as
Extended Binary Tree.

Binary Tree Representations

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

• Array Representation

• 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 Traversals

• When we wanted to display a binary tree, we need to follow some order in which all the nodes
of that binary tree must be displayed. In any binary tree, displaying order of nodes depends on
the traversal method.
 • Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal.

• There are three types of binary tree traversals.

• In - Order Traversal

• Pre - Order Traversal

• Post - Order Traversal

1. In - Order Traversal ( leftChild - root - rightChild )

• In In-Order traversal, the root node is visited between the left child and right child.

In this traversal,

• the left child node is visited first,

• then the root node is visited and

• Later we go for visiting the right child node.

This in-order traversal is applicable for every root node of all subtrees in the tree. This is performed
recursively for all nodes in the tree.

• 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 in-order
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 root node.

• Step 3 − Recursively traverse right subtree.

2. Pre - Order Traversal ( root - leftChild - rightChild )

• In Pre-Order traversal, the root node is visited before the left child and right child nodes.

In this traversal,

• the root node is visited first,

• then its left child and

• later its right child.

This pre-order traversal is applicable for every root node of all subtrees in the tree.

• 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 root node.

• Step 2 − Recursively traverse left subtree.

• Step 3 − Recursively traverse right subtree.

3. Post - Order Traversal ( leftChild - rightChild - root )

In Post-Order traversal, the root node is visited after left child and right child. In this traversal, left child
node is visited first, then its right child and then its root node. This is recursively performed until the
right most node is visited.
 • We start from A, and following pre-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 right subtree.

• Step 3 − Visit root node.

Binary Search Tree

• In a binary tree, every node can have a maximum of two children but there is no need to
maintain the order of nodes basing on their values. In a binary tree, the elements are arranged in
the order they arrive at the tree from top to bottom and left to right.

• A binary tree has the following time complexities...

• Search Operation - O(n)

• Insertion Operation - O(1)

• Deletion Operation - O(n)

• To enhance the performance of binary tree, we use a special type of binary tree known
as Binary Search Tree. Binary search tree mainly focuses on the search operation in a binary
tree. Binary search tree can be defined as follows...

• Binary Search Tree is a binary tree in which every node contains only smaller values in its
left subtree and only larger values in its right subtree.

• In a binary search tree, all the nodes in the left subtree of any node contains smaller values and
all the nodes in the right subtree of any node contains larger values as shown in the following
figure...
Example
The following tree is a Binary Search Tree. In this tree, left subtree of every node contains nodes with
smaller values and right subtree of every node contains larger values.

Operations on a Binary Search Tree

• The following operations are performed on a binary search tree...

• Search

• Insertion

• Deletion

Search Operation in BST

• In a binary search tree, the search operation is performed with

O(log n) time complexity. The search operation is performed as follows...

Step 1 - Read the search element from the user.

Step 2 - Compare the search element with the value of root node in the tree.

Step 3 - If both are matched, then display "Given node is found!!!" and terminate the
function
 Step 4 - If both are not matched, then check whether search element is smaller or larger than
that node value.

Step 5 - If search element is smaller, then continue the search process in left subtree.

Step 6- If search element is larger, then continue the search process in right subtree.

Step 7 - Repeat the same until we find the exact element or until the search element is
compared with the leaf node

Step 8 - If we reach to the node having the value equal to the search value then display
"Element is found" and terminate the function.

Step 9 - If we reach to the leaf node and if it is also not matched with the search element,
then display "Element is not found" and terminate the function.

Insertion Operation in BST

• In a binary search tree, the insertion operation is performed with O(log n) time complexity. In
binary search tree, new node is always inserted as a leaf node. The insertion operation is
performed as follows...

Step 1 - Create a newNode with given value and set its left and right to NULL.

Step 2 - Check whether tree is Empty.

Step 3 - If the tree is Empty, then set root to newNode.

Step 4 - If the tree is Not Empty, then check whether the value of newNode
is smaller or larger than the node (here it is root node).

Step 5 - If newNode is smaller than or equal to the node then move to its left child. If
newNode is larger than the node then move to its right child.

Step 6- Repeat the above steps until we reach to the leaf node (i.e., reaches to NULL).

Step 7 - After reaching the leaf node, insert the newNode as left child if the newNode
is smaller or equal to that leaf node or else insert it as right child.

Deletion Operation in BST

• In a binary search tree, the deletion operation is performed with O(log n) time complexity.
Deleting a node from Binary search tree includes following three cases...

Case 1: Deleting a Leaf node (A node with no children)

Case 2: Deleting a node with one child

Case 3: Deleting a node with two children

Case 1: Deleting a leaf node

• We use the following steps to delete a leaf node from BST...

Step 1 - Find the node to be deleted using search operation

Step 2 - Delete the node using free function (If it is a leaf) and terminate the function.

Case 2: Deleting a node with one child

• We use the following steps to delete a node with one child from BST...

Step 1 - Find the node to be deleted using search operation

Step 2 - If it has only one child then create a link between its parent node and child node.

Step 3 - Delete the node using free function and terminate the function.

Case 3: Deleting a node with two children

• We use the following steps to delete a node with two children from BST...

Step 1 - Find the node to be deleted using search operation

Step 2 - If it has two children, then find the largest node in its left subtree (OR)
the smallest node in its right subtree.

Step 3 - Swap both deleting node and node which is found in the above step.

Step 4 - Then check whether deleting node came to case 1 or case 2 or else goto step 2

Step 5 - If it comes to case 1, then delete using case 1 logic.

Step 6- If it comes to case 2, then delete using case 2 logic.

Step 7 - Repeat the same process until the node is deleted from the tree.

Example

• Construct a Binary Search Tree by inserting the following sequence of numbers...

10,12,5,4,20,8,7,15 and 13

• Above elements are inserted into a Binary Search Tree as follows...

Another Example:
Deletion
Searching
Height Balanced Tree

• Height-balanced binary trees are a type of binary tree where the difference in height between the
left and right subtrees of any node is no more than 1.

• This property ensures that the tree maintains a logarithmic height with respect to the number of
nodes, making operations like search, insertion, and deletion efficient.

• Common examples of height-balanced trees include AVL trees and Red-Black trees.

Examples of Height-Balanced Trees

AVL Trees:

• A self-balancing binary search tree that maintains balance through rotations during insertion and
deletion.

Red-Black Trees:

• Another self-balancing binary search tree that uses node coloring (red or black) to ensure
balance.

B-Trees:

• A tree structure used in databases and file systems to store large amounts of data efficiently.

AVL Tree Data structure

• AVL tree is a height-balanced binary search tree. That means, an AVL tree is also a binary
search tree but it is a balanced tree.

• A binary tree is said to be balanced if, the difference between the heights of left and right
subtrees of every node in the tree is either -1, 0 or +1.

• In other words, a binary tree is said to be balanced if the height of left and right children of
every node differ by either -1, 0 or +1.

• In an AVL tree, every node maintains an extra information known as balance factor. The AVL
tree was introduced in the year 1962 by G.M. Adelson-Velsky and E.M. Landis.

An AVL tree is defined as follows...

• An AVL tree is a balanced binary search tree. In an AVL tree, balance factor of every
node is either -1, 0 or +1.

• Balance factor of a node is the difference between the heights of the left and right subtrees of
that node.
 • The balance factor of a node is calculated either height of left subtree - height of right
subtree (OR) height of right subtree - height of left subtree. In the following explanation, we
calculate as follows...

• Balance factor = height Of Left Subtree – height Of Right Subtree

• Every AVL Tree is a binary search tree but every Binary Search Tree need not be AVL tree.

AVL Tree Rotations

• In AVL tree, after performing operations like insertion and deletion we need to check
the balance factor of every node in the tree. If every node satisfies the balance factor condition
then we conclude the operation otherwise we must make it balanced. Whenever the tree
becomes imbalanced due to any operation we use rotation operations to make the tree balanced.

Rotation operations are used to make the tree balanced.

• Rotation is the process of moving nodes either to left or to right to make the tree balanced.

There are four rotations and they are classified into two types.

Single Left Rotation (LL Rotation)

• In LL Rotation, every node moves one position to left from the current position.

• To understand LL Rotation, let us consider the following insertion operation in AVL Tree.
Single Right Rotation (RR Rotation)

• In RR Rotation, every node moves one position to right from the current position.

• To understand RR Rotation, let us consider the following insertion operation in AVL Tree.

Left Right Rotation (LR Rotation)

• The LR Rotation is a sequence of single left rotation followed by a single right rotation.

• In LR Rotation, at first, every node moves one position to the left and one position to right from
the current position.

• To understand LR Rotation, let us consider the following insertion operation in AVL Tree.

Right Left Rotation (RL Rotation)

• The RL Rotation is sequence of single right rotation followed by single left rotation.

• In RL Rotation, at first every node moves one position to right and one position to left from the
current position.

• To understand RL Rotation, let us consider the following insertion operation in AVL Tree.
Operations on an AVL Tree

The following operations are performed on AVL tree…

• Search

• Insertion

• Deletion

Search Operation in AVL Tree

• In an AVL tree, the search operation is performed with O(log n) time complexity. The search
operation in the AVL tree is similar to the search operation in a Binary search tree. We use the
following steps to search an element in AVL tree...

Step 1 - Read the search element from the user.

Step 2 - Compare the search element with the value of root node in the tree.

Step 3 - If both are matched, then display "Given node is found!!!" and terminate the function

Step 4 - If both are not matched, then check whether search element is smaller or larger than
that node value.

Step 5 - If search element is smaller, then continue the search process in left subtree.

Step 6 - If search element is larger, then continue the search process in right subtree.

Step 7 - Repeat the same until we find the exact element or until the search element is compared
with the leaf node.

Step 8 - If we reach to the node having the value equal to the search value, then display
"Element is found" and terminate the function.

Step 9 - If we reach to the leaf node and if it is also not matched with the search element, then
display "Element is not found" and terminate the function.
Insertion Operation in AVL Tree

In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL
Tree, a new node is always inserted as a leaf node. The insertion operation is performed as follows...

Step 1 - Insert the new element into the tree using Binary Search Tree insertion logic.

Step 2 - After insertion, check the Balance Factor of every node.

Step 3 - If the Balance Factor of every node is 0 or 1 or -1 then go for next operation.

Step 4 - If the Balance Factor of any node is other than 0 or 1 or -1 then that tree is said to be
imbalanced. In this case, perform suitable Rotation to make it balanced and go for next
operation.
Deletion Operation in AVL Tree

The deletion operation in AVL Tree is similar to deletion operation in BST. But after every deletion
operation, we need to check with the Balance Factor condition. If the tree is balanced after deletion go
for next operation otherwise perform suitable rotation to make the tree Balanced.
Heap Tree Data structure

• Heap Tree data structure is a specialized binary tree-based data structure.

• Heap Tree is a binary tree with special characteristics. In a heap data structure, nodes are
arranged based on their values.

• A heap tree data structure some times also called as Binary Heap.

• There are two types of heap data structures and they are as follows...

1. Max Heap

2. Min Heap

Every heap tree data structure has the following properties...

• Property #1 (Ordering): Nodes must be arranged in an order according to their values based
on Max heap or Min heap.

• Property #2 (Structural): All levels in a heap must be full except the last level and all nodes
must be filled from left to right strictly.
Max Heap
• Max heap is defined as follows...
• Max heap is a specialized complete binary tree in which every parent node contains
greater or equal value than its child n
Min Heap
• Min heap is defined as follows...
• Min heap is a specialized complete binary tree in which every parent node contains lesser
or equal value than its child nodes.

Above tree is satisfying both Ordering property and Structural property according to the Max Heap data
structure.
Operations on Max Heap
The following operations are performed on a Max heap data structure...
1. Finding Maximum
2. Insertion
3. Deletion
Finding Maximum Value Operation in Max Heap
• Finding the node which has maximum value in a max heap is very simple.
• In a max heap, the root node has the maximum value than all other nodes.
• So, directly we can display root node value as the maximum value in max heap.
Insertion Operation in Max Heap
Insertion Operation in max heap is performed as follows...
 • Step 1 - Insert the newNode as last leaf from left to right.
• Step 2 - Compare newNode value with its Parent node.
• Step 3 - If newNode value is greater than its parent, then swap both of them.
• Step 4 - Repeat step 2 and step 3 until newNode value is less than its parent node (or) newNode
reaches to root.
Example
Consider the below max heap. Insert a new node with value 85.
Deletion Operation in Max Heap

• In a max heap, deleting the last node is very simple as it does not disturb max heap properties.

• Deleting root node from a max heap is little difficult as it disturbs the max heap properties.

We use the following steps to delete the root node from a max heap...

Step 1 - Swap the root node with last node in max heap

Step 2 - Delete last node.

Step 3 - Now, compare root value with its left child value.

Step 4 - If root value is smaller than its left child, then compare left child with its right sibling.
Else goto Step 6

Step 5 - If left child value is larger than its right sibling, then swap root with left
child otherwise swap root with its right child.

Step 6 - If root value is larger than its left child, then compare root value with its right
child value.

Step 7 - If root value is smaller than its right child, then swap root with right
child otherwise stop the process.

Step 8 - Repeat the same until root node fixes at its exact position.
• Here, node with value 75 is larger than its left child (15) and it does not have right child. So we
stop the process.
Finally, max heap after deleting root node (90) is as follows...

Heap Sort

• Heap sort is one of the sorting algorithms used to arrange a list of elements in
order.

• Heap sort algorithm uses one of the tree concepts called Heap Tree.

• In this sorting algorithm, we use Max Heap to arrange list of elements in

Ascending order and Min Heap to arrange list elements in Descending order.

Step by Step Process

• The Heap sort algorithm to arrange a list of elements in ascending order is

performed using following steps...

Step 1 - Construct a Binary Tree with given list of Elements.

Step 2 - Transform the Binary Tree into Max Heap.

Step 3 - Delete the root element from Max Heap using Heapify method.

Step 4 - Put the deleted element into the Sorted list.

Step 5 - Repeat the same until Max Heap becomes empty.

Step 6 - Display the sorted list.

Example