Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 1 / a / Solution

Use pattern matching on the two data constructors, concatenating the left subtree's inorder traversal, the root label, and the right subtree's inorder traversal:

data Tree = Leaf | Fork Tree Int Tree

inorder :: Tree -> [Int]
inorder Leaf = []
inorder (Fork l x r) = inorder l ++ [x] ++ inorder r

Here Leaf represents the empty binary tree, rather than a labelled leaf. The printed declaration uses type; an executable Haskell algebraic data type requires data, as above. By structural induction, the two equations return precisely the prescribed inorder traversal:

inorder (Fork (l, x, r)) = inorder (l) + + [x] + + inorder (r) .

 Ancestors (12)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version