CODEWITHSUNDEEP
listhaskellrecursionnestednested-lists
lalessandro
lalessandro

Reputation: 190

Haskell leftmost deepest node of tree

Suppose I have a binary tree structure defined as

data IntTree = Empty | Node Int IntTree IntTree

and the tree

Node 0 (Node 1 Empty Empty)(Node 2 (Node 3 Empty Empty)(Node 4 Empty Empty))

How can I extract the leftmost deepest node (ie Node 3 Empty Empty)?

Upvotes: 2

Views: 164

Answers (2)

Will Ness
Will Ness

Reputation: 71065

[Node 0 (Node 1 Empty Empty)(Node 2 (Node 3 Empty Empty)(Node 4 Empty Empty))]
[        Node 1 Empty Empty, Node 2 (Node 3 Empty Empty)(Node 4 Empty Empty) ]
[               Empty,Empty,         Node 3 Empty Empty, Node 4 Empty Empty  ]
[                                           Empty,Empty,        Empty,Empty  ]
[                                                                            ]

suggests

deepest :: IntTree -> [Int]
deepest  =  pure  >>>  iterate (>>= g)  >>>  takeWhile (not . null) 
                  >>>  reverse  >>>  drop 1  >>>  take 1
                  >>>  (>>= \ xs -> [i | Node i _ _ <- xs])
  where
  g (Node _ lt rt) = [lt, rt]
  g Empty = []

and then we get

> deepest $ Node 0 (Node 1 Empty Empty)
                   (Node 2 (Node 3 Empty Empty) (Node 4 Empty Empty))
[3,4]

so all that's left is to take 1 from that, if you want to.

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476699

You should make use of recursion and define a helper function that returns the depth of the node, then for each innode, you select the deepest child. Such function thus looks like:

leftmostDeep : IntTree -> IntTree
leftmostDeep = fst . go
    where go n@(Node _ Empty Empty) = (n, 0)
          go n@(Node _ Empty r) = let (nr, dr) = go r in (nr, dr+1)
          go n@(Node _ l Empty) = let (nl, dl) = go l in (nl, dl+1)
          go (Node l r) = …
              where (na, da) = go l
              where (nb, db) = go r

where … is left as an exercise. This should determine which item is the deepest, and as tiebreaker, return the left subtree. You should also increment the depth of that node with one.

Upvotes: 5

Related Questions