Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
implementation of inorder scan of a binary tree
case class BT[T](left: Option[BT[T]], value: T, right: Option[BT[T]]);
def inorder[T](t:BT[T], out: T=>Unit): Unit = {
val stack: mutable.Stack[(Boolean, BT[T])] = new mutable.Stack[(Boolean, BT[T])]()
def p(n: BT[T]) = stack.push((false, n))
p(t)
while (!stack.isEmpty) {
(stack.pop() match {
case (true, top) =>
out(top.value)
top.right
case (false, top) =>
stack.push((true, top))
top.left
}) foreach p
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment