0% found this document useful (0 votes)

16 views141 pages

Unit 4 - Tree

Unit 4 focuses on trees as non-linear data structures, covering their basic terminology, representations, and various types such as binary trees and binary search trees. It discusses applications of trees in programming, database search optimization, and data manipulation. The unit also details tree properties, traversal methods, and comparisons between binary trees and binary search trees.

Uploaded by

pratikgorakhdhotre

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

16 views141 pages

Unit 4 - Tree

Uploaded by

pratikgorakhdhotre

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 141

Unit 4- Tree

Ms. S. L. Sonawane

[1] Thareja
2/20/2025 DSA- Unit 2 by Ms. S. L. Sonawane 1
UNIT 4 – Tree

● Concept of Non-Linear data Structures

● Tree:
○ Basic terminology,Representation of trees
○ Binary Tree: ADT, Properties and its representation
○ Binary tree traversals (recursive and non-recursive) and
operations
○ Binary search tree: Definition, Operations
○ Heaps: Priority Queue, Max and Min heap, operations on
heap.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 2

UNIT 4 – Tree

● Computer programming
● improve database search times (binary search trees, AVL trees,
red black trees)
● Game programming (minmax trees, decision trees, path
finding trees)
● 3D graphics programming (binary trees, quadtrees, octrees)
● Arithmetic scripting languages (arithmetic precedence trees)
● data compression (Huffman trees)
● file systems (btrees, sparse indexed trees, trie trees).

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 3

UNIT 4 – Non-linear Data Structure

● Represent the data containing hierarchical or network

relationship between the elements.
● every data element may have more than one predecessor as
well as successor. Elements do not form any particular linear
sequence.
● capable of expressing more complex relationships than linear
data structures

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 4

UNIT 4 – Non-linear Data Structure

● Uses of trees
○ Manipulating hierarchical data
○ Making information easily searchable
○ Manipulating sorted lists of data

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 5

UNIT 4 – Non-linear Data Structure

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 6

UNIT 4 – Tree

● degree of a node is the

number of subtrees of the
node. degree of A is 3, of
C is 1, and of F is zero.
● degree of a tree is the
maximum degree of the
nodes in the tree.
● A node with degree zero is
a leaf or terminal node.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 7

UNIT 4 – Tree

● Children of the same parent

are siblings.
● D is the grandparent of M
● The ancestors of a node are
all the nodes along the path
from the root to the node. For
example, the ancestors of M
are A, D, and H.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 8

UNIT 4 – Tree

● the descendants of a node are all

the nodes that are in its subtrees.
For example, £, F, K, and E are
the descendants of B.
● level of a node by initially
letting the root be at level one.
● The height or depth of a tree is Path: A sequence of consecutive
edges
the maximum level of any node Indegree of node: no. of edges
arriving at that node
in the tree.
Outdegree of node: no.of edges
leaving that node
2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 9
UNIT 4 – Representation of Tree

● List Representation
● Left Child-Right Sibling Representation
● Representation As A Degree Two Tree

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 10

UNIT 4 – Representation of Tree

● List Representation:
information in the root node
comes first, followed by a list of
the subtrees of that node.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 11

UNIT 4 – Representation of Tree

● Left Child-Right Sibling Representation

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 12

UNIT 4 – Representation of Tree

● Representation As A Degree
Two Tree: we simply rotate the
left child-right sibling tree
clockwise by 45 degrees.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 13

UNIT 4 – Representation of Tree

Convert the general tree in Fig. 7.44

into its corresponding binary tree.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 14

Binary tree

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 15

Properties of a Binary tree

● Every binary tree with n elements, n>0, has exactly n-1 edges
● A binary tree of height h, h>=0, has at least h, and atmost (2^h)-1
elements in it.
● The height of a binary tree that contains n, n>=0, elements is at
most n and at least log(n+1)

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 16

Binary tree

● Full binary tree contains exactly (2^h)-1 elements

● Complete binary tree satisfies two properties:
○ every level, except the last level is completely filled.
○ all nodes appear from left to right

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 17

Binary tree

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 18

Binary tree

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 19

Representation of Binary tree

Array Based Representation

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 20

Representation of Binary tree

Array Based Representation

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 21

Representation of Binary tree

Array Based Representation

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 22

Representation of Binary tree

Array Based Representation

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 23

Representation of Binary tree

Array Based Representation

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 24

Representation of Binary tree

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 25

Representation of Binary tree

Linked Representation

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 26

Representation of Binary tree

Linked Representation

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 27

Representation of Binary tree

Linked Representation:
The merits of representing binary trees through liked representations
are as follows:
1. The drawbacks of the sequential representation are overcome in
this representation. We may or may not know the tree depth in
advance. In addition, for unbalanced trees, the memory is not wasted.
2. Insertion and deletion operations are more efficient in this
representation.
3. It is useful for dynamic data.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 28

Representation of Binary tree

Linked Representation:
The demerits of representing binary trees through linked
representation are as follows:
1. In this representation, there is no direct access to any node. It has
to be traversed from the root to reach to a particular node.
2. As compared to sequential representation, the memory needed per
node is more. This is due to two link fields (left child and right child
for binary trees) in the node.
3. The programming languages not supporting dynamic memory
management would not be useful for this representation.
2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 29
Binary tree Traversals

Preorder - DLR
Inorder- LDR
Postorder - LRD
Level Order - Levelwise from left to right

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 30

Binary tree Traversals

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 31

Binary tree Traversals

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 32

Binary tree Traversals

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 33

Binary tree Traversals

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 34

Binary tree Traversals

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 35

Binary tree Traversals

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 36

Binary tree Traversals

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 37

Binary tree Traversals

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 38

Binary tree Traversals

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 39

Binary tree Traversals

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 40

Binary tree Traversals

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 41

Binary Search tree

● Sequential search with O(n) searches

● Binary search with O(log n) searches.
● If the list is an ordered list stored in a
contiguous sequential storage, the binary
search is faster.
● Though the list is stored, if it is stored in a linked
list, the binary search cannot work as it does not
support direct access.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 42

Binary Search tree

● On the other hand, in a linked organization, we

need only a few pointer manipulations for
insertion and deletions.
● If so, we can then find an implementation for an
ordered list where we can search quickly (as
with binary search) and insert or delete
elements quickly (as with linked list).
● A binary tree provides an excellent solution to
this problem.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 43

Binary Search tree

● We can make entries of an ordered list into the

nodes of a binary tree. We can search a target key
in O(log n) steps, and in addition, we can insert
and delete the key in time O(log n).
● The binary search tree (BST) is a binary tree with
the property that the value in a node is greater
than any value in a node’s left subtree and less
than any value in the node’s right subtree.
● This property guarantees fast search time
provided the tree is relatively balanced.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 44

Binary Search tree

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 45

Binary Search tree

● Searching a key
● Inserting a key
● Deleting a key
● Traversing the tree

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 46

Binary Search tree

Esha, Beena, Deepa, Gilda, Amit

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 47

Binary Search tree

Build a BST from the following set of elements—100,

50, 200, 300, 20, 150, 70, 180, 120, 30—and traverse
the tree built in inorder, postorder, and preorder

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 48

Binary Search tree : Deleting a node

1. X is a leaf node.
2. X has one child.
3. X has both child nodes.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 49

Binary Search tree : Deleting a node

2. X has one child.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 50

Binary Search tree : Deleting a node

3. X has both child nodes : X is replaced with inorder

successor

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 51

Binary Search tree Operations

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 52

Binary Search tree Operations

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 53

Binary Search tree Operations

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 54

Binary Search tree Operations

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 55

Binary Search tree Operations

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 56

Binary Search tree Operations

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 57

Binary Search tree Operations

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 58

Binary Search tree Operations

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 59

Binary Search tree Operations

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 60

Comparison of Binary tree and BST

● Both of them are trees with degree two, that is, each
node has utmost two children. This makes the
implementation of both easy.
● The BST is a binary tree with the property that the
value in a node is greater than any value in a node’s
left subtree and less than any value in a node’s right
subtree.
● The BST guarantees fast search time provided the
tree is relatively balanced, whereas for a binary tree,
the search is relatively slow.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 61

Construction of Expression Tree

(Scan the postfix expression from left to right.)

1. Get one token from expression E.
2. Create a node say curr for it.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 62

Construction of Expression Tree

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 63

Construction of Expression Tree

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 64

Construction of Expression Tree

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 65

Construction of Expression Tree

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 66

Game Tree

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 67

m-way Search Tree

● Concept is similar to normal binary search trees, but

M-way search trees can store more than one key
values in a single node
● M-way search tree has M – 1 values per node and
M sub trees. In such a tree, M is called the degree
of the tree.

● Note that in a binary search tree M = 2, so it has one

value and two sub-trees.
● 2-3 Tree Link: Virtual Labs
●

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 68

m-way Search Tree

Here M = 3. So a
node can store a
maximum of two key
values and can
contain pointers to
2/20/2025 three sub-trees. 69
IOC-DS- Unit 1 by Ms. S. L. Sonawane
m-way Search Tree

● it is not compulsory that every node has exactly

M–1 values and M sub trees.

4 way tree

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 70

Heap

● In practice, BSTs are rarely used to sort data.

● In case there is a fixed amount of data and
sorting does not need to take place until all the
data is collected, the data can be placed in an
array and sorted using the quicksort algorithm.
● On the other hand, when the data must be
simultaneously inserted and sorted, there is a
data structure which, in practice works more
efficiently than BSTs, known as heaps

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 71

Heap

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 72

Heap

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 73

Heap

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 74

Heap

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 75

Heap

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 76

Heap
8,20,9,4,15,10,7,22,3,12

08 08 20 20 20

20 08 08 09 08 09

20 20 04

08 09 15 09

04 15 04 08
IOC-DS- Unit 1 by Ms. S. L. Sonawane 77
Heap
20 20

15 09 15 10

04 08 10 04 08 09

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 78

Heap

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 79

Heap

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 80

Heap

Hence, the complexity of the insertion function is O(log n).

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 81
Heap
44,33,11,55,77,90,60,40,99,22,88,66

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 82

Heap

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 83

Heap

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 84

Heap -Deletion of Element

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 85

Heap -Deletion of Element

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 86

Heap -Deletion of Element

Hence, the complexity of a deletion is O(log n).

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 87
Heap -Deletion of Element

Hence, the complexity of a deletion is O(log n).

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 88
Heapsort
The steps for building heap sort are as follows:
1. Build the heap tree.
2. Start deleteHeap operations, storing each deleted
element at the end of the heap array

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 89

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 90

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 91

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 92

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 93

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 94

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 95

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 96

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 97

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 98

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 99

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 100

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 101

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 102

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 103

Heapsort

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 104

Priority Queue
● Similar to queue
● While the higher priority elements are added at
the front of the queue, elements with lower
priority are added at the rear.
● Implementation of priority queue using linear
array, but we should consider the time required to
insert an element in an array and then sort it.
● We need O(n) time to insert an element and at
least O( n log n) time to sort the array.
● Therefore, a better way to implement a priority
queue is by using a binary heap which allows
both enqueue and dequeue of elements in O(log
n)
2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 105
Graph

Graphs as non-linear data structures represent the

relationship among data elements, having more
than one predecessor and/or successor. A graph G
is a collection of nodes (vertices) and arcs joining a
pair of the nodes (edges). Edges between two
vertices repre sent the relationship between them.
For finite graphs, V and E are finite. We can denote
the graph as G = (V, E).

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 106

REPRESEnTATion of GRAPHS
Adjacency matrix (sequential representation)
2. Adjacency list (linked representation)

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 107

REPRESEnTATion of GRAPHS

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 108

REPRESEnTATion of GRAPHS

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 109

REPRESEnTATion of GRAPHS

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 110

REPRESEnTATion of GRAPHS

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 111

REPRESEnTATion of GRAPHS

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 112

REPRESEnTATion of GRAPHS
Linked representation (adjacency list) of a graph has an
advantage of space complexity when a graph is sparse
but does not provide direct access. The probable
disadvantage of adjacency list is that it does not allow
direct access, and hence, we cannot quickly determine
whether an edge between any two vertices is incident or
not.
The adjacency list representation is usually preferred as
it provides a compact way to represent them. For dense
graphs, adjacency matrix representation may be
preferred since |E| is closer to V2 and when we also
want fast access to information such as whether the
edge2/20/2025
between any two vertices
IOC-DS- Unit 1 by Ms. S. L.is incident or not, the113
Sonawane
GRAPH TRAvERSAL
depth-first tra versal
breadth-first traversal.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 114

GRAPH TRAvERSAL
In DFS, as the name indicates, from the currently visited
vertex in the graph, we keep searching deeper whenever
possible. All the vertices are visited by processing a
vertex and its descendents before processing its
adjacent vertices. This procedure can be writ ten either
recursively or non-recursively. For recursive code, the
internal stack would be used, and for non-recursive
code, we would use a stack.

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 115

GRAPH TRAvERSAL

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 116

GRAPH TRAvERSAL

2/20/2025 IOC-DS- Unit 1 by Ms. S. L. Sonawane 117

GRAPH TRAvERSAL

Let us initiate a traversal from the vertex 1. The

order of traversal will be 1, 2, 4, 8, 5, 6, 3, 7.
Another possible traversal could be 1, 3, 7, 8, 6,
5, 2, 4. O(n + e) time is required by the DFS for
adjacency list representation and O(n2) for
adjacency matrix representation.