Data Structures & Algorithms

(CS-212)
Week 9: Trees
 Trees
• So far we did linear data structures
• There are a number of applications where linear
data structures are not appropriate.
• Trees are non-linear
• Allow much more efficient implementations of
algorithms
• Also, tree structure is the natural form of many
types of data
• Therefore, are seen commonly in file systems,
GUIs, databases, websites etc.
 Trees
• For the linear context, in our earlier data
structures, there was a before and after
relationship between elements
• The relationship between elements in trees
is hierarchical, with elements being above
and below each other
• The terminology comes from family tree, so
we will be using terminology such as
parent, child, ancestor, descendant etc.
 Tree of a Family

Muhammad Saleem

Shahid Saleem Zahid Saleem Shahzad Saleem

Arham Noor Hadid Hashim Fahd Ahmad Sara Omer

 University Hierarchy
• Hierarchical structure of a university
shown asa tree.
 Tree
• A tree is an abstract data type that stores
elements hierarchically
• With the exception of the top element,
known as the root, each element in a tree
has a parent element and zero or more
children elements
External or leaf nodes?
 Tree Data Structure
• A linear linked list will not be able to capture
the tree-like relationship with ease.
• Shortly, we will see that for applications that
require searching, linear data structures are
not suitable.
• A node in tree can have any number of
children.
• We will focus our attention on binary trees.
 Binary Tree
• A binary tree is a finite set of elements that is
either empty or is partitioned into three disjoint
subsets.
• The first subset contains a single element called
the root of the tree.
• The other two subsets are themselves binary
trees called the left and right subtrees.
• Each element of a binary tree is called a node of
the tree.
 Binary Tree
• Binary tree with 9 nodes.
A

B C

D E F

G H I
 Binary Tree
root

B C

D E F

G H I

Left subtree Right subtree

 Binary Tree
• Recursive definition
A
root

B C

D E F

Left subtree G H I

Right subtree
 Binary Tree
• Recursive definition
A

B C
root

D E F

G H I

Left subtree
 Binary Tree
• Recursive definition
A

B C

D E F

root
G H I
 Binary Tree
• Recursive definition
A
root

B C

D E F

G H I

Right subtree
 Binary Tree
• Recursive definition
A

B C
root

D E F

G H I

Left subtree Right subtree

 Not a Tree
• Structures that are not trees.
A

B C

D E F

G H I
 Not a Tree
• Structures that are not trees.
A

B C

D E F

G H I
 Not a Tree
• Structures that are not trees.
A

B C

D E F

G H I
 Binary Tree: Terminology

parent
A

Left descendant B C Right descendant

D E F

G H I

Leaf nodes Leaf nodes

 Binary Tree
• If every non-leaf node in a binary tree has non-empty left and right subtrees, the tree
is termed a strictly binary tree.

B C

D E J F

G K H I
 Level of a Binary Tree Node
• The level of a node in a binary tree is
defined as follows:
 Root has level 0,
 Level of any other node is one more than the
level its parent.
• The depth of a binary tree is the maximum
level of any leaf in the tree.
Level of a Binary Tree Node

A 0 Level 0

B 1 C 1 Level 1

D 2 E 2 F 2 Level 2

G 3 H 3 I 3 Level 3
 Complete Binary Tree
• A complete binary tree of depth d is the strictly
binary all of whose leaves are at level d.
0
A

B 1 C 1

D 2 E 2 F 2 G 2

H 3 I J 3 K L 3 M 3 N 3 O 3
 Complete Binary Tree

A Level 0: 20 nodes

B C Level 1: 21 nodes

D E F G Level 2: 22 nodes

H I J K L M N O Level 3: 23 nodes
 Complete Binary Tree
• At level k, there are 2k nodes.
• Total number of nodes in the tree of depth
d:
d
20+ 21+ 22 + ………. + 2d =  2j = 2d+1 – 1
j=0

• In a complete binary tree, there are 2d leaf

nodes and (2d - 1) non-leaf (inner) nodes.
 Complete Binary Tree
• If the tree is built out of ‘n’ nodes then

n = 2d+1 – 1
or log2(n+1) = d+1
or d = log2(n+1) – 1
• I.e., the depth of the complete binary tree built
using ‘n’ nodes will be log2(n+1) – 1.
• For example, for n=1,000,000, log2(1000001) is
less than 20; the tree would be 20 levels deep.
• The significance of this shallowness will become
evident later.
 Operations on Binary Tree
• There are a number of operations that can
be defined for a binary tree.
• If p is pointing to a node in an existing tree
then
 left(p) returns pointer to the left subtree
 right(p) returns pointer to right subtree
 parent(p) returns the parent of p
 sibling(p) returns sibling of p.
 info(p) returns content of the node.
 Implementation of Binary Tree
• Binary trees can be implemented in at
least two ways
– As arrays
– As linked structures
 Binary Tree as Array
• 0 index based sequencing
– The root is always located in the first cell, cell 0, and –1
indicates a null child
– The key concept is that, if a parent is stored in location k,
then its left and right child are located in locations 2k+1 and
2k+2 respectively
• 1 index based sequencing
– The root is always located in the second cell, cell 1, and –1
indicates a null child
– The key concept is that, if a parent is stored in location k,
then its left and right child are located in locations 2k and
2k+1 respectively
 13

10 25

2 12 20 31

29
 Binary Tree: As Array
0 index based sequencing
Index Info Left Right
0 13 1 2
13
1 10 3 4
2 25 5 6
3 2
4 12
10 25
5 20
6 31 13
7 2 12 20 31
8
9
10 29
11
12
13 29
#define size 500
class BinaryTree
{
public:
int treenodes[size];
BinaryTree(void);
bool isleaf(int nodeindex); // returns true if the node is a leaf
int parent(int nodeindex); // returns the index of the parent
int leftchild(int nodeindex); // returns the index of the left child
int rightchild(int nodeindex); // returns the index of the right child
bool rootnode(int index, int value);
bool addleftchild(int value, int parent);
bool addrightchild(int value,int parent);
};
BinaryTree::BinaryTree(void) // builds the "constructor"
{

for(int i = 0; i < 500; i++)

treenodes[i] = -1; // set all nodes empty
}
bool BinaryTree::isleaf(int nodeindex)
{
return leftchild(nodeindex)==-1 &&
rightchild(nodeindex)==-1;
}
int BinaryTree::parent(int nodeindex)
{
int rv = (nodeindex - 1) / 2;
return (rv >= size || treenodes[rv] == -1)? -1 : rv;
}
bool BinaryTree::rootnode(int value)
{
treenodes[0] =value;
return true;

}
bool BinaryTree::addleftchild(int value, int parent)
{
int index = (2*parent)+1;
if(index<size)
{
treenodes[index] = value;
return true;

}
else
{
cout<<“can’t set child”;
return false;
}

}
bool BinaryTree::addrightchild(int value, int parent)
{
int index = (2*parent)+2;
if(index<size)
{
treenodes[index] = value;
return true;

}
else
{
cout<<“can’t set child”;
return false;
}

}
int BinaryTree::leftchild(int nodeindex) // returns the index of the
left child
{
int rv = (2*nodeindex)+1;
return (rv >= size || treenodes[rv] == -1)? -1 : rv;
}
int BinaryTree::rightchild(int nodeindex) // returns the index of the
right child
{
int rv = (2*nodeindex)+2;
return (rv >= size || treenodes[rv] == -1)? -1 : rv;
}
IMPLEMENTATION
 Binary Tree Implementation Using Pointers
• We use two classes:
– TreeNode
– BinaryTree
• Declare TreeNode class for the nodes
– info: int-type data in this example

class TreeNode {
private:
int info; // data
TreeNode* left; // pointer to Left
TreeNode* right; // pointer to Right
TreeNode* parent; // pointer to Parent

};
•
 Binary Tree Implementation Using Pointers
class TreeNode {
public:
//constructors
TreeNode();
TreeNode( int info);
int getInfo();
void setInfo(int info);
TreeNode* getLeft();
void setLeft(TreeNode *left);
TreeNode *getRight();
void setRight(TreeNode *right);
int isLeaf( );
TreeNode* getParent();
void setParent(TreeNode *parent);

private:
int info; // data
TreeNode* left; // pointer to Left
TreeNode* right; // pointer to Right
TreeNode* parent; // pointer to Parent

};
 TreeNode Constructors
TreeNode::TreeNode()
{
this->info= -1;
this->left = this->right = NULL;

}
TreeNode:: TreeNode( int info)
{
this->info= info;
this->left = this->right = NULL;

}
 TreeNode Methods
int TreeNode::getInfo()
{
return this->info;
}
void TreeNode::setInfo(int info)
{
this->info = info;

}
TreeNode* TreeNode::getLeft()
{
return this->left;

}
void TreeNode::setLeft (TreeNode *left)
{
this->left = left;
}
 TreeNode Methods
TreeNode* TreeNode::getRight()
{
return this->right;

}
void TreeNode::setRight(TreeNode *right)
{

this->right = right;

}
int TreeNode::isLeaf( )
{

if( this->left == NULL && this->right == NULL )

return 1;
return 0;
}
TreeNode* TreeNode::getParent()
{
return this->parent;

}
void TreeNode::setParent(TreeNode *parent)
{
this->parent = parent;

}
class BinaryTree{
public:
void insert(TreeNode* root, int info);
bool search(int key);
bool delete(int key);

private:
int info; // data
TreeNode* left; // pointer to Left
TreeNode* right; // pointer to Right
TreeNode* parent; // pointer to Parent

};
Lecture content adapted from Michael T. Goodrich textbook,
chapters 7.