Data Structures

&
Analysis of Algorithm
Week # 9
Lecture #17,18
Tree

Prepared By : Miss Sonia Jamil

Lecturer at Computer Science Department
ISP Multan
Objective of DS

 To impart the basic concepts of data structures and algorithms.

 To understand concepts about searching and sorting techniques.
 To Understand basic concepts about stacks, queues, lists, trees and
graphs.
 To understanding about writing algorithms and step by step approach
in solving problems with the help of fundamental data structures
Outcome of DS

 Ability to analyze algorithms and algorithm correctness.

 Ability to summarize searching and sorting techniques.
 Ability to describe stack, queue and linked list operation.
 Ability to have knowledge of tree and graphs concepts
Summary of previous lecture

 In the previous lecture we discussed following Concepts of Fourth linear data

structure…
 Doubly Linked List
 Example
 Application
 Algorithm
Lecture Agenda

 To move further in our course content. Today we are going to discuss about Non-Linear
Data Structures
 Tree
 Types of Tree
 Applications of Tree
 Operations of Tree
 Tree Traversing (Pre-Order, In-Order, Post-Order)
Introduction to
trees
• So far we have discussed mainly linear data structures – strings,
arrays, lists, stacks and queues

• Now we will discuss a non-linear data structure called tree.

• Trees are mainly used to represent data containing a hierarchical

relationship between elements, for example,
• records,
• family trees and
• table of contents.
• Consider a parent-child relationship
 So far we discussed Linear data
structures like

stack
Tree

 Tree is a tree in which each node can have either zero or many child nodes.
 It can not be empty.
 There is no limitation on the degree of a node.
 The topmost node of a general tree is called the root node.
 There are many subtrees in a Tree.
 The subtree of a tree is unordered because the nodes of the general tree can not be
ordered according to specific criteria.
 In a tree, each node has in-degree(number of parent nodes) one and maximum out-
degree(number of child nodes) n.
Binary Tree

 A binary tree is the specialized version of the simple tree.

 A binary tree is a tree in which each node can have at most two nodes.
 In a binary tree, there is a limitation on the degree of a node because the nodes in a
binary tree can’t have more than two child node(or degree two).
 The topmost node of a binary tree is called root node and there are mainly two
subtrees one is left-subtree and another is right-subtree.
 Unlike the simple tree, the binary tree can be empty.
 Unlike the simple tree, the subtree of a binary tree is ordered because the nodes of a
binary tree can be ordered according to specific criteria.
Difference between tree & Binary tree

 The main difference between tree and binary tree is

that tree arranges data in a structure similar to a tree, in
a hierarchical manner, while a binary tree is a type of tree in which a
parent node can have a maximum of two child nodes.
Important Terms of Tree

 Following are the important terms with respect to tree.

 Path − Path refers to the sequence of nodes along the edges of a tree.
 Root − The node at the top of the tree is called root. There is only one root per tree and one
path from the root node to any node.
 Parent − Any node except the root node has one edge upward to a node called parent.
 Child − The node below a given node connected by its edge downward is called its child
node.
 Leaf − The node which does not have any child node is called the leaf node.
 Subtree − Subtree represents the descendants of a node.
 Visiting − Visiting refers to checking the value of a node when control is on the node.
Important Terms of Tree Continue…

 Traversing − Traversing means passing through nodes in a specific order.

 Levels − Level of a node represents the generation of a node. If the root
node is at level 0, then its next child node is at level 1, its grandchild is at
level 2, and so on.
 keys − Key represents a value of a node based on which a search
operation is to be carried out for a node.
 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.
Why Trees?

 One reason to use trees might be because you want to store

information that naturally forms a hierarchy. For example, the file
system on a computer:
 Trees (with some ordering e.g., BST) provide moderate access/search
(quicker than Linked List and slower than arrays).
 Trees provide moderate insertion/deletion (quicker than Arrays and
slower than Unordered Linked Lists).
 Like Linked Lists and unlike Arrays, Trees don’t have an upper limit on
number of nodes as nodes are linked using pointers.
Implementation of Tree

 One way to implement a tree would be to have in each node, besides its data, a link to
each child of the node.
 However, since the number of children per node can vary so greatly and is not known
in advance, it might be infeasible to make the children direct links in the data
structure, because there would be too much wasted space.
 Node declaration of Tree:

struct TreeNode
{
Object element;
TreeNode *firstChild;
TreeNode *nextSibling;
};
Implementation of Tree

 The solution is simple: Keep the children of each node in a linked list of tree nodes.
The above declaration as shows.
 Below Figure shows how a tree might be represented in this implementation.
 Horizontal arrows that point downward are first Child links.
 Arrows that go left to right are next Sibling links.
 Null links are not drawn, because there are too many.
 In the tree of Figure, node E has both a link to a sibling (F) and a link to a child (I),
while some nodes have neither.
Types of Tree

 Full Binary Tree

 Complete Binary Tree
 Perfect Binary Tree
 Balanced Binary Tree
 Skew Tree
Full Binary Tree

 A Binary Tree is a full binary tree if every node has 0 or 2 children.

 The following are the examples of a full binary tree.
 We can also say a full binary tree is a binary tree in which all nodes
except leaf nodes have two children.
 In a Full Binary Tree, number of leaf nodes is the number of
internal nodes plus 1
L=I+1
Where L = Number of leaf nodes, I = Number of internal nodes
Complete Binary Tree

 A Binary Tree is a complete Binary Tree if all the 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 a Perfect Binary Tree in which all the

internal nodes have two children and all leaf nodes are
at the same level.
 A Perfect Binary Tree of height h (where height is the
number of nodes on the path from the root to leaf) has
2h – 1 node.
 An example of a Perfect binary tree is ancestors in the
family. Keep a person at root, parents as children,
parents of parents as their children.
Balanced Binary Tree

 A binary tree is balanced if the height of the tree is O(Log n) where n

is the number of nodes.
 For Example,
 The AVL tree maintains O(Log n) height by making sure that the difference
between the heights of the left and right subtrees is almost 1.
 Red-Black trees maintain O(Log n) height by making sure that the number
of Black nodes on every root to leaf paths is the same and there are no
adjacent red nodes.
 Balanced Binary Search trees are performance-wise good as they provide
O(log n) time for search, insert and delete.
Skew Tree

 A Tree where every internal node has one child. Such trees are
performance-wise same as linked list.
Binary Tree Basic Operations

 The basic operations that can be performed on a binary search tree data structure, are the
following −
Insert − Inserts an element in a tree/create a tree.
Search − Searches an element in a tree.
 Traversal is a process to visit all the nodes of a tree and may print their values too.
 Because, all nodes are connected via edges (links) we always start from the root (head)
node.
 That is, we cannot randomly access a node in a tree. There are three ways which we use to
traverse a tree −
In-order Traversal

Pre-order Traversal

Post-order Traversal
 Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values
In-order Traversal
 In this traversal method, the left subtree is visited first, then the root and later the
right sub-tree.
 We should always remember that every node may represent a subtree itself.
 If a binary tree is traversed in-order, the output will produce sorted key values in an
ascending order.
In-order Traversal

 We start from A, and following in-order traversal, we move to its left subtree B. B is
also traversed in-order. The process goes on until all the nodes are visited. The output
of in-order traversal of this tree will be −
D →B→E→A→F→C→G
 Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.
Pre-Order Traversal

 In this traversal method, the root node is visited first, then the left
subtree and finally the right subtree.
Pre-Order Traversal

 We start from A, and following pre-order traversal, we first visit A itself and then move
to its left subtree B. B is also traversed pre-order. The process goes on until all the
nodes are visited. The output of pre-order traversal of this tree will be −
A → B→D→E→C→F→G
Algorithm

Until all nodes are traversed −

Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.
Post-order Traversal

 In this traversal method, the root node is visited last, hence the
name. First we traverse the left subtree, then the right subtree and
finally the root node.
Post-order Traversal

 We start from A, and following Post-order traversal, we first visit the left
subtree B. B is also traversed post-order. The process goes on until all the
nodes are visited. The output of post-order traversal of this tree will be −
D →E→B→F→G→C→A
Algorithm

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.
Insertion

 The very first insertion creates the tree.

 Afterwards, whenever an element is to be inserted, first locate its
proper location.
 Start searching from the root node, then if the data is less than the
key value, search for the empty location in the left subtree and insert
the data.
 Otherwise, search for the empty location in the right subtree and
insert the data.
NLS Code of Insertion

If root is NULL
then create root node
return
If root exists then
compare the data with node.data
while until insertion position is located
If data is greater than node.data
goto right subtree
else
goto left subtree
endwhile
insert data
 //go to left of the tree
Algorithm of Insertion if(data < parent->data) {
current = current->leftChild;

void insert(int data) { //insert to the left

struct node *tempNode = (struct node*) malloc(sizeof(struct if(current == NULL) {
node)); parent->leftChild =
struct node *current; tempNode;
return;
struct node *parent;
}
tempNode->data = data; }
tempNode->leftChild = NULL; //go to right of the tree
tempNode->rightChild = NULL; else {
//if tree is empty, create root node current = current-
>rightChild;
if(root == NULL) {
root = tempNode; //insert to the right
} else { if(current == NULL) {
current = root; parent->rightChild =
parent = NULL;
tempNode;
return;
while(1) {
}
Search

 Whenever an element is to be searched, start searching from the root

node, then if the data is less than the key value, search for the
element in the left subtree.
 Otherwise, search for the element in the right subtree. Follow the
same algorithm for each node.
NLS Code of Searching

If root.data is equal to search.data

return root
else
while data not found
If data is greater than node.data
goto right subtree
else
goto left subtree
If data found
return node
endwhile
return data not found
Algorithm of Searching
//else go to right tree
struct node* search(int data) {
else {
struct node *current = root; current = current->rightChild;
printf("Visiting elements: "); }
//not found
if(current == NULL) {
while(current->data != data) { return NULL;
}
if(current != NULL)
return current;
printf("%d ",current->data); }
}

//go to left tree

if(current->data > data) {
current = current->leftChild;
Applications of Tree

 Binary Search Trees(BSTs) are used to quickly check whether an

element is present in a set or not.
 Heap is a kind of tree that is used for heap sort.
 A modified version of a tree called Tries is used in modern routers to
store routing information.
 Most popular databases use B-Trees and T-Trees, which are variants of
the tree structure to store their data
 Compilers use a syntax tree to validate the syntax of every program
you write.