Skip to content

Instantly share code, notes, and snippets.

@vpatryshev
Created April 27, 2016 16:04
Show Gist options
  • Save vpatryshev/b98b937e904616562df3666f440754fc to your computer and use it in GitHub Desktop.
Save vpatryshev/b98b937e904616562df3666f440754fc to your computer and use it in GitHub Desktop.
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