Trees

1
Nature View of a Tree
leaves

branches
root
Computer Scientist’s View
root

leaves

branches
nodes
 Trees
•A tree is a finite set of elements. Root
•It is an abstract model of a
hierarchical structure. A

•consists of nodes with a parent-

child relation. B C

•Applications:
• Organization charts D E F G
• File systems
• Programming environments H I leaf
COMSATS

5
Directory Structure

6
Tree Terminology
Subtree: tree consisting of a
• Root: node without parent (A) node and its descendants
• Parent: node A is parent of B is parent of F…
• Child: G is Children of C is children of A
• Siblings: nodes share the same parent Level 0 …………………………....
A
• Internal node: node with at least one child (A, B, C,
F)
• External node (leaf ): node without children (E, I, J,
K, G, H, D)
B
………………Level C
1………………….…………D
• Ancestors of a node: parent, grandparent, grand-
grandparent, etc.
• Descendant of a node: child, grandchild, grand-
grandchild, etc.
…………………Level
E F 2…………………………..
G H
• Depth of a node: number of level
• Height of a tree: maximum no levels (3)
• Degree of a node: the number of its children
• Degree of a tree: the node with max no of child's. ……………………………..Level
I J K 3…………..
 Tree Properties
Property Value
Level 0 ………………………….... A Number of nodes 9
Height of tree 4
Level 1………………………………………………… Root Node A
B C
Leaves DHIFC
Interior nodes BCEG
Level 2………………………………………………..
D E F Ancestors of H GEBA
Descendants of B DEFGHI
Siblings of E FD
Level 3…………………………….. Right subtree of A C
G
Degree of B 3

Level 4……………………………..
Degree of this tree 3 (max dgre)
H I
Depth (Level) of E 2
Height of tree (max levels) 4
Representation of Trees
• Every tree node:
• Data:– useful information
• Children:- pointers to its children

Data

Data   Data  Data  

Data   Data   Data  

Representation of Trees
• Node Representation

• The root comes first, followed by a list of sub-trees

data link 1 link 2 ... link n

How many link fields are

needed in such a representation?
 Unbounded Branching
Left Child - Right Sibling
data
left child right sibling
• Unbounded Trees: A
• Parent
• Left Child
• Right Sibling D
B C

E F G H I J

K L M
Left Child, Right Sibling Representation

Data
Left Right
Child Sibling A

B C D

E F G H I

J K L
Binary Tree
• A binary tree is a tree with the
following properties:
A
• Each node has at most two children
(degree of two) called as:
• Left child
• Right child
B C
• The children of a node are an ordered
pair

D E F G
• Binary Tree Recursive Definition: a
binary tree is either
• a tree consisting of a single node, OR
H I
• a tree whose root has an ordered pair
of children, each of which is a binary
tree
 Representation of binary tree
//Definition of the node

struct node{
int data;
node *left;
node *right;
};
Applications:
• arithmetic expressions
• decision processes
• searching
Arithmetic Expression Tree
• Binary tree associated with an arithmetic expression
• internal nodes: operators
• external nodes: operands
• Example: arithmetic expression tree for the expression (2  (a - 1) + (3  b))

 

2 - 3 b

a 1
Decision Tree
• Binary tree associated with a decision process
• internal nodes: questions with yes/no answer
• external nodes: decisions
• Example: dining decision
Want a fast meal?

Yes No

How about coffee? On expense account?

Yes No Yes No
Starbucks Spike’s Al Forno Café Paragon
Full Binary Tree
• A full binary tree of a given height h has 2h+1–1
nodes.
• Height 3 full binary tree…
Labeling Nodes In A Full Binary Tree
• Label the nodes 1 through 2h+1 – 1.
• Label by levels from top to bottom.
• Within a level, label from left to right.
1

2 3

4 5 6 7
8 9 10 11 12 13 14 15
Node Number Properties
• Parent of node i is node i / 2, unless i = 1.
• Node 1 is the root and has no parent.

2 3

4 5 6 7
8 9 10 11 12 13 14 15
Node Number Properties
• Left child of node i is node 2i, unless 2i > n, where n
is the number of nodes.
• If 2i > n, node i has no left child.
1

2 3

4 5 6 7
8 9 10 11 12 13 14 15
Node Number Properties
• Right child of node i is node 2i+1, unless 2i+1 > n,
where n is the number of nodes.
• If 2i+1 > n, node i has no right child.
1

2 3

4 5 6 7
8 9 10 11 12 13 14 15
Full Binary Tree
• Level k has 2k nodes, so 2h leaves
• In a tree of height h.
• No of internal nodes = 1+2+22+…. +2h-1 = 2h - 1
• No internal nodes = no of leaves-1
• Total no. of nodes is n = 2h+1-1
• In a tree of n nodes
𝑛+1
No of leaves =
2
𝑛+1
Height: ℎ = log 2 = log 2 (𝑛𝑜 𝑜𝑓 𝑙𝑒𝑎𝑣𝑒𝑠)
2
Binary Tree
• A binary tree can be obtained from an full binary
tree by pruning.

24
Minimum height of a binary tree
• A binary tree of height h has
• At most 2k nodes at level k
• At most 1+2+22+…. +2h = 2h+1-1 nodes
• If the tree has n nodes then
• n <= 2h+1-1
log2 (𝑛+1)
• Hence ℎ ≥
2
Maximum height of a binary tree
• A binary tree of n nodes has Skewed Binary Tree
height at most n-1
A A
• This is obtained when every
node (except the leaf) has
B
exactly one child B

E
26
 Complete Binary Trees
Full Binary Tree: A labeled binary tree containing the labels 1 to n
with root 1, branches leading to nodes labeled 2 and 3, branches from
these leading to 4, 5 and 6, 7, respectively, and so on.

Complete Binary Tree: A binary tree with n nodes and level k is

complete iff its nodes correspond to the nodes numbered from 1 to n in
the full binary tree of level k.

1 1

2 2 3
3

4 5 6 7 4 5 6 7

8 9 10 11 12 13 14 15
8 9
Complete binary tree Full binary tree of depth 3
Examples of the Binary Tree
Skewed Binary Tree Complete Binary Tree

A 1 A
A

B B 2
B C

C
3 D E F G
D

4 H I
E 5
Tree Walks/Traversals
• A way of visiting of all the nodes in a tree in a
specified order.
• Pre order: node, left child, right child
• Post order: left child, right child, node
• In order: left child, node, right child
• Level order

29
Arithmetic Expression Using BT
+ inorder traversal
A/B*C*D+E
infix expression
* E
preorder traversal
+**/ABCDE
* D prefix expression
postorder traversal
AB/C*D*E+
/ C
postfix expression
level order traversal
A B +*E*D/CAB

30
 Inorder Traversal (recursive version)
void inorder(tree_pointer ptr)
/* inorder tree traversal */
{ A/B*C*D+E
if (ptr) {
inorder(ptr->left);
cout<<ptr->data;
indorder(ptr->right);
}
} 31
 Trace Operations of Inorder Traversal
if (ptr) {
Call of inorder Value in root Action Call of inorder Value in root Action
inorder(ptr->left);
cout<<ptr->data; +
indorder(ptr->right);}
1 + 12 NULL 1
2 * 11 C cout
3 * 13A / B * C * D + E NULL * E
4 / 2 * 2 cout
5 A 14 D
17
18 19
6 NULL 15 NULL
* D
5 A cout 14 D cout
7 NULL 16 3
NULL 14
4 / cout 1 + 15 16
cout
8 B 17 / E C
9 NULL 18 4 NULL 11
8 B cout 17 E 12 13 cout
10 NULL 19 A B
NULL
3 * cout 5 8
11 C
6 7 9 10
Preorder Traversal (recursive version)
void preorder(tree_pointer ptr)
/* preorder tree traversal */
{ +**/ABCDE
if (ptr) {
cout<<ptr->data;
preorder(ptr->left);
predorder(ptr->right);
}
}
Postorder Traversal (recursive version)
void postorder(tree_pointer ptr)
/* postorder tree traversal */
{ AB/C*D*E+
if (ptr) {
postorder(ptr->left);
postdorder(ptr->right);
cout<<ptr->data;
}
}
 Binary Search Tree
• Binary search tree
• Every element has a unique key.
• The keys in a nonempty left subtree are smaller than
the key in the root of subtree.
• The keys in a nonempty right subtree are larger than
the key in the root of subtree.
• The left and right subtrees are also binary search trees.

36
Examples of Binary Search Trees

20 30 60

12 25 5 40 70

10 15 22 2 65 80

37
Binary Search Tree Insert
• Insert Keys
6 9 8 11 12 10 7 2 4 5 1 3

2 9

1 4 8 11

3 5 7 10 12

38
Binary Search Tree
• In-order Traversal
1 2 3 4 5 6 7 8 9 10 11 12

2 9

1 4 8 11

3 5 7 10 12

39
 Insert Node in Binary Search Tree

30 30 30

5 40 5 40 5 40

2 2 80 2 35 80

Insert 80 Insert 35

40
Binary Tree Class
class binaryTree
{
public:
bool isEmpty();
void inorderTraversal(); // inorder traversal
void preorderTraversal(); // preorder traversal
void postorderTraversal(); // postorder traversal of the tree
int treeHeight(); // to calculate the height of the tree
int treeNodeCount(); // to count total no of nodes
int treeLeavesCount(); // to count the leaves
void destroyTree(); // to Deallocates the memory space
binaryTree(const binaryTree& otherTree); //copy constructor
binaryTree(); //default constructor
~binaryTree(); //destructor
protected:
node *root;
private:
void copyTree(node* &copiedTreeRoot, node* otherTreeRoot);
void destroy(node* &p);
void inorder(node *p);
void preorder(node *p);
void postorder(node *p);
int height(node *p);
int max(int x, int y);
int nodeCount(node *p);
int leavesCount(node *p);
};
Binary Search Tree
// inherits the binaryTree public/private members

class bSearchTree: public binaryTree

{
public:
bool search(const int&); // Returns true if searchItem is found..
void insert(const int&); // to insert number in the binary search tree..
void deleteNode(const int& key) //Function to delete Item from..
};
Empty Binary Tree
binaryTree::binaryTree() { // Default Constructor
root = NULL;
}

bool binaryTree::isEmpty() { // returns true if tree is empty

return (root == NULL);
}
Other Operations
void binaryTree::inorderTraversal() {
inorder(root); cout<<endl;
}

void binaryTree::preorderTraversal() {
preorder(root); cout<<endl;
}

void binaryTree::postorderTraversal() {
postorder(root); cout<<endl;
}

int binaryTree::treeHeight() {
return height(root);
}

int binaryTree::treeNodeCount() {
return nodeCount(root);
}

int binaryTree::treeLeavesCount() {
return leavesCount(root);
}
Binary Search Tree Insert Operation
• //Function to insert new Item in the binary search
tree.

• //Postcondition: If no node in the binary search

tree has the same data as Item, a node with the
data Item is created and inserted in the binary
search tree.
Insert Operation
• For empty tree root will change its state from NULL.
• So special case for empty tree i.e.

void bSearchTree::insert(int num){

root = 0x0f111
if (!root){
root = new node;
root->data=num;
root->right=root->left=NULL;
return;
}
//other lines of code if tree is not empty…
//search the node …
//add a node after that node…
};
 Search The node (for insertion)
// i.e. to insert num=11 search the node after which it will come.
6
// t points next node t2 previous node...

node *t = root, *t2; 2 9

do {
1 4 8 12
if (t->data == num){
cout<<“Item already in the list."; 3 5 7 10 13
cout<<“Duplicates are not allowed.\n“;
return;
}

t2 = t;

if (num>t->data)
t = t->right;
else
t = t->left;

} while (t!==NULL);
Add node after node (t2).
// The searched node is pointed by t2 6
// add new node after node t2.

if (num > t2->data){ 2 9

t2->right = new node;

t2 = t2->right; 1 4 8 12

} 3 5 7 10 13
else
{
t2->left = new node;
t2 = t2->left;
}

t2->data=num;
t2->right=t2->left=NULL;
 Insertion into A Binary Search Tree
void bSearchTree::insert(int num){
if (!root){ root = new node;
root->data=num;
root->right=root->left=NULL;
return;
}
node *t = root, *t2;
do {
if (t->data == num){
cout<<"The insert item is already in the list ";
cout<<"duplicates are not allowed."<<endl;
return;
}
t2 = t;
if (num>t->data) t = t->right;
else t = t->left;
} while (t);
if (num>t2->data){
t2->right = new node;
t2 = t2->right;
} else {
t2->left = new node;
t2 = t2->left;
}
t2->data=num;
t2->right=t2->left=NULL;
};
 Binary Search Tre-Searching O(h)

//Function to determine if key is in the binary search tree.

//Postcondition: Returns true if key is found in the binary search tree; otherwise,
returns false.

bool bSearchTree::search(const int& key) {

node* current = root;
while (current) {
if (key == current->data) return 1;
if (key < current->data) current = current->left;
else current= current->right;
}
return 0;
}

//end search

50
Binary Search Tree-Delete Operation
• //Function to delete Item from the
binary search tree

• //Postcondition: If a node with the

same data as Item is found, it is
deleted from the binary search tree.
 Delete for a binary search tree
Then node to be delete is/has

• Leaf with no left, right child (45)

• Simply del it

• No left sub-tree (30)

• Place here right sub-tree and del
it.

• No right sub-tree (80)

• Place here left sub-tree and del
it.

• Non-empty left and right subtrees (50)

• Search immediate predecessor
i.e. (48)
• Swap values with it.
• Delete…
Deletion for A Binary Search Tree
1
leaf 30
Node

5 80
T1 T2
1
X 2
1 NULL 2
child
node
X
T1

T2
53
 Deletion for A Binary Search Tree
non-leaf 40 40 40
node
20 60 20 55 20 55

10 30 50 70 10 30 50 70 10 30 50 70

45 55 45 60 45 52

52 52
Before deleting 60 Swap 60 with, largest After deleting 60
left sub-tree Item (55) or
smallest right sub-tree item.
54
Searching node for Delete Operation
void deleteNode(const int& key){

node *c = root; // current pointer...

node *p = root; // previous pointer...

bool found = false;

while (c && !found) {
if (c->data == key)
found = true;
else {
p = c;
if(key < c->data) c = c->left;
else c = c->right;
}
}

if(c == NULL){
cout<<"The item not found!\n";
return;
}

// c: the node you want to delete.

// p: the previous node

// Code here to delete the searched node.

}
 Delete Operation (one NULL Child)
// code to delete node like 30 or 53 having no left child.
if (c->right)
{
node * t = c;
if (p->left == c) p->left = c->right;
else p->right = c->right;
delete t;
return;
}
// code to delete node like 80 or 65 having no right child.
node * t = c;
if(p->right == c)
p->right = c->left;
else
p->left = c->left;
delete c;
 Delete Operation (one NULL Child)
// code to delete node like 50 having both right, left child.
if (c->right && c->left) //if right, left both child
{
node * s = c;// actual node that we will swap;
p = c; // previous node to the node to be swapped
c = c->left; // next node during search.
while (c->right){
p = c;
c = c->right;
}
if (s!=p) { //swapping of data;
int dt = c->data;
c->data = s->data;
s->data = dt;

node * t = c;
p->right = c->left; //skipping the node
delete t;
}
else {
node *t = c;
p->left = c->left;
delete t;
}
return;
}
Binary Search Tree Delete Operation
void deleteNode(const int& key){
node *c = root; // current pointer...
node *p = root; // previous pointer...
bool found = false;
while (c && !found) {
if (c->data == key) found = true;
else {
p = c;
if(key < c->data) c = c->left;
else c = c->right;
}
}
if(c == NULL){
cout<<"The item not found!\n";
return;
}
if (c->right && c->left) // IF RIGH AND LEFT BOTH CHILD EXIST
{
node * s = c; // node to be swapped;
p = c; // previous node to the node to be swapped
c = c->left; // actual node to witch "s" will be swapped.
while (c->right){
p = c;
c = c->right;
}
if (s!=p) {
// swapping of data;
int dt = c->data;
c->data = s->data;
s->data = dt;

node * t = c;
p->right = c->left; // skipping the node from the tree.
delete t;
}
else{
node *t = c;
p->left = c->left;
delete t;
}
return;
}
if (c->right)
{
node * t = c;
if (p->left == c) p->left = c->right;
else p->right = c->right;
delete t;
return;
}

node * t = c;
if(p->right == c)
p->right = c->left;
else
p->left = c->left;
delete c;
// else the logic to delete node...
}
 Heap
 A max tree is a tree in which the key value in
each node is no smaller than the key values in
its children. A max heap is a complete binary
tree that is also a max tree.
 A min tree is a tree in which the key value in
each node is no larger than the key values in
its children. A min heap is a complete binary
tree that is also a min tree.
 Operations on heaps
– creation of an empty heap
– insertion of a new element into the heap;
– deletion of the largest element from the heap
60
*Figure 5.25: Sample max heaps (p.219)

[1] [1] [1]

14 9 30

[2] [3] [2] [3] [2]

12 7 6 3 25
[4] [5] [6] [4]
10 8 6 5

Property:
The root of max heap (min heap) contains
the largest (smallest).
*Figure 5.26: Sample min heaps (p.220)

[1] [1] [1]

2 10 11

[2] [3] [2] [3] [2]

7 4 20 83 21
[4] [5] [6] [4]
10 8 6 50
 Data Structures
• unordered linked list
• unordered array
• sorted linked list
• sorted array
• heap

63
*Figure 5.27: Priority queue representations (p.221)

Representation Insertion Deletion

Unordered (1) (n)

array
Unordered (1) (n)
linked list
Sorted array O(n) (1)
Sorted linked O(n) (1)
list
Max heap O(log2n) O(log2n)
 Example of Insertion to Max Heap

20 20 21

15 2 15 5 15 20

14 10 14 10 2 14 10 2

initial location of new node insert 5 into heap insert 21 into heap

65
 Insertion into a Max Heap
void insert_max_heap(element item, int *n)
{
int i;
if (HEAP_FULL(*n)) {
fprintf(stderr, “the heap is full.\n”);
exit(1);
}
i = ++(*n);
while ((i!=1)&&(item.key>heap[i/2].key)) {
heap[i] = heap[i/2];
i /= 2; 2k-1=n ==> k=log2(n+1)
}
heap[i]= item; O(log2n)
} 66
Example of Deletion from Max Heap

remove
20 10 15

15 2 15 2 14 2

14 10 14 10

67
 Deletion from a Max Heap
element delete_max_heap(int *n)
{
int parent, child;
element item, temp;
if (HEAP_EMPTY(*n)) {
fprintf(stderr, “The heap is empty\n”);
exit(1);
}
/* save value of the element with the
highest key */
item = heap[1];
/* use last element in heap to adjust heap
temp = heap[(*n)--];
parent = 1;
child = 2;
68
while (child <= *n) {
/* find the larger child of the current
parent */
if ((child < *n)&&
(heap[child].key<heap[child+1].key))
child++;
if (temp.key >= heap[child].key) break;
/* move to the next lower level */
heap[parent] = heap[child];
child *= 2;
}
heap[parent] = temp;
return item;
}

69
Heap
• Heap
• a min (max) element is deleted. O(log2n)
• deletion of an arbitrary element O(n)
• search for an arbitrary element O(n)

70