• Introduction to Tree

Tree
• Tree is non-linear data structure. This data
structure is mainly used to represent data
containing a hierarchal relation ship between
elements.
 Tree Terminologies
• Root is a specially designed node (or data
items) in a tree. It is the first node in the
hierarchical arrangement of the data items.
The topmost node in a tree is called the root
node. Being the topmost node, the root node
will not have a parent.
• Node: Each data item in a tree is called a
node. It specifies the data information and
links (branches) to other data items.
 Tree Terminologies.....
• Parent Child Relationship: Each node in a tree
has zero or more child nodes, (by convention,
trees are drawn growing downwards). A node
that has a child is called the child's parent
node (or ancestor node, or superior,
predecessor Node). A Child Node is called
successor Node.
 Tree Terminologies.....
• Edge: It is a connecting line of two nodes. That
is a line drawn from one to another node. In a
tree with 'N' number of nodes there will be a
maximum of 'N-1' number of edges. For
example in the following figure an edge from
Node A to C can be written as (A,C)
 Tree Terminologies.....
• Path: It is a sequence of consecutive edges from the source
node to the destination node. Length of a Path is total
number of nodes in that path. In below example the path A -
B - E - J has length 4. In the following figure we can see:
• Path between A & J : A-B-E-J or {(A,B) (B,E) (E,J)}
• Path between C & K : C-G-K or {(C,G) (G,K)}
 Tree Terminologies.....
• 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).
 Tree Terminologies.....
• 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'.
– Height of following tree is 3.
– In any tree height of a node is the total no of edges from leaf node to that
node is longest path.
– In any tree : height of tree is the height of the root node.
 Tree Terminologies.....
• 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'.
– In any tree depth of node is total no of edges from root node to that node.
– In any tree depth of tree is total no of edges from toot node to leaf node in
the longest path.
 Tree Terminologies.....
• Degree of a Node: The degree of a node is the
number of sub trees of a node. or it is No of
children of a given node.
• Degree of a Tree: It is the Maximum degree of
nodes in a given tree.
 Tree Terminologies.....
• An internal node (also known as an inner
node or branch node, non terminal node, ) is
any node of a tree that has child nodes.
• An external node (also known as an outer
node, leaf node, or terminal node) is any node
that does not have child nodes. A node with
degree 0.
 Tree Terminologies.....
• Siblings: Immediate children of the same
parent are called siblings. The children nodes
of a given parent nodes are called siblings.
•
• Edge: It is a connecting line of two nodes. That
is a line drawn from one to another node.
•
• Path: It is a sequence of consecutive edges
from the source node to the destination node.
 BINARY TREE:
• A tree is said to be binary tree if it has at most
degree two. In simple word we say that a
binary tree must have zero, one or two
degree. In the next couple of slide we can see
types of Binary Tree.
 Strictly Binary Tree:
• If every non-terminal node in a binary tree consist of non-
empty left sub tree and non-empty right sub tree then such a
tree is called strictly binary tree. following two trees are
strictly binary tree. Or every node in the binary tree has either
0 or two children is called strictly binary tree.
 Complete Binary Tree:
• A strictly binary tree with n nodes of depth d is called
complete binary tree if all of it’s terminal nodes (leaf nodes)
are at the same level. Following two trees are complete binary
tree.
 BINARY TREE:

• A tree is said to be binary tree if it have at

most degree two. In simple word we say that a
binary tree must have zero, one or two
degree.
 Strictly Binary Tree:
• If every non-terminal node in a binary tree consist of
non-empty left sub tree and non-empty right sub
tree then such a tree is called strictly binary tree.
following two trees are strictly binary tree. Or every
node in the binary tree has either 0 or two children is
called strictly binary tree.
 Complete Binary Tree:
• A strictly binary tree with n nodes of depth d
is called complete binary tree if all of it’s
terminal nodes (leaf nodes) are at the same
level. Following two trees are complete binary
tree.
 Skewed Binary Tree:
• A skewed binary tree is a binary tree that satisfies the following 2
properties-
1. All the nodes except one node has one and only one child.
2. The remaining node has no child.
• A skewed binary tree is a binary tree of n nodes such that its depth is (n-
1).
 BINARY TREE REPRESENTATION

• A binary tree can be represented in a system

using one of the two methods.
– Linked representation
– Array representation.
 Array Representation of tree:
An array can be used to store the nodes of a
binary tree. The indexing for storing binary
nodes begins from 0 .... The maximum no of
nodes are specified.
• The root node always at index 0. Then
successive memory locations(index) are
assigned level wise to the left child & then
right child.
Array Representation of tree:
 Array Representation:
Formulas for identifying the relationship:
• Father(n): The father of node can be identified by using the following
formula:
– Floor((n-1)/2)
Example: Consider a node numbered (indexing) 3. Now we can identify the
father of 3 as per following:
– Floor((n-1)/2)
– Floor((3-1)/2) = Floor(1) = 1; it means the father of node at index 3 will
be at index 1.
 Array Representation:
Formulas for identifying the relationship:
• Left Child(n): The left child of node at index n will be at: (2n+1)
– Example: Consider a node numbered (indexing) 1. its left child will
be at indexing:
– (2n+1)= (2*1+1) = 3

• Right Child(n): The Right child of node at index n will be at: (2n+2)
– Example: Consider a node numbered (indexing) 2. its right child will
be at indexing:
– (2n+2)= (2*2+2) = 6

• Sibling:
• If the left child at index n is given then right sibling is at (n+1).
• If the right child at index n is given then left sibling is at (n-1).
 Linked Representation of Tree:
The most popular and practical way of representing a binary tree
is using linked list (or pointers). In linked list, every element is
represented as nodes. A node consists of three fields such as :
(a) Left Child (LChild)
(b) Information of the Node (Info)
(c) Right Child (RChild)

struct Tree
{
int /char information;
struct Tree *Lchild;
struct Tree *Rchild;
};
Continued ............
 Extended Binary Tree:
• For converting binary tree to a strictly binary
tree all the NULL subtrees are extended with
dummy nodes then such a tree is called
extended binary tree.
Extended Binary Tree:
 Traversing of Binary tree:
• A tree can be traversed using following three
methods / Algorithms
– Pre Order Traversing (Root, Left, Right)
– In Order Traversing (Left, Root, Right)
– Post Order Traversing (Left, Right, Root)
Pre Order Traversing (Root, Left, Right)
1. Visit the ROOT node.
2. Traverse the LEFT subtree in pre order.
3. Traverse the RIGHT subtree in pre order.
 Example: Traverse the following tree in Preorder

Pre Order: A,B,D,E,I,C,F,G,J

In Order Traversing (Left, Root, Right)
1. Traverse the LEFT subtree in in order.
2. Visit the ROOT node.
3. Traverse the RIGHT subtree in in order.
• Example: Traverse the following tree in Inorder

In Order: D,B,I,E,A,F,C,G,J
 Post Order Traversing (Left, Right , Root)

1. Traverse the LEFT subtree in post order.

2. Traverse the RIGHT subtree in post order.
3. Visit the ROOT node.
• Example: Traverse the following tree in Postorder

Post Order: D,I,E,B,F,J,G,C,A

• Draw a tree if following (pre order, in order)
order are given.

• Draw a tree if following (post order, in order

are given).
BINARY EXPRESSION TREE / EXPRESSION TREE / Algebraic Expression

• When an expression is converted into binary

tree that tree is called binary expression tree
or expression tree. Here operands become
leafs and operators become roots or sbroots.
 CONVERSION OF EXPRESSION INTO
BINARY TREE:
• CONVERSION OF Algebraic EXPRESSION INTO
BINARY TREE: It is a divide and conquer
technique. It is based on following steps:
All expressions in parentheses are evaluated
first.
Exponent will come next.
Division, multiplication & mod will be the next.
Subtraction and addition will be evaluated
next.
Example: Convert Expression “A / B – D” into Binary Tree
Example: Convert Expression “(A – B) * C+ D” into Binary Tree
Example: Convert Expression “ (A + B) * (C + D) - E / F” into
Binary Tree
 BINARY SEARCH TREE (BST):
• A binary search tree is a tree which is either empty or satisfy the following three
conditions:
1. The vale of left child must always less then root.
2. The vale of right child must always greater then root.
3. All the left child must follow first (1) condtion and all the right child must
follow second(condtion).
• Example:
 Variation / Drawback in BST
• Left Skew BST:
 Variation / Drawback in BST
• Right Skew BST:
• Important Point: In order of BST always gives
Traversing in increasing [Link] can see
inorder traversing of following tree give
increasing sorted order of nodes.
 INSERTING NODE INTO BINARY
SEARCH TREE:
• The node that is inserted very fist become root of
the tree; then next sequence of insertion of
nodes become either the root of left sub tree of
right sub tree as per following:
• Compare the keynode with root node if it is lesser
then root node, it goes to the left; or if it is
greater then root node, it goes to right and insert
it wherever its place is found.
• For example: Insert following nodes into BST
• 43, 10, 79, 90, 12, 54, 11, 9, 50 (ans is on the next
slide)
Q: Insert following Nodes into BST :
43, 10, 79, 90, 12, 54, 11, 9, 50
 DELETING NODE FROM BINARY SEARCH TREE:
• For the deletion of node following three condition may exist,
we delete node as per following three conditions:

 Node having zero (0) child: If a node that is to be deleted has

0 child, it can be deleted directly or its link can be deleted.
 Node having One (1) child: If a node that is to be deleted has
1 child, it can be deleted by replacing it with its child.
 Node having Two (2) child: If a node that is to be deleted has
2 children, it can be deleted by one of the following two
methods:
 It can be deleted by replacing with immediate predecessor
in in-order or it can be deleted by replacing with largest
node from the left sub tree.
or
 It can be deleted by replacing with immediate successor in
in-order or it can be deleted by replacing with smallest
node from the right sub tree.
• Creation / Insertion of Binary Tree or Binary
Search Tree
• Searching in BST
 BINARY TREE /BST INSERTION OR CREATION OF NODES
• Algorithm or function: //In Following function or algorithm, ‘p’ is a structure
pointer, in the beginning tree will be empty (does not have any node), so p will
have NLL, ‘val’ is the vale that is to be inserted into binary tree’s node.

node *insert(node *p,int val)

{
if(p==NULL)
{
p=(node*)malloc(sizeof(node));
p->lchild = p->rchild = NULL;
p->info=val;
}
else if(val < p->info)
{
p ->lchild= insert(p->lchild,val);
}
else if(val > p->info)
{
p ->rchild= insert(p->rchild,val);
}
return(p);
}
 SEARCHIN IN BST or SEARCHIN IN Binary Tree:
• Algorithm or function: Here p is a structure pointer and ‘key’ is the
vale that is to be searched in binary search tree. At the time of
function calling root and keyvalue that is to be searched will be
passed

search(node *p,int key)

{
if(p==NULL)
{
printf("Searching is not successful");
}
else if(key == p->info)
{
printf("Searching is successful");
}
else if(key < p->info)
{
search(p->lchild , key);
}
else if(key > p->info)
{
search(p->rchild,key);
}
}
 Tree TRAVERSING ALGORITHMS:

• There are three traversing algorithm which we

have already seen:
• Pre Order
• Post Order
• In Order
 Pre Order Traversing:
Pre Order Traversing: -
1. PRINT/Visit the ROOT node.
2. Traverse the LEFT subtree in pre order.
3. Traverse the RIGHT subtree in pre order.

Pre Order Traversing: -

PREORDER(Node *P)
{
If( P != NULL)
{
PRINT (P->INFO)
PREORDER(P->Lchild)
PREORDER(P->Rchild)
}
}
 In Order Traversing:
• In Order Traversing: -
1. Traverse the LEFT subtree in in-order.
2. PRINT/Visit the ROOT node.
3. Traverse the RIGHT subtree in in-order.

• In Order Traversing: -
INORDER(Node *P)
{
If( P != NULL)
{
INORDER (P->Lchild)
PRINT (P->INFO)
INORDER (P->Rchild)
}
}
 Post Order Traversing:
Post Order: -
1. Traverse the LEFT subtree in post order.
2. Traverse the RIGHT subtree in post order.
3. PRINT/Visit the ROOT node.

Post Order: -
POSTORDER(Node *P)
{
If( P != NULL)
{
POSTORDER (P->Lchild)
POSTORDER (P->Rchild)
PRINT (P->INFO)
}
}