{- |
Description: In-order and pre-order sequences of binary trees
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Part of Ninety-Nine Haskell "Problems".  Some solutions are in "Solutions.P68".
-}
module Problems.P68 (inorder, preorder, ordersToTree) where

import           Problems.BinaryTrees
import qualified Solutions.P68        as Solution

-- $setup
-- >>> import Problems.P54

{- |
Return the in-order sequence of a binary tree.

=== Examples

>>> inorder tree1
"dbeacgf"
-}
inorder :: Tree a -> [a]
inorder :: forall a. Tree a -> [a]
inorder = Tree a -> [a]
forall a. Tree a -> [a]
Solution.inorder

{- |
Return the pre-order sequence of a binary tree.

=== Examples

>>> preorder tree1
"abdecfg"
-}
preorder :: Tree a -> [a]
preorder :: forall a. Tree a -> [a]
preorder = Tree a -> [a]
forall a. Tree a -> [a]
Solution.preorder

{- |
Given the in-order and pre-order sequences of a binary tree, return the original binary tree.

The values in each node of the binary tree will be distinct,
in which case the tree is determined unambiguously.

=== Examples

>>> ordersToTree "dbeacgf" "abdecfg" == Just tree1
True
-}
ordersToTree :: Eq a
             => [a]  -- ^ In-order sequence
             -> [a]  -- ^ Pre-order sequence
             -> Maybe (Tree a)  -- ^ Binary tree with the given in-order and pre-order sequences
ordersToTree :: forall a. Eq a => [a] -> [a] -> Maybe (Tree a)
ordersToTree = [a] -> [a] -> Maybe (Tree a)
forall a. Eq a => [a] -> [a] -> Maybe (Tree a)
Solution.ordersToTree