12.key
http://people.eng.unimelb.edu.au/tobym
@tobycmurray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
Toby Murray
COMP90038
Algorithms and Complexity
Lecture 12: More Divide-and-Conquer Algorithms
(with thanks to Harald Søndergaard)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Divide and Conquer
• In the last lecture we studied the archetypal divide-
and-conquer sorting algorithms: mergesort and
quicksort.
• We also introduced the powerful master theorem,
providing solutions to a large class of recurrence
relations, for free.
• allows us to quickly determine the complexity of
these divide-and-conquer algorithms
• Now we shall look at tree traversal, and then a final
example of divide-and-conquer, giving a better
solution to the closest-pair problem.
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Binary Trees
• An example of a binary tree, with empty subtrees
marked as ☐
• This tree has height 4, the empty tree having height -1
3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Review of Linked List
Terminology
4
2
node
pointer
(in Java: “reference”)
72 3 5X:
X is (a pointer to) the head node of the list
2Y:
“Y.val” refers to
“Y.next”
refers to
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Tree Terminology
5
root
left
subtree
right
subtree
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Tree Terminology
6
17
t:
t is (a pointer to) the root node of the tree
“t.root” refers to
33
…
33
…… … …
17
t:
“t.left” refers to “t.right”
refers to
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Binary Trees
• An example of a binary tree, with empty subtrees
marked as ☐
• This tree has height 4, the empty tree having height -1
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Empty Nodes
8
38
25
empty trees are
just null pointers
right subtree
is empty
null pointer
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Levels and Height
9
Level 0
Level 1
Level 2
Level 3
Level 4
So the tree has height 4 (its maximum level)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Binary Tree Concepts
• Special trees have their external nodes ☐ ︎only at
level h and h+1 for some h:
10
A full binary tree:
Each node has 0 or 2
(non-empty) children.
A complete tree: Each level
filled left to right.
(Every level except perhaps the
last is completely filled.)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Calculating the Height
• Recursion is the natural way of calculating the height:
11
T:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
• Input size: number n of (internal) nodes (e.g. for T n is 13)
• Number of external nodes always n+1 (e.g. for T x is 14)
• The function HEIGHT makes one tree comparison (is T null/
empty?) per node (internal and external), so altogether 2n +
1 comparisons. T:
Height Complexity
12
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Binary Tree Traversal
• Preorder traversal visits the root, then the left
subtree, and finally the right subtree.
• Inorder traversal visits the left subtree, then the
root, and finally the right subtree.
• Postorder traversal visits the left subtree, the right
subtree, and finally the root.
• Level-order traversal visits the nodes, level by
level, starting from the root.
13
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
14
Call Stack
PREORDERTRAVERSE(17)
Visit order:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
15
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
16
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
17
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
18
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33
PREORDERTRAVERSE(19)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
19
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33
PREORDERTRAVERSE(19)
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
20
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33
PREORDERTRAVERSE(19)
19
PREORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
21
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33
PREORDERTRAVERSE(19)
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
22
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33
PREORDERTRAVERSE(19)
19
PREORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
23
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33
PREORDERTRAVERSE(19)
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
24
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33 19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
25
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33 19
PREORDERTRAVERSE(16)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
26
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33 19
PREORDERTRAVERSE(16)
16
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
27
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33 19
PREORDERTRAVERSE(16)
16
PREORDERTRAVERSE(38)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
28
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33 19
PREORDERTRAVERSE(16)
16 38
PREORDERTRAVERSE(38)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
29
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33 19
PREORDERTRAVERSE(16)
16 38
PREORDERTRAVERSE(38)
(…skipping the calls to
PREORDERTRAVERSE(null)…)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
30
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33 19
PREORDERTRAVERSE(16)
16 38
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
31
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33 19
PREORDERTRAVERSE(16)
16 38
PREORDERTRAVERSE(31)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
32
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33 19
PREORDERTRAVERSE(16)
16 38
PREORDERTRAVERSE(31)
31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
33
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33 19
PREORDERTRAVERSE(16)
16 38
PREORDERTRAVERSE(31)
31
(…skipping the calls to
PREORDERTRAVERSE(null)…)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
34
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33 19
PREORDERTRAVERSE(16)
16 38 31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
35
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17
PREORDERTRAVERSE(33)
33 19 16 38 31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
36
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17 33 19 16 38 31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
37
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17 33 19 16 38 31
PREORDERTRAVERSE(48)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
38
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17 33 19 16 38 31
PREORDERTRAVERSE(48)
48
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
39
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17 33 19 16 38 31
PREORDERTRAVERSE(48)
48
PREORDERTRAVERSE(11)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
40
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17 33 19 16 38 31
PREORDERTRAVERSE(48)
48
PREORDERTRAVERSE(11)
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
41
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17 33 19 16 38 31
PREORDERTRAVERSE(48)
48
PREORDERTRAVERSE(11)
11
(…skipping the calls to
PREORDERTRAVERSE(null)…)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
42
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17 33 19 16 38 31
PREORDERTRAVERSE(48)
48 11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
43
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17 33 19 16 38 31
PREORDERTRAVERSE(48)
48 11
PREORDERTRAVERSE(14)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
44
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17 33 19 16 38 31
PREORDERTRAVERSE(48)
48 11
PREORDERTRAVERSE(14)
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
45
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17 33 19 16 38 31
PREORDERTRAVERSE(48)
48 11
PREORDERTRAVERSE(14)
14
(…skipping the calls to
PREORDERTRAVERSE(null)…)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
46
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17 33 19 16 38 31
PREORDERTRAVERSE(48)
48 11 14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
47
Call Stack
PREORDERTRAVERSE(17)
Visit order: 17 33 19 16 38 31 48 11 14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
48
Call Stack
Visit order: 17 33 19 16 38 31 48 11 14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
49
Visit order:
Call Stack
INORDERTRAVERSE(17)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
50
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
51
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
INORDERTRAVERSE(19)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
52
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
INORDERTRAVERSE(19)
INORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
53
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
INORDERTRAVERSE(19)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
54
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
INORDERTRAVERSE(19)
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
55
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
INORDERTRAVERSE(19)
19
INORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
56
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
INORDERTRAVERSE(19)
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
57
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
58
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
59
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
60
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
INORDERTRAVERSE(38)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
61
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
INORDERTRAVERSE(38)
INORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
62
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
INORDERTRAVERSE(38)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
63
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
INORDERTRAVERSE(38)
38
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
64
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
INORDERTRAVERSE(38)
38
INORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
65
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
INORDERTRAVERSE(38)
38
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
66
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
38
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
67
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
38 16
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
68
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
38 16
INORDERTRAVERSE(31)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
69
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
38 16
INORDERTRAVERSE(31)
INORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
70
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
38 16
INORDERTRAVERSE(31)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
71
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
38 16
INORDERTRAVERSE(31)
31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
72
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
38 16
INORDERTRAVERSE(31)
31
INORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
73
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
38 16
INORDERTRAVERSE(31)
31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
74
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33
INORDERTRAVERSE(16)
38 16 31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
75
Visit order:
Call Stack
INORDERTRAVERSE(17)
INORDERTRAVERSE(33)
19 33 38 16 31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
76
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
77
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
78
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
79
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
INORDERTRAVERSE(11)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
80
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
INORDERTRAVERSE(11)
INORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
81
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
INORDERTRAVERSE(11)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
82
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
INORDERTRAVERSE(11)
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
83
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
INORDERTRAVERSE(11)
11
INORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
84
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
INORDERTRAVERSE(11)
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
85
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
86
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
11 48
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
87
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
11 48
INORDERTRAVERSE(14)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
88
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
11 48
INORDERTRAVERSE(14)
INORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
89
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
11 48
INORDERTRAVERSE(14)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
90
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
11 48
INORDERTRAVERSE(14)
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
91
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
11 48
INORDERTRAVERSE(14)
14
INORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
92
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
11 48
INORDERTRAVERSE(14)
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
93
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17
INORDERTRAVERSE(48)
11 48 14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
94
Visit order:
Call Stack
INORDERTRAVERSE(17)
19 33 38 16 31 17 11 48 14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
95
Visit order:
Call Stack
19 33 38 16 31 17 11 48 14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
96
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
97
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
98
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
POSTORDERTRAVERSE(19)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
99
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
POSTORDERTRAVERSE(19)
POSTORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
100
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
POSTORDERTRAVERSE(19)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
101
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
POSTORDERTRAVERSE(19)
POSTORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
102
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
POSTORDERTRAVERSE(19)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
103
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
POSTORDERTRAVERSE(19)
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
104
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
105
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
POSTORDERTRAVERSE(16)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
106
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
POSTORDERTRAVERSE(16)
POSTORDERTRAVERSE(38)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
107
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
POSTORDERTRAVERSE(16)
POSTORDERTRAVERSE(38)
POSTORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
108
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
POSTORDERTRAVERSE(16)
POSTORDERTRAVERSE(38)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
109
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
POSTORDERTRAVERSE(16)
POSTORDERTRAVERSE(38)
POSTORDERTRAVERSE(null)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
110
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
POSTORDERTRAVERSE(16)
POSTORDERTRAVERSE(38)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
111
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
POSTORDERTRAVERSE(16)
POSTORDERTRAVERSE(38)
38
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
112
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
POSTORDERTRAVERSE(16)
38
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
113
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
POSTORDERTRAVERSE(16)
38
POSTORDERTRAVERSE(31)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
114
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
POSTORDERTRAVERSE(16)
38
POSTORDERTRAVERSE(31)
(…skipping the calls to
POSTORDERTRAVERSE(null)…)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
115
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
POSTORDERTRAVERSE(16)
38
POSTORDERTRAVERSE(31)
31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
116
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
POSTORDERTRAVERSE(16)
38 31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
117
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19
POSTORDERTRAVERSE(16)
38 31 16
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
118
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19 38 31 16
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
119
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
POSTORDERTRAVERSE(33)
19 38 31 16 33
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
120
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
19 38 31 16 33
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
121
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
19 38 31 16 33
POSTORDERTRAVERSE(48)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
122
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
19 38 31 16 33
POSTORDERTRAVERSE(48)
POSTORDERTRAVERSE(11)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
123
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
19 38 31 16 33
POSTORDERTRAVERSE(48)
POSTORDERTRAVERSE(11)
(…skipping the calls to
POSTORDERTRAVERSE(null)…)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
124
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
19 38 31 16 33
POSTORDERTRAVERSE(48)
POSTORDERTRAVERSE(11)
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
125
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
19 38 31 16 33
POSTORDERTRAVERSE(48)
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
126
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
19 38 31 16 33
POSTORDERTRAVERSE(48)
11
POSTORDERTRAVERSE(14)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
127
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
19 38 31 16 33
POSTORDERTRAVERSE(48)
11
POSTORDERTRAVERSE(14)
(…skipping the calls to
POSTORDERTRAVERSE(null)…)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
128
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
19 38 31 16 33
POSTORDERTRAVERSE(48)
11
POSTORDERTRAVERSE(14)
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
129
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
19 38 31 16 33
POSTORDERTRAVERSE(48)
11 14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
130
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
19 38 31 16 33
POSTORDERTRAVERSE(48)
11 14 48
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
131
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
19 38 31 16 33 11 14 48
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
132
Visit order:
Call Stack
POSTORDERTRAVERSE(17)
19 38 31 16 33 11 14 48 17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
133
Visit order:
Call Stack
19 38 31 16 33 11 14 48 17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
Using a Stack
• Explicitly maintain a stack of nodes
• In an implementation, the elements placed onto the
stack would not be whole trees, but pointers to the
corresponding internal nodes
134
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
135
Queue:
Traversal order:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
136
Queue: 17
Traversal order:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
137
Queue:
Traversal order:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
138
Queue:
Traversal order: 17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
139
Queue:
Traversal order: 17
33
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
140
Queue:
Traversal order: 17
33 48
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
141
Queue:
Traversal order: 17
48
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
142
Queue:
Traversal order: 17
48
33
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
143
Queue:
Traversal order: 17
48
33
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
144
Queue:
Traversal order: 17
48
33
19 16
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
145
Queue:
Traversal order: 17 33
19 16
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
146
Queue:
Traversal order: 17 33
19 16
48
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
147
Queue:
Traversal order: 17 33
19 16
48
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
148
Queue:
Traversal order: 17 33
19 16
48
11 14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
149
Queue:
Traversal order: 17 33
16
48
11 14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
150
Queue:
Traversal order: 17 33
16
48
11 14
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
151
Queue:
Traversal order: 17 33 48
11 14
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
152
Queue:
Traversal order: 17 33 48
11 14
19 16
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
153
Queue:
Traversal order: 17 33 48
11 14
19 16
38
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
154
Queue:
Traversal order: 17 33 48
11 14
19 16
38 31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
155
Queue:
Traversal order: 17 33 48
14
19 16
38 31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
156
Queue:
Traversal order: 17 33 48
14
19 16
38 31
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
157
Queue:
Traversal order: 17 33 48 19 16
38 31
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
158
Queue:
Traversal order: 17 33 48 19 16
38 31
11 14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
159
Queue:
Traversal order: 17 33 48 19 16
31
11 14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
160
Queue:
Traversal order: 17 33 48 19 16
31
11 14 38
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
161
Queue:
Traversal order: 17 33 48 19 16 11 14 38
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal
Using a Queue
• Replace the stack with a queue
162
Queue:
Traversal order: 17 33 48 19 16 11 14 38 31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem (2D)
Revisited (see Lecture 5)
163
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem
Revisited
• In Lecture 5 we gave a brute-force algorithm for the
closest pair problem: Given n points in the Cartesian
plane, find a pair with minimal distance.
• The brute-force method had complexity Θ(n2). We can
use divide-and-conquer to do better, namely Θ(n log n).
• First, sort the points by x value and store the result in
array byX. Also sort the points by y value and store the
result in array byY.
• Now we can identify the x median, and recursively
process the set PL of points with lower x values, as well
as the set PR with higher x values.
164
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem
Revisited
165
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem
Revisited
166
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem
Revisited
167
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem
Revisited
168
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem
Revisited
169
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem
Revisited
170
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem
Revisited
171
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem
Revisited
• The recursive calls will identify dL, the shortest distance for pairs in
PL, and dR, the shortest distance for pairs in PR.
• Let m be the x median and let d = min(dL,dR). This d is a
candidate for the smallest distance.
• But d may not be the global minimum—there could be some close
pair whose points are on opposite sides of the median line x = m.
• For candidates that may improve on d we only need to look at
those in the band m − d ≤ x ≤ m + d.
• So pick out, from array byY, each point p with x-coordinate
between m−d and m+d, and keep these in array S.
• For each point in S, consider just its “close” neighbours in S.
172
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem
Revisited
• The following calculates the smallest distance
and leaves the (square of the) result in minsq.
• It can be shown that the while loop can
execute at most 5 times for each i value—
see diagram.
173
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
You’re Learning Heaps!
• Next up: Priority queues, heaps and heapsort.
174