Binary Search Tree with size 7 and height 3

Question

I am constructing a binary search tree of size 7 and height 3. I only have to hard-code it, not generate it through a function.

This is the tree that I have hard-coded

Node (Node (Node (Empty, 0, Empty), 1, 
Node (Empty, 3, Empty)), 5
Node (Empty, 7, Node (8, 9, Empty))))

What I want is for Node 9 to have two children (8 and Empty). However, I keep on getting an error on 8 that says "this expression has type int but an expression of was expected of type int tree". How can I correct this?

Thanks!

Andrej Bauer Andrej Bauer · Accepted Answer · 2013-02-02T22:56:47

You cannot write 8 for the leaf. You have to write Node (Empty, 8, Empty).

type tree = Empty | Node of tree * int * tree

(* the tree

           5
         /  \
        /    \
       1      7         
     /  \      \
    0    3      9
               /
              8
*)
let t =
  Node (
    Node (Node (Empty, 0, Empty),
          1, 
          Node (Empty, 3, Empty)),
    5,
    Node (
      Empty,
      7,
      Node (Node (Empty, 8, Empty),
            9,
            Empty)
    )
  )

(* With an auxliary function we can do this to get the same tree: *)

let leaf k = Node (Empty, k, Empty)

let t' =
  Node (
    Node (leaf 0, 1, leaf 3),
    5,
    Node (Empty, 7, Node (leaf 8, 9, Empty)))

Binary Search Tree with size 7 and height 3

2 Answers