DATA

STRUCTURES

MAHESH GOYANI
MAHATMA GANDHI INSTITUE OF TECHNICAL EDUCATION & RESEARCH CENTER
mgoyani@rediffmail.com

(C) GOYANI MAHESH 1

BINARY TREE

(C) GOYANI MAHESH 2

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 sub trees.

 A Binary Tree With n nodes, n>0 has exactly n-1 edges.

 A Binary tree of depth d, d>0 has at least d and at most 2d – 1 nodes

 If a binary tree contains n node at level l, than it contains at most 2n
nodes at level l+1

(C) GOYANI MAHESH 3

LEVEL OF BINARY TREE

 Root has level 0,

 Level of any other node is one more than the level of its parent

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

(C) GOYANI MAHESH 4

Array Representation

 Suppose a binary tree T of depth d then at most 2 d-1 nodes can be there in T.
So the array of size “SIZE” is used to represent the binary tree.
 For depth 3,
SIZE = (23-1)= 7, so A[7] is enough to store the tree

A 0

1 B 2 C

3 D E 4 5 G 6

A[ ] A B C D E G
[0] [1] [2] [3] [4] [5] [6]

(C) GOYANI MAHESH 5

 The father of a node having index n can be obtained by (n-1)/2. For example to find the
father of D, Index of D is 3. Then the father node can be obtained
= (3-1) / 2
=2/2
= 1, i.e, A[1] is father of D, that is B.

The left child of a node having index n can be obtained by (2n + 1). For example to find the
left child of C, index of C = 2
= (2*2 + 1)
=5, i.e A[5] is Left child of C, that is NULL

The Right child of a node having index n can be obtained by (2n + 2). For example to find
the Right child of B, index of B = 1
= (2*1 + 2)
=4, i.e A[4] is Left child of C, that is E

Left and Right brother (Siblings) of node having index n are at location n-1 and n+1
respectively.

(C) GOYANI MAHESH 6

Linked List Representation

LChild DATA RChild

B NULL
C

NULL E NULL NULL F NULL

NULL D NULL

(C) GOYANI MAHESH 7

Node Creation

LChild ROOT RChild

Struct node
{
int ROOT;

ROOT Struct node *LChild;

Struct node *RChild;
};

LChild RChild

(C) GOYANI MAHESH 8

 If a binary tree has only LEFT sub tree, then it is called Left Skewed Binary Tree
 If a binary tree has only RIGHT sub tree, then it is called Right Skewed Binary Tree

X A

LEFT RIGHT
Y SKEWED SKEWED B

A C
Z

B C

BINARY
D E TREE F

G H I

(C) GOYANI MAHESH 9

BINARY TREE

root

B C

D E F

G H I

Left sub tree Right sub tree

(C) GOYANI MAHESH 10

BINARY TREE

Recursive Definition

A
root

B C

D E F

Left sub tree G H I

Right sub tree

(C) GOYANI MAHESH 11

BINARY TREE

Recursive Definition

B C
root

D E F

G H I

Left sub tree

(C) GOYANI MAHESH 12

BINARY TREE

Recursive Definition

B C
root

D E F

G H I

Left sub tree Right sub tree

(C) GOYANI MAHESH 13

NOT A TREE

B C

D E F

G H I

(C) GOYANI MAHESH 14

NOT A TREE

B C

D E F

G H I

(C) GOYANI MAHESH 15

NOT A TREE

B C

D E F

G H I

(C) GOYANI MAHESH 16

OPERATION 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 father of p

 brother(p) returns brother of p.

 info(p) returns content of the node.

 In order to construct a binary tree, the following can be useful:

 setLeft(p,x) creates the left child node of p. The child node contains the info ‘x’.

 setRight(p,x) creates the right child node of p. The child node contains the info ‘x’.

(C) GOYANI MAHESH 17

APPLICATION OF BINARY TREE

 A binary tree is a useful data structure when two-way decisions must be

made at each point in a process.
 For example, suppose we wanted to find all duplicates in a list of
numbers:

14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

 One way of finding duplicates is to compare each number with all those
that precede it.

14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 18

CREATION OF BINARY TREE

 The first number in the list is placed in a node that is designated as the root
of a binary tree.

 Initially, both left and right sub trees of the root are empty.

 We take the next number and compare it with the number placed in the root.

 If it is the same then we have a duplicate.

 Otherwise, we create a new tree node and put the new number in it.

 The new node is made the left child of the root node if the second number is
less than the one in the root.

 The new node is made the right child if the number is greater than the one in
the root.

(C) GOYANI MAHESH 19

SEARCHING FOR DUPLICATES

 If the list of numbers is large and is growing, this procedure involves a large
number of comparisons.

 A linked list could handle the growth but the comparisons would still be large.

 The number of comparisons can be drastically reduced by using a binary

tree.

 The tree grows dynamically like the linked list.

(C) GOYANI MAHESH 20

SEARCHING FOR DUPLICATES

14

14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 21
SEARCHING FOR DUPLICATES

15 14

15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 22
SEARCHING FOR DUPLICATES

14

15

15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 23
SEARCHING FOR DUPLICATES

4 14

15

4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 24
SEARCHING FOR DUPLICATES

14

4 15

4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 25
SEARCHING FOR DUPLICATES

9 14

4 15

9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 26
SEARCHING FOR DUPLICATES

14

4 15

9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 27
SEARCHING FOR DUPLICATES

7 14

4 15

7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 28
SEARCHING FOR DUPLICATES

14

4 15

7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 29
SEARCHING FOR DUPLICATES

18 14

4 15

18, 3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 30
SEARCHING FOR DUPLICATES

14

4 15

9 18

18, 3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 31
SEARCHING FOR DUPLICATES

3 14

4 15

9 18

3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 32
SEARCHING FOR DUPLICATES

14

4 15

3 9 18

3, 5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 33
SEARCHING FOR DUPLICATES

5 14

4 15

3 9 18

5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 34
SEARCHING FOR DUPLICATES

14

4 15

3 9 18

5, 16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 35
SEARCHING FOR DUPLICATES

16 14

4 15

3 9 18

16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 36
SEARCHING FOR DUPLICATES

14

4 15

3 9 18

7 16

16, 4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 37
SEARCHING FOR DUPLICATES

4 14

4 15

3 9 18

7 16

4, 20, 17, 9, 14, 5

(C) GOYANI MAHESH 38
SEARCHING FOR DUPLICATES

20 14

4 15

3 9 18

7 16

20, 17, 9, 14, 5

(C) GOYANI MAHESH 39
SEARCHING FOR DUPLICATES

14

4 15

3 9 18

7 16 20

20, 17, 9, 14, 5

(C) GOYANI MAHESH 40
 TRACE OF INSERT

p
17 q 14

4 15

3 9 18

7 16 20

17, 9, 14, 5
(C) GOYANI MAHESH 41
 TRACE OF INSERT

p
17 14

4 q 15

3 9 18

7 16 20

17, 9, 14, 5
(C) GOYANI MAHESH 42
 TRACE OF INSERT

17 14

4 p 15
q
3 9 18

7 16 20

17, 9, 14, 5
(C) GOYANI MAHESH 43
 TRACE OF INSERT

17 14

4 p 15

3 9 q 18

7 16 20

17, 9, 14, 5
(C) GOYANI MAHESH 44
 TRACE OF INSERT

17 14

4 15

3 9 p 18
q
7 16 20

17, 9, 14, 5
(C) GOYANI MAHESH 45
 TRACE OF INSERT

17 14

4 15

3 9 p 18

7 q 16 20

17, 9, 14, 5
(C) GOYANI MAHESH 46
 TRACE OF INSERT

17 14

4 15

3 9 18

7 p 16 20
q
5

17, 9, 14, 5
(C) GOYANI MAHESH 47
 TRACE OF INSERT

17 14

4 15

3 9 18

7 p 16 20

5 q

17, 9, 14, 5
(C) GOYANI MAHESH 48
 TRACE OF INSERT

14

4 15

3 9 18

7 p 16 20

5 node 17

17, 9, 14, 5 p->setRight( node );

(C) GOYANI MAHESH 49

TREE TRAVSERSAL
14 (4,14,15), (4,15,14)
(14,4,15), (14,15,4)
(15,4,14), (15,14,4)
4 15

 Three common ways:

N node

Preorder: (N,L,R)
Inorder: (L,N,R)
Postorder: (L,R,N)
left right
L subtree subtree R

(C) GOYANI MAHESH 50

INORDER

2 8

1 4 7 9

3 5

(C) GOYANI MAHESH 51

INORDER

14

4 15

3 9 18

7 16 20

5 17

Inorder: 3 4 5 7 9 14 15 16 17 18 20

(C) GOYANI MAHESH 52

PREORDER

1
Make Money Fast!

2 5 9
1. Motivations 2. Methods References

6 7 8
3 4
2.1 Stock 2.2 Ponzi 2.3 Bank
1.1 Greed 1.2 Avidity
Fraud Scheme Robbery

(C) GOYANI MAHESH 53

PREORDER

14

4 15

3 9 18

7 16 20

5 17

Preorder: 14 4 3 9 7 5 15 18 16 17 20

(C) GOYANI MAHESH 54

POSTORDER

9
cs16/

8
3 7
todo.txt
homeworks/ programs/
1K

1 2 4 5 6
h1c.doc h1nc.doc DDR.java Stocks.java Robot.java
3K 2K 10K 25K 20K

(C) GOYANI MAHESH 55

POSTORDER

14

4 15

3 9 18

7 16 20

5 17

Postorder: 3 5 7 9 4 17 16 20 18 15 14

(C) GOYANI MAHESH 56

COMPLEXITY

 Average Case : O (log2n)

 Best Case : O (log2n)
 Worst Case : O (log2n)

(C) GOYANI MAHESH 57

BINARY SEARCH TREE

 Binary Search Tree (BST) is a binary tree, which is either empty or satisfies
following properties :
 Every node has a value and no two nodes have the same property
 If there exists a LEFT CHILD then its value is less than the value of
ROOT.
 If there exists a RIGHT CHILD then its value is greater than the value
of ROOT.

50

25 75

20 40 80

30 77 90

(C) GOYANI MAHESH 58