O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required