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 ...

Get Learning Functional Data Structures and Algorithms now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.