Skip to content

Instantly share code, notes, and snippets.

@dholbrook
Created June 21, 2012 17:59
Show Gist options
  • Star 63 You must be signed in to star a gist
  • Fork 24 You must be signed in to fork a gist
  • Save dholbrook/2967371 to your computer and use it in GitHub Desktop.
Save dholbrook/2967371 to your computer and use it in GitHub Desktop.
Scala binary tree
/**
* D Holbrook
*
* Code Club: PO1
*
* (*) Define a binary tree data structure and related fundamental operations.
*
* Use whichever language features are the best fit (this will depend on the language you have selected). The following operations should be supported:
*
* Constructors
* (bitree data left right) - Should return a binary tree containing data and the left and right children.
* Accessors
* (bitree-data t) - Should return the data contained by the tree.
* (bitree-left t) - Should return the left child of the tree.
* (bitree-right t) - Should return the right child of the tree.
* Predicates
* (bitree-leaf? t) - Should return true if the tree is a leaf (has null left and right children), false otherwise
*/
trait Tree[+A] {
import scala.annotation.tailrec
def value: Option[A] = this match {
case n: Node[A] => Some(n.v)
case l: Leaf[A] => Some(l.v)
case Empty => None
}
def left: Option[Tree[A]] = this match {
case n: Node[A] => Some(n.l)
case l: Leaf[A] => None
case Empty => None
}
def right: Option[Tree[A]] = this match {
case n: Node[A] => Some(n.r)
case l: Leaf[A] => None
case Empty => None
}
/**
* Represents a deferred evaluation of a node value
*/
private case class Eval[A](v: A) extends Tree[A]
/**
* represents common functionality of all traversal order folds
*/
@tailrec
private def foldLoop[A, B](a: List[Tree[A]], z: B)(f: (B, A) => B)(o: (Node[A], List[Tree[A]]) => List[Tree[A]]): B = a match {
case (n: Node[A]) :: tl => foldLoop(o(n, tl), z)(f)(o) // never directly evaluate nodes, function o will create new accumulator
case (l: Leaf[A]) :: tl => foldLoop(tl, f(z, l.v))(f)(o) // always evaluate Leaf
case (e: Eval[A]) :: tl => foldLoop(tl, f(z, e.v))(f)(o) // always evaluate Eval
case Empty :: tl => foldLoop(tl, z)(f)(o) // ignore Empty
case _ => z // will be Nil (empty list)
}
/**
* fold with preorder traversal (root, left, right)
* Tail Recursive Optimized
*
* F
* / \
* B G
* / \ \
* A D I
* / \ /
* C E H
*
* head evaluate accumulator
* ---- -------- -----------
* | (F)
* F | () | F::B::G::()
* F | (F) | (B,G)
* B | () | B::A::D::(G)
* B | (B) | (A,D,G)
* A | (A) | (D,G)
* D | () | D::C::E::(G)
* D | (D) | (C,E,G)
* C | (C) | (E,G)
* E | (E) | (G)
* G | () | G::I::()
* G | (G) | (I)
* I | () | I::H::()
* I | (I) | (H)
* H | (H) | ()
*
* result
* F, B, A, D, C, E, G, I, H
*/
def foldPreorder[B](z: B)(f: (B, A) => B): B = {
foldLoop(List(this), z)(f) { (n, tl) => Eval(n.v) :: n.l :: n.r :: tl }
}
/**
* fold with inorder traversal (left, root, right)
* tail recursive optimized
*
* F
* / \
* B G
* / \ \
* A D I
* / \ /
* C E H
*
* head evaluate accumulator
* ---- -------- -----------
* | (F)
* F | () | B::F::G::()
* B | () | A::B::D::(F,G)
* A | (A) | (B,D,F,G)
* B | (B) | (D,F,G)
* D | () | C::D::E::(F,G)
* C | (C) | (D,E,F,G)
* D | (D) | (E,F,G)
* E | (E) | (F,G)
* F | (F) | (G)
* G | () | G::I::()
* G | (G) | (I)
* I | () | H::I::()
* H | (H) | H
* I | (I) | ()
*
* result
* A,B,C,D,E,F,G,H,I
*/
def foldInorder[B](z: B)(f: (B, A) => B): B = {
foldLoop(List(this), z)(f) { (n, tl) => n.l :: Eval(n.v) :: n.r :: tl }
}
/**
* fold with postorder traversal (left, right, root)
* tail recursive optimized
*
* F
* / \
* B G
* / \ \
* A D I
* / \ /
* C E H
*
* head evaluate accumulator
* ---- -------- -----------
* | (F)
* F | () | B::G::F::()
* B | () | A::D::(B,G,F)
* A | (A) | (D,B,G,F)
* D | () | C::E::D::(B,G,F)
* C | (C) | (E,D,B,G,F)
* E | (E) | (D,B,G,F)
* D | (D) | (B,G,F)
* B | (B) | (G,F)
* G | () | I::G::(F)
* I | () | H::I::(G,F)
* H | (H) | (I,G,F)
* I | (I) | (G,F)
* G | (G) | (F)
* F | (F) | ()
*
* result
* A,C,E,D,B,H,I,G,F
*/
def foldPostorder[B](z: B)(f: (B, A) => B): B = {
foldLoop(List(this), z)(f) { (n, tl) => n.l :: n.r :: Eval(n.v) :: tl }
}
/**
* fold with levelorder traversal
* tail recursive optimized
*
* F
* / \
* B G
* / \ \
* A D I
* / \ /
* C E H
*
* head evaluate accumulator
* ---- -------- -----------
* | (F)
* F | () | (F::()) ::: (B,G)
* F | (F) | (B,G)
* B | () | (B::(G)) ::: (A,D)
* B | (B) | (G,A,D)
* G | () | (G::(A,D)) ::: (I)
* G | (G) | (A,D,I)
* A | (A) | (D,I)
* D | () | (D::(I)) ::: (C,E)
* D | (D) | (I,C,E)
* I | () | (I::(C,E)) ::: (H)
* I | (I) | (C,E,H)
* C | (C) | (E,H)
* E | (E) | (H)
* H | (H) | ()
*
* result
* F, B, G, A, D, I, C, E, H
*/
def foldLevelorder[B](z: B)(f: (B, A) => B): B = {
foldLoop(List(this), z)(f) { (n, tl) => (Eval(n.v) :: tl) ::: List(n.l, n.r) }
}
/**
* calls foldInorder
*/
def fold[B](z: B)(f: (B, A) => B): B = foldInorder(z)(f)
/**
* P02
* (*) Count the number of nodes in a binary tree.
*/
def size: Int = fold(0) { (sum, v) => sum + 1 }
/**
* P03
* (*) Determine the height of a binary tree.
* Definition: The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero.
*/
def height: Int = {
def loop(t: Tree[A]): Int = t match {
case l: Leaf[A] => 1
case n: Node[A] => Seq(loop(n.left.get), loop(n.right.get)).max + 1
case _ => 0
}
loop(this) - 1
}
/**
* P04
* (*) Count the number of leaves in a binary tree.
*/
def leafCount: Int = {
@tailrec
def loop(t: List[Tree[A]], z: Int): Int = t match {
case (l: Leaf[A]) :: tl => loop(tl, z + 1)
case (n: Node[A]) :: tl => loop(n.left.get :: n.right.get :: tl, z)
case _ :: tl => loop(tl, z)
case _ => z
}
loop(List(this), 0)
}
def toSeq: Seq[A] = fold(List[A]()) { (l, v) => v :: l } reverse
def toSeqPreorder: Seq[A] = foldPreorder(List[A]()) { (l, v) => v :: l } reverse
def toSeqInorder: Seq[A] = foldInorder(List[A]()) { (l, v) => v :: l } reverse
def toSeqPostorder: Seq[A] = foldPostorder(List[A]()) { (l, v) => v :: l } reverse
def toSeqLevelorder: Seq[A] = foldLevelorder(List[A]()) { (l, v) => v :: l } reverse
/**
* P05
* (**) Find the last element in a binary tree using pre/in/post/level order traversals.
* Note: This is S-99 problem P01 converted from lists to binary trees.
*/
def lastPreorder = toSeqPreorder.last
def lastInorder = toSeqInorder.last
def lastPostorder = toSeqPostorder.last
def lastLevelorder = toSeqLevelorder.last
/**
* P06
* (**) Find the last but one element in a binary tree using pre/in/post/level order traversals.
* Note: This is S-99 problem P02 converted from lists to binary trees.
*/
def penultimatePreorder = toSeqPreorder.dropRight(1).last
def penultimateInorder = toSeqInorder.dropRight(1).last
def penultimatePostorder = toSeqPostorder.dropRight(1).last
def penultimateLevelorder = toSeqLevelorder.dropRight(1).last
/**
* P07
* (**) Find the Nth element in a binary tree using pre/in/post/level order traversals.
* By convention, the first element in the tree is element 0.
*
*/
def nthPreorder(n: Int) = toSeqPreorder(n)
def nthInorder(n: Int) = toSeqInorder(n)
def nthPostorder(n: Int) = toSeqPostorder(n)
def nthLevelorder(n: Int) = toSeqLevelorder(n)
}
case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree[A]
case class Leaf[A](v: A) extends Tree[A]
case object Empty extends Tree[Nothing]
object Run extends App {
val t: Tree[Symbol] = Node('F, Node('B, Leaf('A), Node('D, Leaf('C), Leaf('E))), Node('G, Empty, Node('I, Leaf('H), Empty)))
println("tree: " + t)
//print the value of b node navigating from root
for {
b <- t.left
value <- b.value
} println("B node: " + value)
//print the value of e node navigating from root
for {
b <- t.left
d <- b.right
value <- d.value
} println("D node: " + value)
//no println() is executed for empty node chain
for {
b <- t.left
d <- b.right
e <- d.right
x <- e.right
value <- x.value
} println("X node SHOUL NOT PRINT!: " + value)
println("as seq: " + t.toSeq)
println("count: " + t.size)
assert(t.size == 9)
println("height: " + t.height)
assert(t.height == 3)
println("leaft count: " + t.leafCount)
assert(t.leafCount == 4)
println("as seqPreorder: " + t.toSeqPreorder)
println("as seqInorder: " + t.toSeqInorder)
println("as seqPostorder: " + t.toSeqPostorder)
println("as seqLevelorder: " + t.toSeqLevelorder)
println("last preorder :" + t.lastPreorder)
println("last inorder :" + t.lastInorder)
println("last postorder :" + t.lastPostorder)
println("last levelorder: " + t.lastLevelorder)
println("nth preorder 5 : " + t.nthPreorder(5))
println("nth inorder 5 : " + t.nthInorder(5))
println("nth postorder 5 : " + t.nthPostorder(5))
println("nth levelorder 5 : " + t.nthLevelorder(5))
//
/**
* **** output *********
*
* tree: Node('F,Node('B,Leaf('A),Node('D,Leaf('C),Leaf('E))),Node('G,Empty,Node('I,Leaf('H),Empty)))
* B node: 'B
* D node: 'D
* as seq: List('A, 'B, 'C, 'D, 'E, 'F, 'G, 'H, 'I)
* count: 9
* height: 3
* leaft count: 4
* as seqPreorder: List('F, 'B, 'A, 'D, 'C, 'E, 'G, 'I, 'H)
* as seqInorder: List('A, 'B, 'C, 'D, 'E, 'F, 'G, 'H, 'I)
* as seqPostorder: List('A, 'C, 'E, 'D, 'B, 'H, 'I, 'G, 'F)
* as seqLevelorder: List('F, 'B, 'G, 'A, 'D, 'I, 'C, 'E, 'H)
* last preorder :'H
* last inorder :'I
* last postorder :'F
* last levelorder: List('F, 'B, 'G, 'A, 'D, 'I, 'C, 'E, 'H)
* nth preorder 5 : 'C
* nth inorder 5 : 'E
* nth postorder 5 : 'B
* nth levelorder 5 : 'D
*
* ***********************
*/
}
@skissh
Copy link

skissh commented Feb 18, 2016

Would some one please show my how to use foldLoop or fold to return a modified tree?

@derekennui
Copy link

Good job!

@aesguerra
Copy link

Exquisite.

@macakmujo
Copy link

very cool, nice work :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment