-- EqualBase.hs
-- Hw 4.2(d)

module EqualBase where

data Tree
  = Leaf Int
  | Node Tree Tree
    deriving (Show)
 
-- 3.1. compute the base of a tree -- where the base
-- is the list of values at the leaves from left to right

base1 :: Tree -> [Tree] -> [Int] -> [Int]
base1 (Leaf v) [] fr = v:fr
base1 (Leaf v) (t:stack) fr = base1 t stack (v:fr)
base1 (Node t1 t2) stack fr = base1 t2 (t1:stack) fr

base :: Tree -> [Int]
base tree = base1 tree [] []

-- Note that it recurses down the right branch at
-- a branch node, so that the base is accumulated in the
-- right to left order.


-- 3.2. Test whether two trees have the same list of base values

equalBase1 :: Tree -> [Tree] -> Tree -> [Tree] -> Bool
...

equalBase :: Tree -> Tree -> Bool
...

-- Note that this function is tail recursive. It also recurses
-- simultaneously on two Node trees, traversing them depth-first,
-- left to right.

-- Historically, this problem is known as the "same fringe" problem
-- using the term "fringe" for what is called the base here.  This
-- problem was first proposed by Karl Hewitt of MIT.