UNIT 5

TREES
 Abstract Data Type

 The Data Type which can be represented in the form

of its operation is called as ADT
 Abstract means hide
 what can it do.
ADT
Declaration of data
Declaration of operation
 TREE Representation

Level
PARENT ROOT NODE 0
NODE
CHILD
PARENT
NODE
NODE Level
1

Level
2
CHILD
LEAF NODE
NODE
 Definition of Tree
• A tree is a finite set of one or more nodes
such that:

• There is a specially designated node called

the root.

• The remaining nodes are partitioned into n>=0

disjoint sets T1, ..., Tn, where each of these sets is
a tree.

• We call T1, ..., Tn the subtrees of the root.

 Terminology

• Finite set of elements in tree are called NODES

• Finite set of lines in tree are called as BRANCHES

• Branch directed towards the node is the INDEGREE of the node

• Branch directed away from the node is the OUTDEGREE of the

node

• The degree of a node is the number of sub trees of the node

The degree of root is 3; the degree of child of root is 2.

• INDEGREE of ROOT is ZERO

 Terminology

• All other nodes of the tree will have in degree one and out
degree can be zero or more

• OUTDEGREE of LEAF node is ZERO

• A node that is neither ROOT not LEAF is INTERNAL NODE

• The total number of edges from leaf node to a particular

node in the longest path is called as HEIGHT of that Node.

• In a tree, height of the root node is said to be Height of the

tree.
• A node is called PARENT node if it has successor nodes i.e.
outdegree greater than ZERO
 Terminology

• The node with degree 0 is a leaf or terminal node.

• A node that has sub trees is the parent of the sub trees.

• The sub trees of the node are the children of the node.

• Children of the same parent are siblings.

• The ancestors of a node are all the nodes along the path
from the root to the node.
 A Tree Node

 Every tree node:

 object – useful information

 children – pointers to its children nodes

O O O

O
 Minimum Number Of Nodes

 Minimum number of nodes in a binary tree whose

height is h.
 At least one node at each of first h levels.

minimum number of nodes is

h+1 where h is height
 Maximum Number Of Nodes

 All possible nodes at first h levels are present.

Applicable for
Full Binary tree
Perfect Binary tree

Maximum number of nodes

20 + 21 + ... 2h = 2h+1 − 1
= 2h+1 − 1
 Number Of Nodes & Height

 Let n be the number of nodes in a binary tree whose

height is h.
 The number of nodes doubles every time
the depth increases by 1
 h <= n <= 2h – 1 Ex. 4<=15<=15 if height of leaf is 1.
 If height of a leaf is considered as 0. In this convention,
the above formula becomes 2h+1 – 1
 Number of nodes in any binary tree is 2lh– 1+2rh – 1+1
i.e. height of left sub-tree + height of right sub-tree+1
 Full Binary Tree

 A full binary tree of a given height h has 2h+1 − 1 nodes.

Height 3 full binary tree.

Numbering Nodes In A Full Binary Tree

 Number the nodes 1 through 2h+1 – 1.

 Number by levels from top to bottom.
 Within a level number from left to right.

2 3

4 5 6 7

8 9 10 11 12 13 14 15
 Node Number Properties
1

2 3

4 5 6 7
8 9 10 11 12 13 14 15

 Parent of node i is node i / 2, unless i = 1.

 Node 1 is the root and has no parent.
 Node Number Properties
1

2 3

4 5 6 7
8 9 10 11 12 13 14 15

 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.
 Node Number Properties
1

2 3

4 5 6 7
8 9 10 11 12 13 14 15

 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.
 Complete Binary Tree With n Nodes

A complete binary tree is a binary tree in which every

level, except possibly the last, is completely filled, and
all nodes are as far left as possible.

A binary tree T is full If each node is either a leaf or

possesses exactly two child nodes.
 A binary tree T with n levels is Complete if all levels
except possibly the last are completely full, and the
last level has all its nodes to the left side.
 Example

2 3

4 5 6 7
8 9 10 11 12 13 14 15

 Complete binary tree with 10 nodes.

 Binary Tree Representation

 Array representation.
 Linked representation.
 Array Representation
 Number the nodes using the numbering scheme for
a full binary tree. The node that is numbered i is
stored in tree[i].
a1

2 3
b c

4 5 6 7
d e f g
8 9 10
h i j

tree[] a b c d e f g h i j
0 5 10
 Right-Skewed Binary Tree
a1
b 3
7
c
15
d

tree[] a - b - - - c - - - - - - - d
0 5 10 15

 To represent a binary tree of depth 'n' using

array representation, we need one
dimensional array with a maximum size of
2n+1 - 1.
 Linked Representation

 Each binary tree node is represented as an

object whose data type is BinaryTreeNode.
 The space required by an n node binary tree is n
* (space required by one node).
 The Class BinaryTreeNode

Class BinaryTreeNode
{
<type of data> Object element;
BinaryTreeNode *leftChild; // left subtree
BinaryTreeNode *rightChild;// right subtree
// constructors and any other methods
// come here
};
 Linked Representation Example

root a

b c

d e

g
f
Left Child
element h
rightChild
 Binary Tree Traversal

 Many binary tree operations are done by

performing a traversal of the binary tree.
 In a traversal, each element of the binary tree is
visited exactly once.
 It is used to display tree.
 Tree Traversal

 Three methods of Traversal

 Preorder
 Postorder
 Inorder

 PREorder:
 visit the root
 Traverse left subtree
 Traverse right subtree
 Tree Traversal

 POSTorder
 Traverse left subtree
 Traverse right subtree
 visit the root

 Inorder
 Traverse left subtree
 visit the root
 Traverse right subtree
 Pre-Order Traversal

B E

C D F

A B C D E F
 In-Order Traversal

B E

C D F

C B D A E F
 Post-Order Traversal

B E

C D F

CDB F E A
 Breadth first Traversal

B C

D E F G

A B C D E F G
Find Inorder, Preorder and Postorder traversal of given
example.
Output:

Inorder Output : D → B → E → A → F → C → G
Preorder Output : A → B → D → E → C → F → G
Postorder Output : D → E → B → F → G → C → A
Find Inorder, Preorder and Postorder traversal of given
example.
Output:

(a) Inorder (Left, Root, Right) : 4 2 5 1 3

(b) Preorder (Root, Left, Right) : 1 2 4 5 3
(c) Postorder (Left, Right, Root) : 4 5 2 3 1
 Binary Search Trees

• Ordered data stored in Array will have efficient

search algorithms but inefficient insertion and
deletion

• Linked list storage will increase efficiency of

insertion and deletion but search will always
be sequential as you always have to start from
ROOT node
Properties of Binary Search Trees

• All items in left sub tree are less than

root

• All items in right sub tree are greater

than or equal to root

• Each sub tree is itself a binary search

tree
Is this Binary Search Tree

17

6 19
Is this Binary Search Tree

17

6 19

3 14
Is this Binary Search Tree

17

19

22
Is this Binary Search Tree

17

22 19
Is this Binary Search Tree

17

6 11
Is this Binary Search Tree

17

6 19

11 15
Is this Binary Search Tree

17

6 19

3 22
 Insertion in BST

17

6 19

4 15

Add node - 2
 Insertion in BST

17

6 19

4 15

2
 Insertion in BST

17

6 19

4 15

Add node - 22
 Insertion in BST

17

6 19

4 15
22
 Insertion

 Algorithm addBST (root, newnode)

If (empty)
Set root to newnode
Return newnode
End if
If (newnode < root)
Return addBST (left sub tree, newnode)
Else
Return addBST (right sub tree, newnode)
End if
End addBST
 Deleting from BST

• If the node doesn’t have children's then just delete the

reference for this node from its parent and recycle the
memory

• If the node has only right sub tree then

Simply attach right subtree to delete's nodes parent

• If the node has only left sub tree then

Simply attach left subtree to delete's nodes parent
 Deleting from BST

• If the node has left and right subtree then

• Find largest node from left subtree and
replace that with node we have to delete
OR
• Find smallest node from right subtree and
replace that with node we have to delete
 BST Operations: Removal

▪ removes a specified item from the BST and adjusts

the tree uses a binary search to locate the target item:
starting at the root it probes down the tree till it finds
the target or reaches a leaf node (target not in the tree)
▪removal of a node must not leave a ‘gap’ in the tree,
 Removal in BST - Pseudocode

method remove (key)

I if the tree is empty return false
II Attempt to locate the node containing the target using the
binary search algorithm
if the target is not found return false
else the target is found, so remove its node:
Case 1: if the node has 2 empty subtrees
replace the link in the parent with null

Case 2: if the node has a left and a right subtree

- replace the node's value with the max value in the
left subtree
- delete the max node in the left subtree
 Removal in BST - Pseudocode

Case 3: if the node has no left child

- link the parent of the node
- to the right (non-empty) subtree

Case 4: if the node has no right child

- link the parent of the target
- to the left (non-empty) subtree
 Removal in BST: Example

Case 1: removing a node with 2 EMPTY SUBTREES

parent 7

cursor 5 9

4 6 8 10

7
Removing 4replace the
link in the parent with
5 9
null
6 8 10
 Removal in BST: Example

Case 2: removing a node with 2 SUBTREES

- replace the node's value with the max value in the left subtree
- delete the max node in the left subtree
What other element
Removing 7 can be used as
cursor replacement?
cursor

7 6

5 9 5 9

4 6 8 10 4 8 10
 Removal in BST: Example

Case 3: removing a node with 1 EMPTY SUBTREE

the node has no left child:
link the parent of the node to the right (non-empty) subtree

parent
parent
7 7
cursor
5 9 cursor 5 9

6 8 10 6 8 10
 Removal in BST: Example

Case 4 : removing a node with 1 EMPTY SUBTREE

the node has no right child:
link the parent of the node to the left (non-empty) subtree
Removing 5
parent
parent

7 cursor 7
cursor
5 9 5 9

4 8 10 4 8 10
 Threaded Binary Tree

 A Threaded Binary Tree is a binary tree in which every node that

does not have a right child has a THREAD (in actual sense, a link) to
its INORDER successor.

 Left thread to its INORDER Predecessor

 By doing this threading we avoid the recursive method of traversing

a Tree, which makes use of stacks and consumes a lot of memory

and time. The node structure for a threaded binary tree varies a bit.
 Binary trees have a lot of wasted space: the leaf
nodes each have 2 null pointers

 We can use these pointers to help us in inorder

traversals

 We have the pointers reference to the next node in

an inorder traversal; called threads

 We need to know if a pointer is an actual link or a

thread, so we keep a boolean for each pointer
 Threaded Binary Tree
 A binary tree is threaded by making all right
child pointers that would normally be null, point
to the inorder successor of the node

 Node structure:

class Node
{
int value;
Node *left, *right;
boolean leftThread, rightThread;
}
Threaded Binary Tree Example

3 8

1 5 7 11

9 13
 Threaded Tree Traversal
64
Output
6 1

3 8

1 5 7 11

9 13

Start at leftmost node, print it

 Threaded Tree Traversal
65
Output
6 1
3

3 8
1 5 7 11
9 13
Follow thread to right, print node
 Threaded Tree Traversal
66
Output
6 1
3
5
3 8
1 5 7 11
9 13
Follow link to right, go to
leftmost node and print
 Threaded Tree Traversal
67
Output
6 1
3
5
3 8 6

1 5 7 11
9 13
Follow thread to right, print node
 Threaded Tree Traversal
68
Output
6 1
3
5
3 8 6
7
1 5 7 11
9 13
Follow link to right, go to
leftmost node and print
 Threaded Tree Traversal
69
Output
6 1
3
5
3 8 6
7
1 5 7 11 8

9 13
Follow thread to right, print node
 Threaded Tree Traversal
70
Output
6 1
3
5
3 8 6
7
1 5 7 11 8
9

9 13
Follow link to right, go to
leftmost node and print
8/8/02 Amir Kamil
 Threaded Tree Traversal
71
Output
6 1
3
5
3 8 6
7
1 5 7 11 8
9
11
9 13
Follow thread to right, print node
 Threaded Tree Traversal
72
Output
6 1
3
5
3 8 6
7
1 5 7 11 8
9
11
9 13 13

Follow link to right, go to

leftmost node and print
 Create threaded Binary tree

1. 20, 10,30,5,16,14,17,15

2. F,B,G,A,D,I,C,E,H
Solution:
 Applications of Tree

1. Searching becomes easy

2. Compilers- Syntax tree
3. Directory/Folder
4. Networking-Routing
5. Gaming