{- | 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