Data Structures Using C

UNIT 4
GEETHA N
ASSISTANT PROFESSOR
B.M.S. COLLEGE OF ENGINEERING
Trees - Introduction
● A tree is a nonlinear hierarchical data structure that consists of nodes connected
by edges.
● Different tree data structures allow quicker and easier access to the data as it is a
non-linear data structure.
Basic Terminologies in Trees
Basic Terminologies in Trees
● Parent Node: The node which is an immediate predecessor of a node is called the parent node of that node. {B} is the parent
node of {D, E}.
● Child Node: The node which is the immediate successor of a node is called the child node of that node. Examples: {D, E}
are the child nodes of {B}.
● Root Node: The topmost node of a tree or the node which does not have any parent node is called the root node. {A} is the
root node of the tree.
● Leaf Node or External Node: The nodes which do not have any child nodes are called leaf nodes. {I, J, K, F, G, H} are the
leaf nodes of the tree.
● Ancestor of a Node: Any predecessor nodes on the path of the root to that node are called Ancestors of that node. {A,B} are
the ancestor nodes of the node {E}
● Descendant: A node x is a descendant of another node y if and only if y is an ancestor of x.
● Sibling: Children of the same parent node are called siblings. {D,E} are called siblings.
● Level of a node: The count of edges on the path from the root node to that node. The root node has level 0.
● Internal node: A node with at least one child is called Internal Node.
● Subtree: Any node of the tree along with its descendant.
Properties of Trees:
● Number of edges: An edge can be defined as the connection between two nodes. If a tree has N nodes then it will have
(N-1) edges. There is only one path from each node to any other node of the tree.
● Depth of a node: The depth of a node is defined as the length of the path from the root to that node. Each edge adds 1
unit of length to the path. So, it can also be defined as the number of edges in the path from the root of the tree to the
node.
● Height of a node: The height of a node can be defined as the length of the longest path from the node to a leaf node of
the tree.
● Height of the Tree: The height of a tree is the length of the longest path from the root of the tree to a leaf node of the
tree.
● Degree of a Node: The total count of subtrees attached to that node is called the degree of the node. The degree of a leaf
node must be 0. The degree of a tree is the maximum degree of a node among all the nodes in the tree.
Height
Depth
Degree
Binary Tree
● Binary tree is a special tree data structure in which each node can have at most 2
children.
● Thus, in a binary tree, Each node has either 0 child or 1 child or 2 children.
Types of Binary Tree
Rooted Binary Tree
A rooted binary tree is a binary tree that satisfies the following 2 properties:
– It has a root node.
– Each node has at most 2 children.
Strictly Binary Tree
• A binary tree in which every node has either 0 or 2 children is called as a Full binary tree.
• Full binary tree is also called as Strictly binary tree.
A Complete Binary Tree
A complete binary tree is a binary tree that satisfies the following 2 properties:
– Every internal node has exactly 2 children.
– All the leaf nodes are at the same level.
Almost Complete Binary Tree
An almost complete binary tree is a binary tree that satisfies the following 2 properties-

– All the levels are completely filled except possibly the last level.

– The last level must be strictly filled from left to right.

Skewed Binary Tree
A skewed binary tree is a binary tree that satisfies the following 2 properties-
• All the nodes except one node has one and only one child.
• A skewed binary tree is a binary tree of n nodes such that its depth is (n-1).
Tree Traversal
• In order to perform any operation on a tree,you need to reach to the specific node. The
tree traversal algorithm helps in visiting a required node in the tree.
• Tree Traversal refers to the process of visiting each node in a tree data structure exactly
once.
Preorder Traversal
Algorithm-
– Visit the root
– Traverse the left sub tree i.e. call Preorder (left sub tree)
– Traverse the right sub tree i.e. call Preorder (right sub tree)
Inorder Traversal
Algorithm-
– Traverse the left sub tree i.e. call Inorder (left sub tree)
– Visit the root
– Traverse the right sub tree i.e. call Inorder (right sub tree)
Postorder Traversal
Algorithm-
– Traverse the left sub tree i.e. call Postorder (left sub tree)
– Traverse the right sub tree i.e. call Postorder (right sub tree)
– Visit the root
Breadth First Search
• Breadth First Traversal of a tree prints all the nodes of a tree level by level.
• Breadth First Traversal is also called as Level Order Traversal.
Binary Search Tree
In a binary search tree (BST), each node contains:
– Only smaller values in its left sub tree
– Only larger values in its right sub tree
Example
Construct a Binary Search Tree (BST) for the following sequence of numbers:
50, 70, 60, 20, 90, 10, 40, 100
• When elements are given in a sequence,
– Always consider the first element as the root node.
– Consider the given elements and insert them in the BST one by one.
Binary Tree Implementation
Each node of a binary tree has the following 3 parts:
● Data
● Pointer to left child node
● Pointer to right child node
Binary Tree Implementation
Binary Tree Implementation (Traversal)
Void inorder(node *root) void preorder(node *root) void postorder(node *root)

{ {
{
if(root!=NULL) if(root!=NULL)
if(root!=NULL)
{ {
{
inorder(root->left); postorder(root->left);
printf("%d ",root->data);
postorder(root->right);
printf("%d ",root->data); preorder(root->left);
printf("%d ",root->data);
inorder(root->right); preorder(root->right);
}
} }
}
} }
Binary Search Tree Operations
Commonly performed binary search tree operations are:
Search Operations
• Search Operation is performed to search a particular element in the Binary Search Tree.

• For searching a given key in the BST,

– Compare the key with the value of root node.

– If the key is present at the root node, then return the root node.

– If the key is greater than the root node value, then recur for the root node’s right subtree.

– If the key is smaller than the root node value, then recur for the root node’s left subtree.
Search Operation
Search Operation
struct node *search(struct node *node, int key) {

// Return NULL if the tree is empty

if (node == NULL)

return NULL;

if (node->key == key)

return node->data;

if (key < node->key)

search(node->left, key);

else

search(node->right, key);

}
Delete Operation
• Deletion Operation is performed to delete a particular element from the Binary
Search Tree.

• When it comes to deleting a node from the binary search tree, three cases are
possible.