CODEWITHSUNDEEP
treeocaml
user2920874
user2920874

Reputation: 31

OCaml - parsing nodes at level in tree

I would like to write all nodes on the level to list.

type 'a tree = T of 'a * 'a tree * 'a tree;;

 let at_level t lvl=
      let rec aux t k =
         match t with
        |Leaf -> []
        |T(x, l, r) -> if k = lvl then 
           (x::aux l (k+1)) @ (aux r (k+1))
        else 
        (aux l (k+1)) @( aux r (k+1))
      in aux t lvl;;

But I always receive the result: [x] where x is value of root. Where is the problem in my program ?

Upvotes: 1

Views: 305

Answers (1)

Marth
Marth

Reputation: 24802

The problem is that you are calling aux t lvl when you should be calling aux t 0, otherwise you'll always have k = lvl from the start (i.e. at the root of the tree).

Also, why do you call aux l (k+1) when you've already found the correct level ? The k = lvl equality can't possibly be true afterwards.

Anyway, here's the code with a few formatting changes :

type 'a tree = T of 'a * 'a tree * 'a tree | Leaf;;

let at_level tree lvl =                                       
  let rec aux t k = match t with                                
    |Leaf -> []                                                   
    |T(value, left, right) when k = lvl -> [value]                
    |T(value, left, right) -> (aux left (k+1)) @ (aux right (k+1))
  in aux tree 0;;


# let tree = T(5,T(6,Leaf,Leaf),T(7,Leaf,Leaf));;
# at_level tree 1;;
- : int list = [6; 7]

Upvotes: 2

Related Questions