Haskell leftmost deepest node of tree

user_4138074 0
Viewed 130

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)?

nested-lists recursion list nested haskell
2 Answers

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.

user_675790 
[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.

user_8498910
Related