Tree

• Tree is a non-linear data structure which organizes data in hierarchical structure and
this is a recursive definition . OR 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.
• In a tree data structure, if we have N number of nodes then we can have a maximum
of N-1 number of links.
 Tree 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.
 Tree Terminology
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.

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.
 Tree Terminology
Internal Nodes
In a tree data structure, the node which has at least one child is called as INTERNAL
Node. In simple words, an internal node is a node with at least one child.

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'
 Tree Terminology
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).

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'.
 Tree Terminology

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. depth of the root node is '0'.
 Tree Terminology
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.
 Tree Terminology
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 pare
 Binary Tree
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. There are different types of binary trees and they are...

Strictly Binary Tree

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.
 Binary Tree
Complete Binary Tree
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.

Extended Binary Tree :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

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.
 Binary Tree Representations
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.
 Binary Tree Traversals
In-order Traversal (Algorithm) left root right
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.
Pre-order Traversal (Algorithm) root left right
Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.
Post-order Traversal (Algorithm) left right root
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.
 Binary Tree Traversals
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 ( 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.
In-Order Traversal for above example of binary tree is
I-D-J-B-F-A-G-K-C-H
 Binary Tree Traversals
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.
Pre-Order Traversal for above example binary tree is
A-B-D-I-J-F-C-G-K-H
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.
Post-Order Traversal for above example binary tree is
I-J-D-F-B-K-G-H-C–A
 Threaded Binary Trees
• Threaded Binary Tree is also a binary tree in which all left child pointers that are
NULL (in Linked list representation) points to its in-order predecessor, and all right
child pointers that are NULL (in Linked list representation) points to its in-order
successor.
• A. J. Perlis and C. Thornton have proposed new binary tree called "Threaded
Binary Tree", which makes use of NULL pointers to improve its traversal process.
In a threaded binary tree, NULL pointers are replaced by references of other nodes
in the tree. These extra references are called as threads.
• If there is no in-order predecessor or in-order successor, then it points to the root
node
• In-order traversal of above binary tree...
H-D-I-B-E-A-F-J-C-G
Threaded Binary Trees
 Binary Search Tree
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.
 Example
Q . Construct a Binary Search Tree by inserting the following sequence of numbers...
10,12,5,4,20,8,7,15 and 13
A.
 Insertion In Binary Search Tree
Insert function is used to add a new element in a binary search tree at appropriate location. Insert
function is to be designed in such a way that, it must node violate the property of binary search
tree at each value.
• Allocate the memory for tree.
• Set the data part to the value and set the left and right pointer of tree, point to NULL.
• If the item to be inserted, will be the first element of the tree, then the left and right of this
node will point to NULL.
• Else, check if the item is less than the root element of the tree, if this is true, then recursively
perform this operation with the left of the root.
• If this is false, then perform this operation recursively with the right sub-tree of the root.
• Insert (TREE, ITEM)
Step 1: IF TREE = NULL
Allocate memory for TREE
SET TREE -> DATA = ITEM
SET TREE -> LEFT = TREE -> RIGHT = NULL
ELSE
IF ITEM < TREE -> DATA
Insert(TREE -> LEFT, ITEM)
ELSE
Insert(TREE -> RIGHT, ITEM)
[END OF IF]
[END OF IF]
 Deletion In BST
Delete (TREE, ITEM)
Step 1: IF TREE = NULL
Write "item not found in the tree" ELSE IF ITEM < TREE -> DATA
Delete(TREE->LEFT, ITEM)
ELSE IF ITEM > TREE -> DATA
Delete(TREE -> RIGHT, ITEM)
ELSE IF TREE -> LEFT AND TREE -> RIGHT
SET TEMP = findLargestNode(TREE -> LEFT)
SET TREE -> DATA = TEMP -> DATA
Delete(TREE -> LEFT, TEMP -> DATA)
ELSE
SET TEMP = TREE
IF TREE -> LEFT = NULL AND TREE -> RIGHT = NULL
SET TREE = NULL
ELSE IF TREE -> LEFT != NULL
SET TREE = TREE -> LEFT
ELSE
SET TREE = TREE -> RIGHT
[END OF IF]
FREE TEMP
[END OF IF]
Step 2: END
 Deletion In BST
The node to be deleted is a leaf node

The node to be deleted has only one child

 Deletion In BST
The node to be deleted has two children
the node which is to be deleted, is replaced with its in-order successor or predecessor
recursively until the node value (to be deleted) is placed on the leaf of the tree. After
the procedure, replace the node with NULL and free the allocated space.
The in-order traversal of the tree given below.
6, 25, 30, 50, 52, 60, 70, 75.
 Searching In BST
Searching means finding or locating some specific element or node within a data structure.
• Compare the element with the root of the tree.
• If the item is matched then return the location of the node.
• Otherwise check if item is less than the element present on root, if so then move to the left
sub-tree.
• If not, then move to the right sub-tree.
• Repeat this procedure recursively until match found.
• If element is not found then return NULL.
Algorithm:
Search (ROOT, ITEM)
• Step 1: IF ROOT -> DATA = ITEM OR ROOT = NULL
Return ROOT
ELSE
IF ROOT < ROOT -> DATA
Return search(ROOT -> LEFT, ITEM)
ELSE
Return search(ROOT -> RIGHT,ITEM)
[END OF IF]
[END OF IF]
• Step 2: END
 AVL Tree
• AVL Tree is invented by GM Adelson - Velsky and EM Landis in 1962. The tree is
named AVL in honour of its inventors.
• AVL Tree can be defined as height balanced binary search tree in which each node
is associated with a balance factor which is calculated by subtracting the height of
its right sub-tree from that of its left sub-tree.
• Tree is said to be balanced if balance factor of each node is in between -1 to 1,
otherwise, the tree will be unbalanced and need to be balanced.
Balance Factor (k) = height (left(k)) - height (right(k))
 AVL Rotations
We perform rotation in AVL tree only in case if Balance Factor is other than -1, 0, and
1. There are basically four types of rotations which are as follows:
RR Rotation
When BST becomes unbalanced, due to a node is inserted into the right subtree of the
right subtree of A, then we perform RR rotation, RR rotation is an anticlockwise
rotation, which is applied on the edge below a node having balance factor -2

In above example, node A has balance factor -2 because a node C is inserted in the right
subtree of A right subtree. We perform the RR rotation on the edge below A.
 AVL Rotations
LL Rotation
When BST becomes unbalanced, due to a node is inserted into the left subtree of the
left subtree of C, then we perform LL rotation, LL rotation is clockwise rotation, which
is applied on the edge below a node having balance factor 2.

In above example, node C has balance factor 2 because a node A is inserted in the left
subtree of C left subtree. We perform the LL rotation on the edge below A.
 AVL Rotations
RL Rotation
R L rotation= LL rotation + RR rotation, i.e., first LL rotation is performed on subtree
and then RR rotation is performed on full tree, by full tree we mean the first node
from the path of inserted node whose balance factor is other than -1, 0, or 1.

LR Rotation
LR rotation = RR rotation + LL rotation, i.e., first RR rotation is performed on subtree
and then LL rotation is performed on full tree, by full tree we mean the first node from
the path of inserted node whose balance factor is other than -1, 0, or 1.
 Construct an AVL tree having the following elements
H, I, J, B, A, E, C, F, D, G, K, L
Insert H, I, J

The resultant balance tree is:

Insert B, A

The resultant balance tree is:

Insert E

a) We first perform RR rotation on node B

b) We first perform LL rotation on the node

 Insert C, F, D

a) We first perform LL rotation on node E

b) We then perform RR rotation on node B

Insert G

a) We first perform RR rotation on node C

b) We then perform LL rotation on node H

Insert K
The resultant balanced tree after RR rotation is Insert L
 Heap Tree
A heap is a complete binary tree, and the binary tree is a tree in which the node can
have utmost two children.
How can we arrange the nodes in the Tree?
There are two types of the heap:
Min Heap
Max heap
Min Heap: The value of the parent node should be less than or equal to either of its
children.In other words, the min-heap can be defined as, for every node i, the value of
node i is greater than or equal to its parent value except the root node. Mathematically,
it can be defined as: A[Parent(i)] <= A[i]
 Heap Tree
Max Heap: The value of the parent node is greater than or equal to its
children. Or In other words, the max heap can be defined as for every
node i; the value of node i is less than or equal to its parent value except
the root node. Mathematically, it can be defined as:
A[Parent(i)] >= A[i]
 Insertion in the Heap tree
To create the max heap tree using:
44, 33, 77, 11, 55, 88, 66
 Insertion in the Heap tree
Insertion Operation is performed to insert an element in the heap tree.
Step-01:
Insert the new element as a next leaf node from left to right.
Step-02:
Ensure that the tree remains a max heap.
• Check that every non-leaf node contains a greater or equal value
element than its child nodes.
• If there exists any node that does not satisfies the ordering property of
max heap, swap the elements.
• Start checking from a non-leaf node with the highest index (bottom to
top and right to left).
 Deletion in Heap Tree
When it comes to deleting a node from the heap tree, following two cases are possible-
Case-01: Deletion Of Last Node-
Just remove / disconnect the last leaf node from the heap tree.
Case-02: Deletion Of Some Other Node-
Deleting a node other than the last node disturbs the heap properties.
The steps involved in deleting such a node are-
Step-01:
Delete the desired element from the heap tree.
Pluck the last node and put in place of the deleted node.
Step-02:
Ensure that the tree remains a max heap.
• Check that every non-leaf node contains a greater or equal value element than its
child nodes.
• If there exists any node that does not satisfies the ordering property of max heap,
swap the elements.
• Start checking from a non-leaf node with the highest index (bottom to top and right
to left).
 Deletion in Heap Tree
Consider the following max heap-
50, 30, 20, 15, 10, 8, 16
Delete a node with value 50.
Step-02:

We delete the element 50 which is present at root node.

We pluck the last node 16 and put in place of the deleted node.
The resulting tree is-
 Deletion in Heap Tree
Step-03:
We ensure that the tree is a max heap.
Node 16 contains greater element in its left child node.
So, we swap node 16 and node 30.

This is the required max heap after deleting the node with value 50.
THANK YOU