Notes - Imperative Programming TT23, Tree traversal
Flashcards
Suppose we had a class
class Tree(var datum: Int, var left: Tree, var right: Tree)
how could we implement a non-recursive inorder traversal of this data structure with a stack, assuming we want to call a Visit method at each node?
class Tree(var datum: Int, var left: Tree, var right: Tree)
Visit method at each node?def inorderTraversal(root: Tree) : Unit = {
val stack = new Stack[Tree]()
val current = root
while(!stack.isEmpty || current != null) {
if (curr != null) {
stack.push(curr)
curr = curr.left
} else {
val node = stack.pop()
Visit(node)
curr = node.right
}
}
}
Suppose we had a class
class Tree(var datum: Int, var left: Tree, var right: Tree)
how could we implement a non-recursive postorder traversal of this data structure with a stack, assuming we want to call a Visit method at each node?
class Tree(var datum: Int, var left: Tree, var right: Tree)
Visit method at each node?def inorderTraversal(root: Tree) : Unit = {
if (root == null) {
return
}
val firstStack = new Stack[Tree]()
val secondStack = new Stack[Tree]()
firstStack.push(root)
while (!firstStack.isEmpty) {
val curr = firstStack.pop()
secondStack.push(curr)
if (curr.left != null) { firstStack.push(curr.left) }
if (curr.right != null) { firstStack.push(curr.right) }
}
while (!secondStack.isEmpty) {
val node = secondStack.pop()
Visit(node)
}
}