COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 11-2 : Tree Traversals
Giulia Alberini, Fall 2020 Slides adapted from Michael Langer’s
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Tree traversals
Depth first VS Breadth first
Recursive and Non-recursive (with stack or with queue)
TRAVERSALS
TREE TRAVERSAL
How to visit (enumerate, iterate through, traverse… ) all the nodes of a tree ?
TREE TRAVERSAL – DEPTH FIRST “PREORDER”
depthFirst (root){
if (root is not empty){
visit root
for each child of root depthfirst( child )
} }
TREE TRAVERSAL – DEPTH FIRST “PREORDER”
depthFirst (root){
if (root is not empty){
visit root
for each child of root depthfirst( child )
} }
1
“preorder” traversal: visit the root before the children
TREE TRAVERSAL – DEPTH FIRST “PREORDER”
depthFirst (root){
if (root is not empty){
visit root
for each child of root depthfirst( child )
} }
1
2
Note that here we are assuming that we iterate through the children nodes from left to right.
TREE TRAVERSAL – DEPTH FIRST “PREORDER”
depthFirst (root){
if (root is not empty){
visit root
for each child of root depthfirst( child )
} }
1
2
3
TREE TRAVERSAL – DEPTH FIRST “PREORDER”
depthFirst (root){
if (root is not empty){
visit root
for each child of root depthfirst( child )
} }
1
2
3
4
5
TREE TRAVERSAL – DEPTH FIRST “PREORDER”
depthFirst (root){
if (root is not empty){
visit root
for each child of root depthfirst( child )
} }
1
2
7
8
3
4
9
10
11
5
6
EXAMPLE OF USING A PREORDER TRAVERSAL
We would like to print a hierarchical file system (visit = print directory or file name)
Documents Music
(directory) (directory) (directory)
My Documents
Eminem
Lose Yourself (file)
Music
Videos
Work
Research
Raffi (directory) Shake My Sillies Out Baby Beluga
Videos (directory) : (file)
Work (directory) COMP250 (directory) :
Research (directory) :
(file) (file)
Eminem
Raffi
COMP 250
Lose Y ourself
Shake my sillies out
Baby Beluga
“VISIT” A NODE
“Visit” implies that you do something at that node.
Analogy: you aren’t visiting London UK if you just fly through Heathrow.
TREE TRAVERSAL – DEPTH FIRST “POSTORDER”
Q: Which node is visited first?
depthFirst (root){
if (root is not empty){
for each child of root
depthfirst( child )
visit root
} }
“postorder” traversal: visit the root after the children
TREE TRAVERSAL – DEPTH FIRST “POSTORDER”
depthFirst (root){
if (root is not empty){
for each child of root
depthfirst( child )
visit root
} }
1
TREE TRAVERSAL – DEPTH FIRST “POSTORDER”
depthFirst (root){
if (root is not empty){
for each child of root
depthfirst( child )
visit root
} }
1
2
TREE TRAVERSAL – DEPTH FIRST “POSTORDER”
depthFirst (root){
if (root is not empty){
for each child of root
depthfirst( child )
visit root
} }
5
1
4
2
3
TREE TRAVERSAL – DEPTH FIRST “POSTORDER”
depthFirst (root){
if (root is not empty){
for each child of root
depthfirst( child )
visit root
} }
11
5
6
10
1
4
7
8
9
2
3
EXAMPLE 1 OF USING A POSTORDER TRAVERSAL: height(v)
4
height(v){
if (v is a leaf)
return 0 else{
h=0
for each child w of v
h = max(h, height(w)) return 1 + h
} }
2
1
1
0
visit = return value of height
3
0
2
1
0
0
0
1
0
0
0
EXAMPLE 2 OF USING A POSTORDER TRAVERSAL
What is the total number of bytes in all files in a directory?
numBytes(v){
if (v is a leaf)
return number of bytes at v else{
sum = 0
for each child w of v
sum += numBytes(w)
return sum
} }
My Documents
Music
Videos
Work
Research
Eminem
Raffi
COMP 250
Lose Y ourself
Shake my sillies out
Baby Beluga
visit = determining the number of bytes for a node, e.g. If we were to store ‘sum’ at the node.
depthFirst()–PREORDER VSPOSTORDERTRAVERSAL
depthFirst (root){
if (root is not empty){
for each child of root
depthfirst( child )
visit root
} }
depthFirst (root){
if (root is not empty){
visit root
for each child of root depthfirst( child )
} }
CALL SEQUENCE OF depthFirst()
When we call depthFirst(root), the same call sequence occurs for preorder vs postorder implementation.
In the example on the rigth, the letter order corresponds to depthFirst(root) call order.
a
b
g
h
c
d
i
j
k
e
f
CALL STACK FOR depthFirst(root)
Note that the call stack stores information about the active method calls in a program.
a
b
g
h
c
d
i
j
k
e
f
ef
ddddd i j k
bbbbbbb g hhhhhhh aaaaaaaaaaaaaaaaaa
c bb
aaa
CALL STACK FOR depthFirst(root)
Note that the call stack stores information about the active method calls in a program.
a
b
g
h
c
d
i
j
k
f
e
f dddijk bbbb g hhhhhhh
aaaaaaaaaaaaaaa
e cdd bbbbb
aaaaaa
CALL STACK FOR depthFirst(root)
Note that the call stack stores information about the active method calls in a program.
a
b
g
h
c
d
i
j
k
e
f
d ijk
bb g hhhhhhh aaaaaaaaaaaaa
ef c dddd bbbbbbb
aaaaaaaa
CALL STACK FOR depthFirst(root)
Note that the call stack stores information about the active method calls in a program.
a
Notation: the letters indicate the call order of depthFirst(root)
b
g
c
d
ef
cddddd ijk
bbbbbbbbb g hhhhhhh aaaaaaaaaaaaaaaaaaaaa
i
h
j
k
e
f
EXAMPLE
We used a tree to represent the call stack of the recursive Fibonacci method. fibonacci(247)
fibonacci(246) fibonacci(245)
fibonacci( 245 ) fibonacci( 244 ) fibonacci(244) fibonacci(243)
fibonacci(244) fibonacci(243) fibonacci(243) fibonacci(242) Etc.
TREE TRAVERSAL IMPLEMENTATIONS
Recursive
depth first (pre- versus post-order)
Non-Recursive using a stack using a queue
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
}
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
} }
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
s.push(child) }
}
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
s.push(child) }
}
What is the order in which the nodes are visited?
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
} }
s.push(child)
a
h
b
g
i
c
d
j
k
e
f
k jjj
h iiiii f ggggggggg d eee
_bbbbbbbbbbb_ccccccc_
a
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
} }
s.push(child)
a
h
b
g
i
c
d
j
k
e
f
_
k jjj
h iiiii f ggggggggg d eee
bbbbbbbbbbb_ccccccc_
a
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
} }
s.push(child)
a
h
b
g
i
c
d
j
k
e
f
h gg _bbb
k jjj
iiiii f ggggggg d eee bbbbbbbb_ccccccc_
a
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
} }
s.push(child)
a
h
b
g
i
c
d
j
k
h
e
f
ggg _bbbb
k jjj
iiiii f gggggg d eee bbbbbbb_ccccccc_
a
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
} }
s.push(child)
a
h
b
g
i
c
d
j
k
k jj
iii gggggg _bbbbbbb
h
e
f
j iif
ggg d eee bbbb_ccccccc_
a
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
} }
s.push(child)
a
h
b
g
i
c
d
j
k
jjj iiii
ggggggg _bbbbbbbb
h
k
e
f
if ggdeee
bbb_ccccccc_
a
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
} }
s.push(child)
a
h
b
g
c
e
d
i
j
k
k
f
jj iiiii
gggggggg _bbbbbbbbb
j
h
f gdeee
bb_ccccccc_
a
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
} }
s.push(child)
a
h
b
g
i
c
d
j
k
k
e
f
jj iiii
ggggggggg _bbbbbbbbbb
j
h
i
f deee
b_ccccccc_
a
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
} }
s.push(child)
a
b
g
h
i
c
d
j
k
k
e
f
jj iiii
gggggggg _bbbbbbbbbbb
j
h
i
g
f deee
_ccccccc_
a
TREE TRAVERSAL – WITH A STACK
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
} }
s.push(child)
b
g
c
d
i
j
k
k
e
f
jj iiii
gggggggg ee _bbbbbbbbbb _ccccc _
j
a
h
h
i
g
b
d
f
e
a
c
TREE TRAVERSAL – WITH A STACK
Q: Is it depth first?
A: Yes, but it visits the children “from right to left”
a
b
g
h
c
d
i
j
k
Recursive preorder: abcdefghijk Recursive postorder: cefdbgijkha
Non-recursive (stack): ahkjigbdfec
e
f
TREE TRAVERSAL – WITH A STACK
Q: Is it preorder or postorder? A: It’s preorder.
Q: Would move the visit change that? A: No… why?
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
s.push(child) }
}
visit cur
WHAT IF WE USED A QUEUE INSTEAD?
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur
s.push(child)
}
}
treeTraversalUsingQueue(root){ initialize empty queue q q.enqueue(root)
while q is not empty {
cur = q.dequeue() visit cur
for each child of cur
q.enqueue(child)
}
}
WHAT IF WE USED A QUEUE INSTEAD?
Queue state at start of the while loop
a
treeTraversalUsingQueue(root){ initialize empty queue q q.enqueue(root)
while s is not empty {
cur = q.dequeue()
visit cur
for each child of cur
} }
q.enqueue(child)
a
b
g
h
c
d
i
j
k
e
f
WHAT IF WE USED A QUEUE INSTEAD?
Queue state at start of the while loop
a
bg h
treeTraversalUsingQueue(root){ initialize empty queue q q.enqueue(root)
while s is not empty {
cur = q.dequeue()
visit cur
for each child of cur
} }
q.enqueue(child)
a
b
g
h
c
d
i
j
k
e
f
WHAT IF WE USED A QUEUE INSTEAD?
Queue state at start of the while loop
a
bg h gh
g h cd
treeTraversalUsingQueue(root){ initialize empty queue q q.enqueue(root)
while s is not empty {
cur = q.dequeue()
visit cur
for each child of cur
} }
q.enqueue(child)
b
a
g
h
c
d
i
j
k
e
f
WHAT IF WE USED A QUEUE INSTEAD?
Queue state at start of the while loop
a
bg h gh
g h cd hc d
treeTraversalUsingQueue(root){ initialize empty queue q q.enqueue(root)
while s is not empty {
cur = q.dequeue()
visit cur
for each child of cur
} }
q.enqueue(child)
a
b
g
h
c
d
i
j
k
e
f
WHAT IF WE USED A QUEUE INSTEAD?
Queue state at start of the while loop
a
bg h gh
g h cd hc d cd cdijk
treeTraversalUsingQueue(root){ initialize empty queue q q.enqueue(root)
while s is not empty {
cur = q.dequeue()
visit cur
for each child of cur
} }
q.enqueue(child)
a
b
g
h
c
d
i
j
k
e
f
WHAT IF WE USED A QUEUE INSTEAD?
Queue state at start of the while loop
a
bg h gh
g h cd hc d cd cdijk dijk ijk
i jk e f j k ef kef ef
f
treeTraversalUsingQueue(root){ initialize empty queue q q.enqueue(root)
while s is not empty {
cur = q.dequeue()
visit cur
for each child of cur
} }
q.enqueue(child)
a
b
g
h
c
d
i
j
k
e
f
BREADTH FIRST TRAVERSAL
For each level i
visit all nodes at level i
Order visited: abghcdijkef
b
a
g
h
c
d
i
j
k
e
f
IMPLEMENTATION DETAILS
Recall the “first child, next sibling” implementation
class Tree
TreeNode
:
class TreeNode
T element;
TreeNode
TreeNode
: }
}
IMPLEMENTATION DETAILS
Recall the “first child, next sibling” implementation Then when we write
for each child {
: }
it means
child = cur.firstChild
while(child !=null) {
:
child = child.nextSibling
}
In the next video: Binary Trees