TREES
AND
TERMINOLOGY
TREE
● Tree is a non-linear data structure which organizes data in hierarchical structure
and this is a recursive definition
● Tree data structure is a collection of data (Node) which is organized in hierarchical
structure recursively
● A tree is a connected graph without any circuits
● If in a graph, there is one and only one path between every pair of vertices, then the
graph is called as tree
PROPERTIES
● There is one and only one path between every pair of vertices in a tree
● A tree with n vertices has exactly (n-1) edges
● A graph is a tree if and only if it is minimally connected
● Any connected graph with n vertices and (n-1) edges is a tree
TREE TERMINOLOGY
ROOT
● The first node from where the tree originates is called as a root node
● In any tree, there must be only one root node
● We can never have multiple root nodes in a tree data structure
EDGE
● The connecting link between any two nodes is called as an edge
● In a tree with n number of nodes, there are exactly (n-1) number of edges
PARENT
● The node which has a branch from it to any other node is called as a parent node
● In other words, the node which has one or more children is called as a parent node
● In a tree, a parent node can have any number of child nodes
CHILD
● The node which is a descendant of some node is called as a child node
● All the nodes except root node are child nodes
SIBLINGS
● Nodes which belong to the same parent are called as siblings
● In other words, nodes with the same parent are sibling nodes
DEGREE
● Degree of a node is the total number of children of that node
● Degree of a tree is the highest degree of a node among all the nodes in the tree
INTERNAL NODE
● The node which has at least one child is called as an internal node
● Internal nodes are also called as non-terminal nodes
● Every non-leaf node is an internal node
LEAF NODE
● The node which does not have any child is called as a leaf node
● Leaf nodes are also called as external nodes or terminal nodes
LEVEL
● In a tree, each step from top to bottom is called as level of a tree
● The level count starts with 0 and increments by 1 at each level or step
HEIGHT
● Total number of edges that lies on the longest path from any leaf node to a
particular
● Node is called as height of that node
● Height of a tree is the height of root node
● Height of all leaf nodes = 0
DEPTH
● Total number of edges from root node to a particular node is called as depth
● Depth of a tree is the total number of edges from root node to a leaf node in the
● longest path
● Depth of the root node = 0
● The terms “level” and “depth” are used interchangeably
SUBTREE
● In a tree, each child from a node forms a subtree recursively
● Every child node forms a subtree on its parent node
FOREST
• A forest is a set of disjoint trees
TYPES OF TREE
•Binary Tree
•Binary Search Tree
•AVL Tree
•Red-Black Tree
•N-ary tree
Binary Tree
The binary tree is the kind of tree in which most two children can be found for each parent. The kids
are known as the left kid and right kid.
TYPES OF BINARY TREES IN JAVA
FULL BINARY TREE
A Binary Tree is full if every node has 0 or 2 children. We can also say a full binary tree
is a binary tree in which all nodes except leaves have two children
COMPLETE BINARY TREE
A Binary Tree is complete Binary Tree if all levels are completely filled except possibly
the last level and the last level has all keys as left as possible
PERFECT BINARY TREE
A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all
leaves are at the same level
Binary Tree Traversal
A binary tree can be traversed in preorder, inorder, postorder or level-order. Among these traversal
methods, preorder, postorder and level-order traversal
Preorder Traversal:
visit the root node, then traverse the left subtree and finally traverse the right subtree.
Inorder Traversal:
traverse the left subtree, then visit the root node and finally traverse the right subtree.
Postorder Traversal:
traverse the left subtree, then traverse the right subtree and finally visit the root node.
Level-order Traversal: traverse the tree level by level.
Binary Tree Traversal
A binary tree can be traversed in preorder, inorder, postorder or level-order. Among these traversal
methods, preorder, postorder and level-order traversal
Preorder Traversal:
visit the root node, then traverse the left subtree and finally traverse the right subtree.
Inorder Traversal:
traverse the left subtree, then visit the root node and finally traverse the right subtree.
Postorder Traversal:
traverse the left subtree, then traverse the right subtree and finally visit the root node.
Level-order Traversal: traverse the tree level by level.
Binary Tree Traversal
Depth First Traversals:
(a) Inorder (Left, Root, Right) : 4 2 5 1 3
(b) Preorder (Root, Left, Right) : 1 2 4 5 3
(c) Postorder (Left, Right, Root) : 4 5 2 3 1
Breadth First or Level Order Traversal : 1 2 3 4 5
Binary Tree Traversal
Preorder Traversal:
visit the root node, then traverse the left subtree and finally traverse the right subtree.
Preorder (Root, Left, Right) :
Binary Tree Traversal
Inorder Traversal:
traverse the left subtree, then visit the root node and finally traverse the right subtree.
Inorder (Left, Root, Right)
Binary Tree Traversal
Postorder Traversal:
traverse the left subtree, then traverse the right subtree and finally visit the root node.
Postorder (Left, Right, Root) :
Binary Tree Traversal
Level-order Traversal: traverse the tree level by level.
Postorder ( Root ,Left, Right) :
Binary Search Tree
Binary Search Tree (BST) is a binary tree extension with several optional restrictions. The left child value of a
node should in BST be less than or equal to the parent value and the right child value should always be greater
than or equal to the parent’s value.
Binary Search Tree
Example:13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18
AVL Tree
AVL tree is a binary search tree self-balancing. On behalf of the inventors Adelson-Velshi and
Landis, the name AVL is given. This was the first tree that balanced dynamically. A balancing factor
is allocated for each node in the AVL tree, based on whether the tree is balanced or not. The height
of the node kids is at most 1. AVL vine. In the AVL tree, the correct balance factor is 1, 0 and -1.
Red-Black Tree
The red-black name is given because the Red-black tree has either red or Black painted on each
node according to the red-black tree’s properties. It maintains the balance of the forest. Even
though this tree is not a fully balanced tree, the searching operation only takes O (log n) time.
N-ary tree
A binary tree is a rooted tree in which each node has no more than 2 children. Let's extend this
definition to N-ary tree. If a tree is a rooted tree in which each node has no more than N children, it
is called N-ary tree.
Example of 3-ary tree:
Convert a N-ary Tree to a Binary Tree
The strategy follows two rules:
•The left child of each node in the binary tree is the next sibling of the node in the N-ary tree.
•The right child of each node in the binary tree is the first child of the node in the N-ary tree.
Example:
Convert a Binary Tree to a N-ary Tree
The strategy follows two rules:
•Deal with its children recursively.
•Add its left child as the next child of its parent if it has a left child.
• Add its right child as the first child of the node itself if it has a right child.
Example:
Convert a Binary Tree to a N-ary Tree
The strategy follows two rules:
•Deal with its children recursively.
•Add its left child as the next child of its parent if it has a left child.
• Add its right child as the first child of the node itself if it has a right child.
Example:
BINARY TREES IN JAVA
● A Binary tree is a tree data structure in which each node has at most two child nodes,
usually distinguished as “left” and “right”
● In a binary tree, a degree of every node is maximum two. A tree with n nodes has
exactly n−1 branches or degree
BINARY TREE TRAVERSALS
POSTORDER void printPostorder(Node node)
{
if(node == null)
● Traverse the left subtree return;
● Traverse the right subtree
● Visit the tree printPostorder(node.left);
printPostorder(node.right);
System.out.print(node.key + " ");
}
OUTPUT:
45231
BINARY TREE TRAVERSALS
IPREORDER ORDER void printPreorder(Node node)
{
if(node == null)
● Visit the tree return;
● Traverse the left subtree
● Traverse the right subtree System.out.print(node.key + " ");
printInorder(node.left);
printInorder(node.right);
OUTPUT:
12453
BINARY TREE TRAVERSALS
IINORDER ORDER void printInorder(Node node)
{
if(node==null)
• Traverse the left subtree return;
• Visit the tree printInorder(node.left);
• Traverse the right subtree
System.out.print(node.key + " ");
printInorder(node.right);
}
OUTPUT:
42513
PUZZLE
QUESTION
What is common in three different types of traversals?
A. Root is visited before right subtree
B. Left subtree is always visited before right subtree
C. Root is visited after left subtree
D. All of the above
QUESTION
The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g,
respectively. The postorder traversal of the binary tree is:
A. d e b f g c a
B. e d b g f c a
C. e d b f g c a
D. d e f g b c a
Answer:
QUESTION
Which of the following cannot generate the full binary tree?
A. Inorder and preorder
B. Inorder and postorder
C. Preorder and postorder
D. None of the above
Answer:
QUESTION
A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is
traversed in pre-order and the values in each node printed out, the sequence of
values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is traversed in post-order, the
sequence obtained would be
A. 8,7,6,5,4,3,2,1
B. 1,2,3,4,8,7,6,5
C. 2,1,4,3,6,7,8,5
D. 2,1,4,3,7,8,6,5
Answer:
QUESTION
What is the order of nodes visited using a post - order traversal?
A. 14,2,1,3,11,10,7,30,40
B. 1,3,2,7,10,40,30,11,14
C. 1,2,3,14,7,10,11,40,30
D. 1,2,3,7,10,11,14,30,40
Answer:
QUESTION
If each node in a tree has value greater the every value in its left subtree and has value
less than every value in its right subtree, the tree is called
A. Complete tree
B. Full binary tree
C. Binary search tree
D. AVL tree
QUESTION
The number of edges from the root to the node is called __________ of the tree.
a) Height
b) Depth
c) Length
d) Width
Answer:
QUESTION
The number of edges from the node to the deepest leaf is called _________ of the tree.
a) Height
b) Depth
c) Length
d) Width
Answer:
program
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct
node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
program
#include <stdio.h> void printPostorder(struct node* node)
#include <stdlib.h> {
struct node if (node == NULL)
{ return;
int data; printPostorder(node->left);
struct node* left; printPostorder(node->right);
struct node* right; printf("%d ", node->data);
}; }
struct node* newNode(int data) void printInorder(struct node* node)
{ {
struct node* node = (struct node*) if (node == NULL)
malloc(sizeof(struct return;
node)); printInorder(node->left);
node->data = data; printf("%d ", node->data);
node->left = NULL; printInorder(node->right);
node->right = NULL; }
return(node);
}
PUZZLE
Tell a word without using vowels
PUZZLE
The three numbers in each box have a relationship that is the same in all six boxes.
UNDIRECTED VS. DIRECTED GRAPHS
A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes
also referred to as vertices and the edges are lines or arcs that connect any two nodes in the
graph.
UNDIRECTED VS. DIRECTED GRAPHS
UNWEIGHTED VS. WEIGHTED GRAPHS
A weighted edge is simply an edge with an associated number, or value, alternatively
known as a weight
MULTIPLE EDGES & LOOPS
Simple graph : Each vertex has exactly one edge connecting it to another vertex
— no vertex connects with another vertex through multiple edges
Multigraph : A graph that does contain multiple edges & self-loops, is known as
a multigraph
ACYCLIC VS CYCLIC GRAPHS
A cycle exists if one can travel from a single vertex back to itself without
repeating (retracing) a single edge or vertex along it’s path
A graph that contains at least one cycle is known as a cyclic graph
Subgraph
● Subgraph: A graph G = (V1, E1) is called subgraph of a graph G(V, E) if V1(G) is a
subset of V(G) and E1(G) is a subset of E(G) such that each edge of G1 has same
end vertices as in G
TYPES OF SUBGRAPH
Vertex disjoint subgraph: Any two graph G1 = (V1, E1) and G2 = (V2, E2) are said to
be vertex disjoint of a graph G = (V, E) if V1(G1) intersection V2(G2) = null. In figure
there is no common vertex between G1 and G2
Edge disjoint subgraph: A subgraph is said to be edge disjoint if E1(G1) intersection
E2(G2) = null. In figure there is no common edge between G1 and G2
Note: Edge disjoint subgraph may have vertices in common but vertex disjoint graph
cannot have common edge, so vertex disjoint subgraph will always be an edge
disjoint subgraph
HAMILTONIAN GRAPH
A Hamiltonian graph may be defined as
If there exists a closed walk in the connectedgraph that
visits every vertex of the graph exactly once(except
starting vertex) without repeating the edges,
then such a graph is called as a Hamiltonian graph. OR
Any connected graph that contains a Hamiltonian circuit is
called as a Hamiltonian Graph
HAMILTONIAN GRAPH
Hamiltonian Graph
A Hamiltonian graph may be defined as
HAMILTONIAN GRAPH
Whether this graph is hamiltonian or not
HAMILTONIAN PATH
Hamiltonian Path
● If there exists a walk in the connected graph that visits every vertex of the graph exactly
once without repeating the edges, then such a walk is called as a Hamiltonian path
● If there exists a Path in the connected graph that contains all the vertices of the graph,
then such a path is called as a Hamiltonian path
LOGIC
Hamiltonian Path Examples
Examples of Hamiltonian path are as follows
isEmpty
Which of the following is / are Hamiltonian graphs?
LOGIC
A) The graph neither contains a Hamiltonian path nor it contains a Hamiltonian circuit
B) Since graph does not contain a Hamiltonian circuit, therefore It is not a Hamiltonian Graph
C) The graph neither contains a Hamiltonian path nor it contains a Hamiltonian circuit
Since graph does not contain a Hamiltonian circuit, therefore It is not a Hamiltonian Graph
A) The graph contains both a Hamiltonian path (ABCDHGFE) and a Hamiltonian circuit
(ABCDHGFEA).
Since graph contains a Hamiltonian circuit, therefore It is a Hamiltonian Graph
A) The graph contains both a Hamiltonian path (ABCDEFG) and a Hamiltonian circuit
(ABCDEFGA)
Since graph contains a Hamiltonian circuit, therefore It is a Hamiltonian Graph
LOGIC
● The graph neither contains a Hamiltonian path nor it
contains a Hamiltonian circuit
● Since graph does not contain a Hamiltonian circuit,
therefore It is not a Hamiltonian Graph
● The graph contains both a Hamiltonian path (ABCDEFGHI)
and a Hamiltonian circuit (ABCDEFGHIA)
● Since graph contains a Hamiltonian circuit, therefore It is a
Hamiltonian Graph
● To gain better understanding about Hamiltonian Graphs in
Graph Theory
Important Notes
● Any Hamiltonian circuit can be converted to a
Hamiltonian path by removing one of its edges
● Every graph that contains a Hamiltonian circuit
also contains a Hamiltonian path but vice versa
is not true
● There may exist more than one Hamiltonian
paths and Hamiltonian circuits in a graph
EXAMPLE
For example, a Hamiltonian Cycle in the following graph is {0, 1, 2, 4, 3, 0}.
(0)--(1)--(2)
| | | |
| | | |
| | | |
(3)--------(4)
And the following graph doesn’t contain any Hamiltonian Cycle.
(0)--(1)--(2)
| | | |
| | | |
| | | |
(3) (4)
EXAMPLE
A graph is considered Eulerian if the graph is both connected and has a closed
trail (a walk with no repeated edges) containing all edges of the graph.
Euler Graph - A connected graph G is called an Euler graph, if there is a closed trail
which includes every edge of the graph G.
Euler Path - An Euler path is a path that uses every edge of a graph exactly once.
An Euler path starts and ends at different vertices.
EXAMPLE
EXAMPLE
THANK YOU
