PREVIOUS SESSION
STACKS AND QUEUES
PROBLEM SOLVING ON STACKS AND QUEUES
INTRODUCTION
HOW TO REACH THE NUMBER 7 WHEN IT IS AN ARRAY DATASTRUCTURE ?
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
INTRODUCTION
HOW TO REACH THE NUMBER 7 WHEN IT IS AN ARRAY DATASTRUCTURE ?
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
INTRODUCTION
HOW TO REACH THE NUMBER 7 WHEN IT IS AN ARRAY DATASTRUCTURE ?
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
INTRODUCTION
HOW TO REACH THE NUMBER 7 WHEN IT IS AN ARRAY DATASTRUCTURE ?
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
INTRODUCTION
HOW TO REACH THE NUMBER 7 WHEN IT IS AN ARRAY DATASTRUCTURE ?
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
INTRODUCTION
HOW TO REACH THE NUMBER 7 WHEN IT IS AN ARRAY DATASTRUCTURE ?
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
INTRODUCTION
HOW TO REACH THE NUMBER 7 WHEN IT IS AN ARRAY DATASTRUCTURE ?
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
INTRODUCTION
HOW TO REACH THE NUMBER 7 WHEN IT IS AN ARRAY DATASTRUCTURE ?
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
INTRODUCTION
HOW TO REACH THE NUMBER 7 WHEN IT IS AN ARRAY DATASTRUCTURE ?
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
CAN I MAKE USE OF ANY DATASTRUCTURE WHICH REACHES THE NUMBER 7 IN LESS TIME ?
INTRODUCTION
YES, BY USING
HIERARCHICAL DATA
STRUCTURE
TREES
INTRODUCTION
YES, BY USING
HIERARCHICAL DATA
STRUCTURE
TREES
INTRODUCTION
HOW TO REACH THE NUMBER 7 WHEN IT IS TREE DATA STRUCTURE ?
INTRODUCTION
HOW TO REACH THE NUMBER 7 WHEN IT IS TREE DATA STRUCTURE ?
INTRODUCTION
HOW TO REACH THE NUMBER 7 WHEN IT IS TREE DATA STRUCTURE ?
AGENDA
TREE TERMINOLOGIES
APPLICATIONS OF TREE
BINARY TREE AND ITS
TRAVERSALS
TREE TERMINOLOGIES
ROOT
NODE
SIBLINGS
EDGE
PARENT NODE / INTERNAL NODE
CHILD OF 2
LEAF NODES /
EXTERNAL NODES
GUESS THE NODE
NODE DEGREE - ?
LEVEL - ?
DEPTH - ?
HEIGHT - ?
TREE TERMINOLOGIES
LEVEL 0
HEIGHT = 2 DEPTH = 1
LEVEL
1
DEPTH = 2
NODE DEGREE = 3
LEVEL 2
HEIGHT = 0 NODE DEGREE = 0
LEVEL 3
HEIGHT OF TREE = 3
APPLICATIONS OF TREES
Implementing the hierarchical structures in
computer systems like directory and
filesystem
Decision making in game application
Implementing the navigation structure of a
website
Parsing of expressions and statements in
programming language compilers
Path-finding algorithm to implement in AI,
robotics and video games applications
BINARY TREE
A tree whose elements have at most 2 children is called a binary tree.
BINARY TREE
A tree whose elements have at most 2 children is called a binary tree.
TYPES OF BINARY TREE :
• Full Binary Tree
• Complete Binary Tree
• Perfect Binary Tree
• Skewed Binary Tree
• Degenerate or Pathological Tree
• Balanced Binary Tree
TYPES OF BINARY TREE
Full Binary Tree Perfect Binary Tree Complete Binary Tree
TYPES OF BINARY TREE
Degenerate or Skewed Binary Tree Balanced Binary Tree
pathological Tree
REPRESENTATION OF BINARY TREE
BINARY TREE USING ARRAY :
BINARY TREE
ARRAY LINKED LIST
REPRESENTATION OF BINARY TREE
BINARY TREE USING ARRAY :
0 1 2 3 4
1
1 2 3 4 5
PARENT
REPRESENTATION OF BINARY TREE
BINARY TREE USING ARRAY :
LEFTCHILD = (2*i)+1
0 1 2 3 4
1
1 2 3 4 5
PARENT LEFTCHILD 2
REPRESENTATION OF BINARY TREE
BINARY TREE USING ARRAY :
LEFTCHILD = (2*i)+1
RIGHTCHILD = (2*i)+2
0 1 2 3 4
1
1 2 3 4 5
PARENT LEFTCHILDRIGHTCHILD 2 3
REPRESENTATION OF BINARY TREE
BINARY TREE USING ARRAY :
0 1 2 3 4
1
1 2 3 4 5
PARENT LEFTCHILDRIGHTCHILD 2 3
PARENT 4
REPRESENTATION OF BINARY TREE
BINARY TREE USING ARRAY :
LEFTCHILD = (2*i)+1
0 1 2 3 4
1
1 2 3 4 5
PARENT LEFTCHILDRIGHTCHILD 2 3
PARENT 4 5
LEFTCHILD
REPRESENTATION OF BINARY TREE
BINARY TREE USING ARRAY :
LEFTCHILD = (2*i)+1
RIGHTCHILD = (2*i)+2
0 1 2 3 4
1
1 2 3 4 5
PARENT LEFTCHILDRIGHTCHILD 2 3
PARENT 4 5
LEFTCHILDRIGHTCHILD
REPRESENTATION OF BINARY TREE
BINARY TREE USING LINKED LIST :
BINARY TREE
ARRAY LINKED LIST
*left data *right
REPRESENTATION OF BINARY TREE
BINARY TREE USING LINKED LIST :
*left 1 *righ
t
*left data *right
REPRESENTATION OF BINARY TREE
BINARY TREE USING LINKED LIST :
*left 1 *righ
t
*left 2 *righ
t
*left data *right
REPRESENTATION OF BINARY TREE
BINARY TREE USING LINKED LIST :
*left 1 *righ
t
*left 2 *righ *left 3 *righ
t t
*left data *right
REPRESENTATION OF BINARY TREE
BINARY TREE USING LINKED LIST :
*left 1 *righ
t
*left 2 *righ *left 3 *righ
t t
*left 4 *righ *left data *right
t
REPRESENTATION OF BINARY TREE
BINARY TREE USING LINKED LIST :
*left 1 *righ
t
*left 2 *righ *left 3 *righ
t t
*left 4 *righ *left 5 *righ *left data *right
t t
LET’S CREATE A BINARY TREE
TRAVERSING THROUGH BINARY TREE
Tree Traversal
Inorder Preorder Postorder Levelorder
TRAVERSING THROUGH BINARY TREE
INORDER TRAVERSAL : LEFT ROOT RIGHT
1
9
2
5 6
TRAVERSING THROUGH BINARY TREE
INORDER TRAVERSAL : LEFT ROOT RIGHT
WITH RECURSION : 1
1. Traverse the left subtree in Inorder
2. Visit the root
3. Traverse the right subtree in Inorder 1
9
2
5 6
TRAVERSING THROUGH BINARY TREE
INORDER TRAVERSAL : LEFT ROOT RIGHT
12 9
5 6
TRAVERSING THROUGH BINARY TREE
POSTORDER TRAVERSAL : LEFT RIGHT ROOT
12 9
5 6
TRAVERSING THROUGH BINARY TREE
POSTORDER TRAVERSAL : LEFT RIGHT ROOT
WITH RECURSION : 1
1. Traverse the left subtree in Postorder
2. Traverse the right subtree in Postorder
3. Visit the root
12 9
5 6
TRAVERSING THROUGH BINARY TREE
POSTORDER TRAVERSAL : LEFT RIGHT ROOT
12 9
5 6
TRAVERSING THROUGH BINARY TREE
PREORDER TRAVERSAL : ROOT LEFT RIGHT
12 9
5 6
TRAVERSING THROUGH BINARY TREE
PREORDER TRAVERSAL : ROOT LEFT RIGHT
WITH RECURSION : 1
1. Visit the root
2. Traverse the left subtree in Preorder
3. Traverse the right subtree in Preorder
12 9
5 6
TRAVERSING THROUGH BINARY TREE
PREORDER TRAVERSAL : ROOT LEFT RIGHT
12 9
5 6
TRAVERSING THROUGH BINARY TREE
LEVELORDER TRAVERSAL :
12 9
5 6
TRAVERSING THROUGH BINARY TREE
LEVELORDER TRAVERSAL :
WITH RECURSION : 1
1. Calculate the height of the tree
2. Traverse through level and print the nodes at the level
12 9
5 6
PROBLEM STATEMENT
FIND MAXIMUM ELEMENT IN THE GIVEN BINARY TREE
12 9
5 6
PROBLEM STATEMENT
FIND TOTAL NUMBER OF NODES IN A BINARY TREE
12 9
5 6
SUMMARY
TREE TERMINOLOGIES
BINARY TREE AND TREE TRAVERSALS
PRACTICE CODING
ANY QUERIES?
KEEP WAITING FOR NEXT SESSION
