module PopulatingNextRightPointers where

data BinaryTree a = Node a (BinaryTree a) (BinaryTree a) (BinaryTree a) | Nil deriving Show

--     1
--    / \
--   2   3


test = Node 1 (Node 2 Nil Nil Nil) (Node 3 Nil Nil Nil) Nil

--     1
--    / \
--   2   3
--  / \ / \
-- 4.  56  7
testone = Node 1 (Node 2 (Node 4 Nil Nil Nil) (Node 5 Nil Nil Nil) Nil) (Node 3 (Node 6 Nil Nil Nil) (Node 7 Nil Nil Nil) Nil) Nil

getRightMost:: BinaryTree a -> BinaryTree a
getRightMost Nil = Nil
getRightMost bt@(Node v l r n) = case l of
                                 Nil -> r
                                 _ -> l

modifyBTWithNext :: BinaryTree a -> BinaryTree a -> BinaryTree a
modifyBTWithNext Nil _ = Nil
modifyBTWithNext bt@(Node v l r n) next = case bt of
                                          Nil -> Nil
                                          Node vl ll rl nl -> Node vl ll rl next

connect:: BinaryTree a -> BinaryTree a
connect Nil = Nil
connect bt@(Node v l r n)  =  let newleft = case r of
                                            Nil -> modifyBTWithNext l (getRightMost n)
                                            _ -> modifyBTWithNext l r
                                  newright = modifyBTWithNext r (getRightMost n)
                              in Node v (connect newleft) (connect newright) n