Binary Trees
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Agenda
• Introduction to Binary Tree
• Why Binary Tree?
• Types of Binary Tree
• Applications of Binary Tree
• Pseudocode for Binary Tree
• Preorder Traversal
• Inorder Traversal
• Postorder Traversal
• Binary Search Tree
• Operations on BST
• Pseudocode for BST DO NOT WRITE ANYTHING
• Summary HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Introduction to Binary Tree
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Introduction to Binary Tree
• A tree where a node can have 0 to maximum 2 children is called a Binary Tree.
• Binary Tree does not store the data in sequential memory locations.
• Binary Tree is a non-linear data structure where the data is stored in a hierarchical format.
• Data is stored at multiple levels.
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Introduction to Binary Tree
Important Terminologies associated with the Binary tree are as below:-
LEVEL 0
ROOT NODE A
EDGE(LINK)
LEVEL 1
PARENT NODE B E
LEVEL 2
CHILD NODE C D F G
SIBLINGS
DO NOT WRITE ANYTHING
LEAF NODE HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Why Binary Tree?
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Why Binary Tree?
Tree Binary
Tree
• Tree can have any number of nodes as a child.
• A binary tree can have maximum of 2 nodes as child nodes. DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Why Binary Tree?
Advantages
• The search() operation becomes faster when we use Binary Tree.
• The insert() and delete() operations cost can be reduced significantly.
• Binary Tree is used in various applications.
• It provides a more convenient method for moving and holding data.
• Solves the problem when we want to store the information in a hierarchical form.
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Types of Binary Tree
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Types of Binary Tree
• Full Binary Tree - it’s a Binary Tree where in every node has either 0 or 2 children.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Types of Binary Tree
• Complete Binary Tree - where all the levels are completely filled with nodes except the level which
is at last and in the last level, all the nodes tend to be on the left side as much as possible.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Types of Binary Tree
• Perfect Binary Tree - is a Binary Tree where all the internal nodes have 2 child nodes and all the leaf
nodes must be at the same level.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Applications of Binary Trees
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Applications of Binary Trees
• Binary trees can also be used for classification purposes.
• Decision Tree – is a supervised machine learning algorithm which will use a binary tree, for the
decision – making process.
• Expression Evaluation.
• Sorting.
• Data Compression.
• Routing Tables.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Pseudocode for Binary Tree
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Pseudocode Binary Tree
• Pseudocode
struct node *NodeNew( int data) void insert(struct node *r, intdata)
{ {
struct node *Node struct node *tmp
Node.data = data if(tmp.left == NULL){
Node.left = NULL temp.left = Nodenew(data)
Node.right = NULL if(tmp.right == NULL){
} temp.right = Nodenew(data)
}
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Pseudocode Binary Tree
• Pseudocode
void DelBT(struct node * Btree) {
if (Btree) {
DelBT(Btree->left)
DelBT(Btree->right)
free(Btree);
}
}
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Preorder Traversal
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Preorder Traversal
• It is a technique of tree traversing in which we visit the root node first.
• Following steps are involved in Preorder traversal:
1. Visit the root.
2. Visit all the nodes on the left side
3. Visit all the nodes on the right side
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Preorder Traversal
15
12 20
10 14 18 25
15, 12, 10, 14, 20, 18, 25
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Inorder Traversal
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Inorder Traversal
• It is a technique of tree traversing in which we visit the root node after visiting the left side of the
tree and before the traversing the right side of the tree.
• Following steps are involved in Inorder traversal:
1. Visit all the nodes on the left side.
2. Visit the root.
3. Visit all the nodes on the right side.
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Inorder Traversal
15
12 20
10 14 18 25
10, 12, 14, 15, 18, 20, 25
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Postorder Traversal
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Postorder Traversal
• It is a technique of tree traversing in which we visit the root node at last after visiting all the nodes
on the left side and all the nodes on the right side.
• Following steps are involved in postorder traversal:
1. Visit all the nodes on the left side.
2. Visit all the nodes on the right side.
3. Visit the root.
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Postorder Traversal
15
12 20
10 14 18 25
10, 14, 12, 18, 25, 20, 15 DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Binary Search Tree
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Binary Search Tree
• Binary search tree is a special type of tree in which every node in the tree can have a maximum of 2
child nodes.
• In this type of tree data on the left side of every node must be small and data on the right- hand
side of every node must be bigger than data in the root node.
• We use a binary search tree when our main operation is frequent searching.
• This is also called an ordered binary tree.
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Binary Search Tree
15
12 20
10 14 18 25
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Operations on BST
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Operations on BST
• Insert
• Delete
• Search
• Traversals such as Preorder, Inorder, and Postorder
• Time Complexity – O(log N)
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Pseudocode for BST
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Pseudocode Binary Search Tree
• Pseudocode
struct node *NodeNew( int data)
{
struct node *Node
Node.data = data
Node.left = NULL
Node.right = NULL
}
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Pseudocode Binary Search Tree
struct Node* InsertBST(struct Node* Node, int data)
{
if (Node == Null) return Nodenew(data)
if ( data < Node.data)
Node.left = InsertBST( Node.left, data)
if ( data > Node.data)
Node.right = InsertBST( Node.right, data)
return
}
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Pseudocode Binary Search Tree
struct Node* search( struct Node* Root, int data)
{
if (Root == Null or Root.data == data)
return
if (Root.data < data)
return search( Root.right, data)
if (Root.data > data )
return search( Root.left , data)
}
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Summary
• We discussed an introduction for a Binary Tree, how it looks and different terminologies associated
with it.
• We looked at different uses of a Binary Tree and also the different types such as Full, Complete and
Perfect Binary Trees.
• We learnt the different applications of a Binary Tree and also the Pseudocode was discussed.
• We discussed different types of traversal methods such as pre-order, in-order and post-order.
• We discussed Binary Search Tree, its uses and also the Pseudocode for a Binary Search Tree.
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
