BINARY TREES

Module 5
Contents
Binary Trees: Introduction and definition,

Node Representation of Binary Trees,

Internal and External Nodes,

Implicit Array Representation of Binary Trees,

Primitive operations on Binary Tree,

Threaded binary tree,

Binary search tree and its primitive operations,

General Expressions as Trees,

evaluating an expression tree,

constructing a Tree.
DEFINITION
• A tree is a finite set of one or more nodes such that
– There is a specially designated node called root.
– The remaining nodes are partitioned into n >= 0 disjoint set T1,…,Tn,
where each of these sets is a tree.
– T1,…,Tn are called the subtrees of the root
 Introduction
Trees: Unlike Arrays, Linked Lists, Stack and queues, which are
linear data structures, trees are hierarchical data structures.
Tree Vocabulary: The topmost node is called root of the tree. The
elements that are directly under an element are called its children.
The element directly above something is called its parent. For
example, ‘a’ is a child of ‘f’, and ‘f’ is the parent of ‘a’. Finally,
elements with no children are called leaves.
Why Trees?
1. One reason to use trees might be to store
information that naturally forms a hierarchy. For
example, the file system on a computer
2. Trees (with some ordering e.g.,
BST) provide moderate
access/search (quicker than Linked
List and slower than arrays).
3. Trees provide moderate
insertion/deletion (quicker than
Arrays and slower than Unordered
Linked Lists).
4. Like Linked Lists and unlike Arrays,
Trees don’t have an upper limit on
Need for binary trees:
• In C, Binary trees have some exciting and useful
applications which can be implemented.

• With the help of a binary search tree, an element can

be found in a huge set because it is fast and efficient.

• Using binary trees, implementation of heapsort is easy.

• To store information in databases, best way is to

make use of binary trees.
Introduction and Definition
Definition: A binary tree is a tree data structure
in which each parent node can have at most two
children. Each node of a binary tree consists of
three items:
• data item
• address of left child
• address of right child
1. Root:- A root is a node without a
parent. In the above image, 50 is the
root node.
2. Siblings:- Siblings mean that nodes
which have the same parent node. In
the above image, 17 and 72 are
siblings because they have 50 in
common.
3. Internal Node:- Internal Node
means that a node which has at least
a single child. In the above image, 17,
72, 12, 23, 54 are internal nodes.
4. External Node:- External Node
means that a node which has no
children. It is also known as leaf. In the
above image, 67 and 76 are external
nodes.
5. Ancestors:- Ancestors include the
parent, grandparent and so on of a node.
In the above image, the ancestors of 23
are 17 and 50.
6. Descendants:- Descendants are the
opposite of ancestors, It includes the
child, grandchild and so on of a node. In
the above image, the descendants of 17
are 12,23,19,9,14.
7. Edge:- An edge means a connection
between one node to another node.
8. Path:- Path is a combination of nodes
and edges connected with each other. In
the above image, 50 to 19 is a path.
9. Depth:- You can calculate depth by the number of edges from node to the
root of the tree.
10. Height:- Height is the maximum depth of a node.
11. Level:- Level of a node is equal to depth of the node+1.
Types of Binary Trees
1. Full Binary Tree 2. Perfect Binary Tree
A full Binary tree is a special type A perfect binary tree is a type of
of binary tree in which every parent binary tree in which every internal
node/internal node has either two node has exactly two child nodes
or no children. We can also say a and all the leaf nodes are at the
full binary tree is a binary tree in same level.
which all nodes except leaf nodes
have two children.
 3. Complete Binary Tree
A complete binary tree is just like a full binary tree, but with two
major differences
1. Every level must be completely filled
2. All the leaf elements must lean towards the left.
3. The last leaf element might not have a right sibling i.e. a
complete binary tree doesn't have to be a full binary tree.
Properties of Complete Binary
Tree
Max Nodes Min Nodes
Binary Tree 2h+1 - 1 h+1
Full Binary Tree 2h+1 - 1 2h+1
Complete Binary Tree 2h+1 - 1 2h

Max Height Min Height

Binary Tree log2(n+1) - 1 n-1
Full Binary Tree log2(n+1) - 1 (n-1)/2
Complete Binary Tree log2(n+1) - 1 logn
BINARY TREE REPRESENTATION
• The storage representation of binary trees can be classified as
1. Array representation
2. Linked representation.
 Array representation
• A tree can be represented using an
array, which is called sequential
representation.
• The nodes are numbered from 1 to
n, and one dimensional array can
be used to store the nodes.
• Position 0 of this array is left empty
and the node numbered i is
mapped to position i of the array
Implicit Array Representation of Binary Trees
0 1 2 3 4 5 6 7 8
A B C D E F G H I

Case 1:
If a node is in the ith index: A

Left child would be at ((2*i)+1)

Right child would be at ((2*i)+2) B C
Parent would be at floor((i-1)/2)
1 2 3 4 5 6 7 8 9 D E F G
A B C D E F G H I

Case 2: H I
If a node is in the ith index:

Left child would be at (2*i)

Right child would be at ((2*i)+1)
Parent would be floor(i/2)
Implicit Array Representation of Binary Trees
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G - - H I

Case 1:
If a node is in the ith index: A

Left child would be at ((2*i)+1)

B C
Right child would be at ((2*i)+2)
Parent would be at floor((i-1)/2)
1 2 3 4 5 6 7 8 9 10 11 D E F G
A B C D E F G - - H I

Case 2: H I
If a node is in the ith index:

Left child would be at (2*i)

Right child would be at ((2*i)+1)
Parent would be floor(i/2)
Implicit Array Representation of Binary Trees
0 1 2 3 4 5 6 7
A B C D E F G H

Case 1:
If a node is in the ith index: A

Left child would be at ((2*i)+1)

Right child would be at ((2*i)+2) B C
Parent would be at floor((i-1)/2)
1 2 3 4 5 6 7 8 D E F G
A B C D E F G H
H
Case 2:
If a node is in the ith index:

Left child would be at (2*i)

Right child would be at ((2*i)+1)
Parent would be floor(i/2)
Implicit Array Representation of Binary Trees
0 1 2 3 4 5 6
A - B - - - C

Case 1:
If a node is in the ith index: A

Left child would be at ((2*i)+1)

Right child would be at ((2*i)+2) B
Parent would be at floor((i-1)/2)

1 2 3 4 5 6 7 C
A - B - - - C

Case 2:
If a node is in the ith index:

Left child would be at (2*i)

Right child would be at ((2*i)+1)
Parent would be floor(i/2)
Implicit Array Representation of Binary Trees
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A - B - - - C - - - - - - - D

Case 1:
If a node is in the ith index: A

Left child would be at ((2*i)+1)

Right child would be at ((2*i)+2) B
Parent would be at floor((i-1)/2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 C
A - B - - - C - - - - - - - D

Case 2: D
If a node is in the ith index:

Left child would be at (2*i)

Right child would be at ((2*i)+1)
Parent would be floor(i/2)
 root
100
Binary Tree Implementation
200 4 40
0
100
#include<stdio.h>
struct node
250 3 0 0 7 300
{
int data; 200 400
struct node *left, *right;
} 0 -1 0 0 10 0
void main()
{ 250 300
struct node *root;
root=0;
root = create();
}
 root
100
Binary Tree Implementation
200 4 40
struct node *create() 0
100
{
struct node *newnode;
250 3 0 0 7 300
int data;
printf("Press 0 to exit"); 200 400
printf("\nPress 1 for new node");
printf("Enter your choice : "); 0 -1 0 0 10 0
scanf("%d", &choice); 250 300
if(choice==0)
else
{ {
return 0; newnode = (struct node *)malloc(sizeof(struct
} node));
printf("Enter the data:");
scanf("%d", &newnode->data);
printf("Enter the left child of %d", data);
newnode->left = create();
printf("Enter the right child of %d", data);
newnode->right = create();
return newnode;
 Binary Tree Implementation
else
struct node *create()
{
{ newnode = (struct node *)malloc
struct node *newnode; (sizeof(struct node));
int data; printf("Enter the data:");
printf("Press 0 to exit"); scanf("%d", &newnode->data);
printf("\nPress 1 for new node");
printf("Enter your choice : "); printf("Enter the left child of %d", data);
scanf("%d", &choice); newnode->left = create();
if(choice==0)
printf("Enter the right child of %d", data
{
newnode->right = create();
return 0;
} return newnode;
}
}
BINARY TREE TRAVERSALS
• Visiting each node in a tree exactly once is called tree
traversal
• The different methods of traversing a binary tree are:
1. Preorder
2. Inorder
3. Postorder
1. Inorder
• Inorder traversal calls for moving down the
tree toward the left until you cannot go
further. Then visit the node, move one node to
the right and continue. If no move can be
done, then go back one more node.
• Let ptr is the pointer which contains the
location of the node N currently being
scanned.
• L(N) denotes the leftchild of node N and R(N)
is the right child of node N
Recursion function:
• The inorder traversal of a binary tree can be recursively defined as
– Traverse the left subtree in inorder.
– Visit the root.
– Traverse the right subtree in inorder.

void inorder(treepointer ptr)

{ if (ptr)
{ inorder (ptr→leftchild);
printf (“%d”,ptr→data);
inorder (ptr→rightchild);
}
}
2. Preorder
• Preorder is the procedure of visiting a node, traverse left and
continue.
• When you cannot continue, move right and begin again or
move back until you can move right and resume.
• Recursion function:
The Preorder traversal of a binary tree can be recursively defined as
– Visit the root void preorder (treepointer ptr)
{ if (ptr)
– Traverse the left subtree in preorder. { printf (“%d”,ptr→data);
– Traverse the right subtree in preorder preorder (ptr→leftchild);
preorder (ptr→rightchild);
}
}
3. Postorder
• Postorder traversal calls for moving down the tree towards
the left until you can go no further.
• Then move to the right node and then visit the node and
continue.
• Recursion function:
The Postorder traversal of a binary tree can be recursively defined as
 Traverse the left subtree in postorder. void postorder(treepointerptr)
 Traverse the right subtree in postorder. { if (ptr)
{ postorder (ptr→leftchild);
 Visit the root postorder (ptr→rightchild);
printf (“%d”,ptr→data);
}
}
EXAMPLES
The preorder enumeration for the tree is A B D C E G F H I.
The postorder enumeration for the tree is D B G E H I F C A.
The inorder enumeration for the tree is B D A G E C H F I.
PREORDER TRAVERSAL ALGORITHM USING STACKS
TRAVERSAL ALGORITHM USING STACKS

Processed Element
INORDER TRAVERSAL ALGORITHM USING STACKS

2
TRAVERSAL ALGORITHM USING STACKS

Processed Element
TRAVERSAL ALGORITHM USING STACKS
TRAVERSAL ALGORITHM USING STACKS

-
PTR=-500
PTR=-PTR
=-(-500)
=5000

Processed Element
 Binary Tree Traversals
• Arithmetic Expression using binary tree
– inorder traversal (infix expression)
A/B*C*D+E
– preorder traversal (prefix expression)
+**/ABCDE
– postorder traversal
(postfix expression)
AB/C*D*E+
– level order traversal
+*E*D/CAB
Binary Tree Traversals (3/9)
• Inorder traversal (LVR) (recursive version)
output A / B * C * D + E
:
ptr
L
V
R
Binary Tree Traversals (4/9)
• Preorder traversal (VLR) (recursive version)
output + * * / A B C D E
:
V
L
R
 Binary Tree Traversals (5/9)
• Postorder traversal (LRV) (recursive version)
output A B / C * D * E +
:

L
R
V
 Binary Tree Traversals (6/9)
• Iterative inorder traversal
– we use a stack to simulate recursion
5 8
4 11
3 14
2 17
1
A B
/ *C *D E+
L
V

output A /B *C *D + E node
:
Threaded Binary Trees
• Threads
– Do you find any drawback of the above tree?
– Too many null pointers in current representation of binary trees
n: number of nodes
number of non-null links: n-1
total links: 2n
null links: 2n-(n-1) = n+1
– Solution: replace these null pointers with some useful “threads”
Binary Tree
Threaded Binary Trees
• Rules for constructing the threads
– If ptr->left_child is null,
replace it with a pointer to the node that would be visited before ptr in
an inorder traversal that is Inorder Predecessor.
– If ptr->right_child is null,
replace it with a pointer to the node that would be visited after ptr in an
inorder traversal that is Inorder Successor.
Binary Tree
Inorder Traversal- D,B,E,G,A,C,F
 Threaded Binary Trees

• Two additional fields of the node structure, left-thread and right-thread

– If ptr->left-thread=TRUE,
then ptr->left-child contains a thread;
– Otherwise it contains a pointer to the left child.
– Similarly for the right-thread
 Threaded Binary Trees
• A Threaded Binary Tree
root A
t: true  thread
f: false  child dangling
f B f C

dangling D t E t F G
inorder traversal:
H I H D I B E A F C G
Threaded Binary Trees
• If we don’t want the left pointer of H and the right pointer of G to be dangling
pointers, we may create root node and assign them pointing to the root node
Threaded Binary Trees
Inorder traversal of a threaded binary tree
• By using of threads we can perform an inorder traversal without making
use of a stack (simplifying the task)
• Now, we can follow the thread of any node, ptr, to the “next” node of
inorder traversal

1. If ptr->right_thread = TRUE, the inorder successor of ptr is ptr-

>right_child by definition of the threads
2. Otherwise we obtain the inorder successor of ptr by following a path of
left-child links from the right-child of ptr until we reach a node with
left_thread = TRUE
 Threaded Binary Trees
• Finding the inorder successor (next node) of a node
threaded_pointer insucc(threaded_pointer tree){
threaded_pointer temp;
temp = tree->right_child;
tree
if (!tree->right_thread)
while (!temp->left_thread)
temp = temp->left_child;
temp
return temp;
}
Inorder
 Threaded Binary Trees
• Inorder traversal of a threaded binary tree
void tinorder(threaded_pointer tree){
/* traverse the threaded binary tree inorder */

threaded_pointer temp = tree; output H D I B E A F C G

for (;;) { :
temp = insucc(temp);
if (temp==tree) tree
break;
printf(“%3c”,temp->data);
}
}
Time Complexity: O(n)
Threaded Binary Trees

Inserting A Node Into A Threaded Binary Tree

Insert child as the right child of node parent
1. change parent->right_thread to FALSE
2. set child->left_thread and child->right_thread to TRUE
3. set child->left_child to point to parent
4. set child->right_child to parent->right_child
5. change parent->right_child to point to child
Right insertion in a threaded binary tree
void insertRight(threadedPointer Sf threadedPointer r)
{ /* insert r as the right child of s */
threadedpointer temp;
r→rightChild = parent→rightChild;
r→rightThread = parent→rightThread;
r→leftChild = parent;
r→leftThread = TRUE;
s→rightChild = child;
s→rightThread = FALSE;
if (!r→rightThread)
{
temp = insucc(r);
temp→leftChild = r;
}
}
Right insertion in a threaded binary tree
void insertRight(threadedPointer Sf threadedPointer r)
{ /* insert r as the right child of s */
threadedpointer temp;
r→rightChild = parent→rightChild;
r→rightThread = parent→rightThread;
r→leftChild = parent;
r→leftThread = TRUE;
s→rightChild = child;
s→rightThread = FALSE;
if (!r→rightThread)
{
temp = insucc(r);
temp→leftChild = r;
}
}
Binary Search Trees
Definition of 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
 Binary Search Trees
Example: (b) and (c) are binary search trees

medium

smaller larger
 Difference between BT and BST

•A binary tree is simply a tree in which each node can have at most
two children.
•A binary search tree is a binary tree in which the nodes are
assigned values, with the following restrictions :
1. No duplicate values.
2. The left subtree of a node can only have values less than the
node
3. The right subtree of a node can only have values greater than the
node and recursively defined
4. The left subtree of a node is a binary search tree.
5. The right subtree of a node is a binary search tree.
BST Operations
Four basic BST operations
1
Traversal

2
Search
3
Insertion
4
Deletion
BST Traversal
PreorderTraversal
Root Left Right

23 18 12 20 44 35 52
PostorderTraversal
Left Right Root

12 20 18 35 52 44 23
InorderTraversal
Left Root Right

12 18 20 23 35 44 52

Produces a sequenced list

 Binary Search Trees
• Search: Search(25) Search(76)
44

17 88

32 65 97

28 54 82

29 76
80
S
e
a
r
c
h
A
l
g
o
ri
t
h
m
 Searching in BST
• Searching a
binary search
tree

O(h)
BST Insertion Algorithm
Inserting into a binary search tree

An empty tree
 Deletion from BST
• Deletion from a binary search tree
– Three cases should be considered
– case 1. leaf  delete
– case 2. one child  delete and
change the pointer to this child
– case 3. two child  either the
smallest element in the right subtree
or the largest element in the left
subtree
BST Deletion Algorithm
BST Deletion Algorithm
 Binary Search Trees

• Height of a binary search tree

– The height of a binary search tree with n elements can become as
large as n.
– It can be shown that when insertions and deletions are made at
random, the height of the binary search tree is O(log2n) on the
average.
– Search trees with a worst-case height of O(log2n) are called balance
search trees
 Binary Search Trees
• Time Complexity
– Searching, insertion, removal
• O(h), where h is the height of the tree
– Worst case - skewed binary tree
• O(n), where n is the # of internal nodes
• Prevent worst case
– rebalancing scheme
– AVL, 2-3, and Red-black tree
Expression Tree
• The expression tree is a binary tree in which each
internal node corresponds to the operator and
each leaf node corresponds to the operand

• Inorder traversal of expression tree produces infix

version of given postfix expression (same with
postorder traversal it gives postfix expression)
Evaluating an expression tree
Let n be node in expression tree
evaluate(n)
If n is not null then
If n.value is operand then
Return n.value
else
the operator is stored at n.value
A = evaluate(n.left)
B = evaluate(n.right)

// calculate applies operator 't.value'

// on A and B, and returns value
Return calculate(A, B, n.value)
Constructing a Tree
• Now For constructing an expression tree we use a stack. We
loop through input expression and do the following for
every character.

1. If a character is an operand push that into the stack

2. If a character is an operator pop two values from the stack make them
its child and push the current node again.

• In the end, the only element of the stack will be the root of
an expression tree.