 3 people like it.

# Layout binary tree

Solution to the layout binary tree problem from 99 OCaml problems

## Type definition

 ```1: 2: 3: 4: 5: 6: 7: ``` ``````type 'a binary_tree = | Empty | Node of 'a * 'a binary_tree * 'a binary_tree let example_tree = Node('a', Node('b', Node('d', Empty, Empty), Node('e', Empty, Empty)), Node('c', Empty, Node('f', Node('g', Empty, Empty), Empty))) ``````

## Counting leaves

 ```1: 2: 3: 4: 5: ``` ``````let rec count_leaves tree = match tree with | Empty -> 0 | Node(_,Empty,Empty) -> 1 | Node(_,a,b) -> (count_leaves a) + (count_leaves b) ``````

## Generating layout

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: ``` ``````type 'a pos_binary_tree = | E (* represents the empty tree *) | N of 'a * int * int * 'a pos_binary_tree * 'a pos_binary_tree (*N(w,x,y,l,r) represents a (non-empty) binary tree with root w "positioned" at (x,y), and subtrees l and r *) let make_pos_binary_tree (tree:binary_tree<_>) = let rec layout t x depth = match t with | Empty -> (x,E) | Node(a,l,r) -> let x',lTree = layout l x (depth+1) let x'',rTree = layout r (x'+1) (depth+1) (x'',N(a,x',depth,lTree,rTree)) let finalX,finalTree = layout tree 1 1 finalTree ``````

## Example and rendering

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: ``` ``````let laidOutTree = make_pos_binary_tree example_tree let canvas = Array2D.init 50 50 (fun _ _ -> ' ') let rec draw tree = match tree with | E -> () | N(v,x,y,l,r) -> canvas.[y,x] <- v draw l draw r draw laidOutTree for y in 0..49 do for x in 0..49 do stdout.Write(canvas.[y,x]) stdout.WriteLine() ``````
union case binary_tree.Empty: 'a binary_tree
union case binary_tree.Node: 'a * 'a binary_tree * 'a binary_tree -> 'a binary_tree
type 'a binary_tree =
| Empty
| Node of 'a * 'a binary_tree * 'a binary_tree

Full name: Script.binary_tree<_>
val example_tree : char binary_tree

Full name: Script.example_tree
val count_leaves : tree:'a binary_tree -> int

Full name: Script.count_leaves
val tree : 'a binary_tree
val a : 'a binary_tree
val b : 'a binary_tree
type 'a pos_binary_tree =
| E
| N of 'a * int * int * 'a pos_binary_tree * 'a pos_binary_tree

Full name: Script.pos_binary_tree<_>
union case pos_binary_tree.E: 'a pos_binary_tree
union case pos_binary_tree.N: 'a * int * int * 'a pos_binary_tree * 'a pos_binary_tree -> 'a pos_binary_tree
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val make_pos_binary_tree : tree:'a binary_tree -> 'a pos_binary_tree

Full name: Script.make_pos_binary_tree
val layout : ('b binary_tree -> int -> int -> int * 'b pos_binary_tree)
val t : 'b binary_tree
val x : int
val depth : int
val a : 'b
val l : 'b binary_tree
val r : 'b binary_tree
val x' : int
val lTree : 'b pos_binary_tree
val x'' : int
val rTree : 'b pos_binary_tree
val finalX : int
val finalTree : 'a pos_binary_tree
val laidOutTree : char pos_binary_tree

Full name: Script.laidOutTree
val canvas : char [,]

Full name: Script.canvas
module Array2D

from Microsoft.FSharp.Collections
val init : length1:int -> length2:int -> initializer:(int -> int -> 'T) -> 'T [,]

Full name: Microsoft.FSharp.Collections.Array2D.init
val draw : tree:char pos_binary_tree -> unit

Full name: Script.draw
val tree : char pos_binary_tree
val v : char
val y : int
val l : char pos_binary_tree
val r : char pos_binary_tree
val y : int32
val x : int32
val stdout<'T> : System.IO.TextWriter

Full name: Microsoft.FSharp.Core.Operators.stdout