6 people like it.

Ninety-Nine F# Problems - Problems 54 - 60 - Binary trees

These are F# solutions of Ninety-Nine Haskell Problems which are themselves translations of Ninety-Nine Lisp Problems and Ninety-Nine Prolog Problems. The solutions are hidden so you can try to solve them yourself.

Ninety-Nine F# Problems - Problems 54 - 60 - Binary trees

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68: 
69: 
70: 
71: 
72: 
73: 

/// These are F# solutions of Ninety-Nine Haskell Problems 
/// (http://www.haskell.org/haskellwiki/H-99:_Ninety-Nine_Haskell_Problems), 
/// which are themselves translations of Ninety-Nine Lisp Problems
/// (http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html)
/// and Ninety-Nine Prolog Problems
/// (https://sites.google.com/site/prologsite/prolog-problems).
///
/// If you would like to contribute a solution or fix any bugs, send 
/// an email to paks at kitiara dot org with the subject "99 F# problems". 
/// I'll try to update the problem as soon as possible.
///
/// The problems have different levels of difficulty. Those marked with a single asterisk (*) 
/// are easy. If you have successfully solved the preceeding problems you should be able to 
/// solve them within a few (say 15) minutes. Problems marked with two asterisks (**) are of 
/// intermediate difficulty. If you are a skilled F# programmer it shouldn't take you more than 
/// 30-90 minutes to solve them. Problems marked with three asterisks (***) are more difficult. 
/// You may need more time (i.e. a few hours or more) to find a good solution
///
/// Though the problems number from 1 to 99, there are some gaps and some additions marked with 
/// letters. There are actually only 88 problems.
///
///  
/// 
/// A binary tree is either empty or it is composed of a root element and two successors, 
/// which are binary trees themselves.
/// 
///                              (a)
///                             /   \
///                            (b)  (c)
///                           /  \    \
///                         (d)  (e)  (f)
///
/// In F#, we can characterize binary trees with a type definition: 
/// 

type 'a Tree = Empty | Branch of 'a * 'a Tree * 'a Tree

///
/// This says that a Tree of type a consists of either an Empty node, or a Branch containing one 
/// value of type a with exactly two subtrees of type a.
///  
/// Given this definition, the tree in the diagram above would be represented as: 
/// 

let tree1 = Branch ('a', Branch ('b', Branch ('d', Empty, Empty),
                               Branch ('e', Empty, Empty)),
                         Branch ('c', Empty,
                               Branch ('f', Branch ('g', Empty, Empty),
                                           Empty))) 

/// Since a "leaf" node is a branch with two empty subtrees, it can be useful to define a 
/// shorthand function:

let leaf x = Branch (x, Empty, Empty) 

/// Then the tree diagram above could be expressed more simply as: 

let tree1' = Branch ('a', Branch ('b', leaf 'd',
                               leaf 'e'),
                          Branch ('c', Empty,
                               Branch ('f', leaf 'g',
                                           Empty)))
/// Other examples of binary trees: 
/// 
/// -- A binary tree consisting of a root node only
let tree2 = Branch ('a', Empty, Empty)
///  
/// -- An empty binary tree
let tree3 = Empty
///  
/// -- A tree of integers
let tree4 = Branch (1, Branch (2, Empty, Branch (4, Empty, Empty)),
                       Branch (2, Empty, Empty))

(*) Problem 54A : Check whether a given term represents a binary tree.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 

/// In Prolog or Lisp, one writes a predicate to do this. 
/// 
/// Example in Lisp: 
/// * (istree (a (b nil nil) nil))
/// T
/// * (istree (a (b nil nil)))
/// NIL
///  
/// Non-solution: 
/// F#'s type system ensures that all terms of type 'a Tree are binary trees: it is just not 
//  possible to construct an invalid tree with this type. Hence, it is redundant to introduce 
/// a predicate to check this property: it would always return True

() Problem 55 : Construct completely balanced binary trees

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 

/// In a completely balanced binary tree, the following property holds for every node: 
/// The number of nodes in its left subtree and the number of nodes in its right subtree 
/// are almost equal, which means their difference is not greater than one.
///  
/// Write a function cbal-tree to construct completely balanced binary trees for a given 
/// number of nodes. The predicate should generate all solutions via backtracking. Put 
/// the letter 'x' as information into all nodes of the tree.
///  
/// Example: 
/// * cbal-tree(4,T).
/// T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil))) ;
/// T = t(x, t(x, nil, nil), t(x, t(x, nil, nil), nil)) ;
/// etc......No
///  
/// Example in F#, whitespace and "comment diagrams" added for clarity and exposition:
///  
/// > cbalTree 4;;
/// val trees : char Tree list =
/// [
///    permutation 1
///        x
///       / \
///      x   x
///           \
///            x
/// Branch ('x', Branch ('x', Empty, Empty),
///              Branch ('x', Empty,
///                        Branch ('x', Empty, Empty)));
///  
///    permutation 2
///        x
///       / \
///      x   x
///         /
///        x
/// Branch ('x', Branch ('x', Empty, Empty),
///              Branch ('x', Branch ('x', Empty, Empty),
///                        Empty));
///  
///    permutation 3
///        x
///       / \
///      x   x
///       \
///        x
/// Branch ('x', Branch ('x', Empty, 
///                           Branch ('x', Empty, Empty)),
///              Branch ('x', Empty, Empty));
///  
///    permutation 4
///        x
///       / \
///      x   x
///     /
///    x
/// Branch ('x', Branch ('x', Branch ('x', Empty, Empty),
///                        Empty), 
///              Branch ('x', Empty, Empty))
/// ]

(Solution 1)

(Solution 2)

() Problem 56 : Symmetric binary trees

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 

/// Let us call a binary tree symmetric if you can draw a vertical line through the root 
/// node and then the right subtree is the mirror image of the left subtree. Write a 
/// predicate symmetric/1 to check whether a given binary tree is symmetric. Hint: Write 
/// a predicate mirror/2 first to check whether one tree is the mirror image of another. 
/// We are only interested in the structure, not in the contents of the nodes.
///  
/// Example in F#: 
/// 
/// > symmetric <| Branch ('x', Branch ('x', Empty, Empty), Empty);;
/// val it : bool = false
/// > symmetric <| Branch ('x', Branch ('x', Empty, Empty), Branch ('x', Empty, Empty))
/// val it : bool = true

(Solution)

() Problem 57 : Binary search trees (dictionaries)

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 

/// Use the predicate add/3, developed in chapter 4 of the course, to write a predicate 
/// to construct a binary search tree from a list of integer numbers.
///  
/// Example: 
/// * construct([3,2,5,7,1],T).
/// T = t(3, t(2, t(1, nil, nil), nil), t(5, nil, t(7, nil, nil)))
///  
/// Then use this predicate to test the solution of the problem P56. 
/// 
/// Example: 
/// * test-symmetric([5,3,18,1,4,12,21]).
/// Yes
/// * test-symmetric([3,2,5,7,4]).
/// No
///  
/// Example in F#: 
/// 
/// > construct [3; 2; 5; 7; 1]
/// val it : int Tree =
///   Branch (3,Branch (2,Branch (1,Empty,Empty),Empty),
///             Branch (5,Empty,Branch (7,Empty,Empty)))
/// > [5; 3; 18; 1; 4; 12; 21] |> construct |> symmetric;;
/// val it : bool = true
/// > [3; 2; 5; 7; 1] |> construct |> symmetric;;
/// val it : bool = true

(Solution)

() Problem 58 : Generate-and-test paradigm

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 

/// Apply the generate-and-test paradigm to construct all symmetric, completely balanced 
/// binary trees with a given number of nodes.
///  
/// Example: 
/// * sym-cbal-trees(5,Ts).
/// Ts = [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), 
///       t(x, t(x, t(x, nil, nil), nil), t(x, nil, t(x, nil, nil)))] 
///  
/// Example in F#: 
/// 
/// > symCbalTrees 5;;
/// val it : char Tree list =
///   [Branch
///      ('x',Branch ('x',Empty,Branch ('x',Empty,Empty)),
///       Branch ('x',Branch ('x',Empty,Empty),Empty));
///    Branch
///      ('x',Branch ('x',Branch ('x',Empty,Empty),Empty),
///       Branch ('x',Empty,Branch ('x',Empty,Empty)))]

(Solution)

() Problem 59 : Construct height-balanced binary trees

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 

/// In a height-balanced binary tree, the following property holds for every node: The 
/// height of its left subtree and the height of its right subtree are almost equal, 
/// which means their difference is not greater than one.
///  
/// Example: 
/// ?- hbal_tree(3,T).
/// T = t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), t(x, nil, nil))) ;
/// T = t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), nil)) ;
/// etc......No
///  
/// Example in F#: 
/// 
/// > hbalTree 'x' 3 |> Seq.take 4;;
/// val it : seq<char Tree> =
///   seq
///     [Branch
///        ('x',Branch ('x',Branch ('x',Empty,Empty),Branch ('x',Empty,Empty)),
///         Branch ('x',Branch ('x',Empty,Empty),Branch ('x',Empty,Empty)));
///      Branch
///        ('x',Branch ('x',Branch ('x',Empty,Empty),Branch ('x',Empty,Empty)),
///         Branch ('x',Branch ('x',Empty,Empty),Empty));
///      Branch
///        ('x',Branch ('x',Branch ('x',Empty,Empty),Branch ('x',Empty,Empty)),
///         Branch ('x',Empty,Branch ('x',Empty,Empty)));
///      Branch
///        ('x',Branch ('x',Branch ('x',Empty,Empty),Branch ('x',Empty,Empty)),
///         Branch ('x',Empty,Empty))]

(Solution)

() Problem 60 : Construct height-balanced binary trees with a given number of nodes

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 

/// Consider a height-balanced binary tree of height H. What is the maximum number of nodes 
/// it can contain?
/// Clearly, MaxN = 2**H - 1. However, what is the minimum number MinN? This question is more 
/// difficult. Try to find a recursive statement and turn it into a function minNodes that 
/// returns the minimum number of nodes in a height-balanced binary tree of height H. On the 
/// other hand, we might ask: what is the maximum height H a height-balanced binary tree with 
/// N nodes can have? Write a function maxHeight that computes this. 
///
/// Now, we can attack the main problem: construct all the height-balanced binary trees with a 
/// given nuber of nodes. Find out how many height-balanced trees exist for N = 15.
///  
/// Example in Prolog: 
/// ?- count_hbal_trees(15,C).
/// C = 1553
///  
/// Example in F#: 
/// 
/// > hbalTreeNodes 'x' 15 |> List.length;;
/// val it : int = 1553
/// > [0 .. 3] |> List.map (hbalTreeNodes 'x');;
/// val it : char Tree list list =
///   [[Empty]; [Branch ('x',Empty,Empty)];
///    [Branch ('x',Branch ('x',Empty,Empty),Empty);
///     Branch ('x',Empty,Branch ('x',Empty,Empty))];
///    [Branch ('x',Branch ('x',Empty,Empty),Branch ('x',Empty,Empty))]]

(Solution)
union case Tree.Empty: 'a Tree
union case Tree.Branch: 'a * 'a Tree * 'a Tree -> 'a Tree
type 'a Tree =
  | Empty
  | Branch of 'a * 'a Tree * 'a Tree

Full name: Script.Tree<_>


 These are F# solutions of Ninety-Nine Haskell Problems
 (http://www.haskell.org/haskellwiki/H-99:_Ninety-Nine_Haskell_Problems),
 which are themselves translations of Ninety-Nine Lisp Problems
 (http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html)
 and Ninety-Nine Prolog Problems
 (https://sites.google.com/site/prologsite/prolog-problems).

 If you would like to contribute a solution or fix any bugs, send
 an email to paks at kitiara dot org with the subject "99 F# problems".
 I'll try to update the problem as soon as possible.

 The problems have different levels of difficulty. Those marked with a single asterisk (*)
 are easy. If you have successfully solved the preceeding problems you should be able to
 solve them within a few (say 15) minutes. Problems marked with two asterisks (**) are of
 intermediate difficulty. If you are a skilled F# programmer it shouldn't take you more than
 30-90 minutes to solve them. Problems marked with three asterisks (***) are more difficult.
 You may need more time (i.e. a few hours or more) to find a good solution

 Though the problems number from 1 to 99, there are some gaps and some additions marked with
 letters. There are actually only 88 problems.

  
 
 A binary tree is either empty or it is composed of a root element and two successors,
 which are binary trees themselves.
 
                              (a)
                             / \
                            (b) (c)
                           / \ \
                         (d) (e) (f)

 In F#, we can characterize binary trees with a type definition:
 
val tree1 : char Tree

Full name: Script.tree1



 This says that a Tree of type a consists of either an Empty node, or a Branch containing one
 value of type a with exactly two subtrees of type a.
  
 Given this definition, the tree in the diagram above would be represented as:
 
val leaf : x:'a -> 'a Tree

Full name: Script.leaf


 Since a "leaf" node is a branch with two empty subtrees, it can be useful to define a
 shorthand function:
val x : 'a
val tree1' : char Tree

Full name: Script.tree1'


 Then the tree diagram above could be expressed more simply as:
val tree2 : char Tree

Full name: Script.tree2


 Other examples of binary trees:
 
 -- A binary tree consisting of a root node only
val tree3 : 'a Tree

Full name: Script.tree3


  
 -- An empty binary tree
val tree4 : int Tree

Full name: Script.tree4


  
 -- A tree of integers
let rec cbalTree n =
    match n with
        | 0 -> [Empty]
        | n -> let q,r = let x = n - 1 in x / 2, x % 2
               [ for i=q to q + r do
                    for lt in cbalTree i do
                       for rt in cbalTree (n - 1 - i) do
                          yield Branch('x', lt, rt) ]
let nodes t =
    let rec nodes' t cont =
        match t with
            | Empty -> cont 0
            | Branch(_, lt, rt) ->
                nodes' lt (fun nlt -> nodes' rt (fun nrt -> cont (1 + nlt + nrt)))
    nodes' t id

let rec allTrees n =
    match n with
        | 0 -> [Empty]
        | n ->
            [ for i=0 to n - 1 do
                 for lt in cbalTree i do
                    for rt in cbalTree (n - 1 - i) do
                       yield Branch('x', lt, rt) ]

let cbalTree' n = allTrees n |> List.filter(fun t ->
                                                match t with
                                                    | Empty -> true
                                                    | Branch(_, lt, rt) -> abs (nodes lt - nodes rt) <= 1 )
let symmetric tree =
    let rec mirror t1 t2 cont =
        match t1,t2 with
            | Empty,Empty -> cont true
            | Empty, Branch _ -> cont false
            | Branch _, Empty -> cont false
            | Branch (_, lt1, rt1), Branch (_, lt2, rt2) ->
                mirror lt1 rt2 (fun isMirrorLeft -> mirror rt1 lt2 (fun isMirrorRight -> cont (isMirrorLeft && isMirrorRight)))
    match tree with
        | Empty -> true
        | Branch (_,lt, rt) -> mirror lt rt id
let insert x tree =
    let rec insert' t cont =
        match t with
            | Empty -> cont <| Branch(x, Empty, Empty)
            | Branch(y, lt, rt) as t ->
                if x < y then
                    insert' lt <| fun lt' -> cont <| Branch(y, lt', rt)
                elif x > y then
                    insert' rt <| fun rt' -> cont <| Branch(y, lt, rt')
                else
                    t
    insert' tree id

let construct xs = xs |> List.fold(fun tree x -> insert x tree) Empty
let symCbalTrees = cbalTree >> List.filter symmetric
let hbalTree a height =
    let rec loop h cont =
        match h with
            | 0 -> cont [Empty, 0]
            | 1 -> cont [Branch (a, Empty, Empty), 1]
            | _ -> loop (h-1) (fun lts ->
                       loop (h-2) (fun rts ->
                       cont <| [let t = lts @ rts
                                for (t1,h1) in t do
                                    for (t2,h2) in t do
                                        let ht = 1 + max h1 h2
                                        if ht = h then
                                            yield Branch (a, t1, t2), ht] ))
    loop height id |> List.map fst
let minNodes height =
    let rec minNodes' h cont =
        match h with
        | 0 -> cont 0
        | 1 -> cont 1
        | _ -> minNodes' (h - 1) <| fun h1 -> minNodes' (h - 2) <| fun h2 -> cont <| 1 + h1 + h2
    minNodes' height id

let maxHeight nodes =
    let rec loop n acc =
        match n with
            | 0 -> acc
            | _ -> loop (n >>> 1) (acc + 1)
    let fullHeight = loop nodes 0 // this is the height of a tree with full nodes
    let minNodesH1 = minNodes (fullHeight + 1)
    if nodes < minNodesH1 then
        fullHeight
    else
        fullHeight + 1

let numNodes tree =
    let rec numNodes' tree cont =
        match tree with
            | Empty -> cont 0
            | Branch(_, lt , rt) ->
                numNodes' lt <| fun ln -> numNodes' rt <| fun rn -> cont <| 1 + ln + rn
    numNodes' tree id

let hbalTreeNodes x nodes =
    let maxH = maxHeight nodes
    let minH = if maxH = 0 then 0 else maxH - 1
    [minH .. maxH] |> List.collect(fun n -> hbalTree x n) |> List.filter(fun t -> nodes = numNodes t)

More information

Link:http://fssnip.net/as
Posted:12 years ago
Author:Cesar Mendoza
Tags: ninety-nine f# problems , tutorial , f# , trees

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.