Learning Functional Data Structures and Algorithms

Building the tree

Let's try building one such tree. The input values are fed from a List. Note that we are using Scala's immutable lists:

scala>   def buildTree[A](list: List[A]): BinTree[A] = list match { 
     |     case Nil => Leaf 
     |     case x :: xs => { 
     |       val k = xs.length / 2 
     |       Branch(x, buildTree(xs.take(k)), buildTree(xs.drop(k))) 
     |     } 
     |   } 
buildTree: [A](list: List[A])BinTree[A] 
 
val treeFromList = buildTree(list) 
treeFromList: BinTree[Int] = Branch(1,Branch(2,Branch(3,Leaf,Leaf),Branch(4,Leaf,Leaf)),Branch(5,Branch(6,Leaf,Leaf),Branch(7,Leaf,Branch(8,Leaf,Leaf)))) 

The method creates a balanced binary tree. Such a balanced tree's left and right subtrees have almost equal number of nodes.

The first case is simple:

case Nil => Leaf 

The clause is hit when the ...