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 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)
}
}