1 files changed, 27 insertions, 0 deletions
diff --git a/61-69/63.hs b/61-69/63.hs
new file mode 100644
index 0000000..3227cea
--- /dev/null
+++ b/61-69/63.hs
@@ -0,0 +1,27 @@
+import Data.List (foldl')
+
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+completeBinaryTree :: Int -> Tree Char
+completeBinaryTree' :: Int -> Tree Char
+
+-- This one is very slow because it simulates adding n nodes one by one to form
+-- a complete binary tree. Although the time complexity is O(nlogn) for
+-- generating a tree of size n, the use of floating point operations still
+-- slows down the function a lot.
+
+completeBinaryTree n = foldl' (\acc m -> addNode acc m) Empty [0..n-1]
+    where addNode Empty _ = Branch 'x' Empty Empty
+          addNode (Branch x l r) m
+            | i >= ln = Branch x l $ addNode r (i - 1)
+            | otherwise = Branch x (addNode l (m - ln)) r
+            where lvl = floor $ logBase 2 $ fromIntegral $ m + 1
+                  i = m - (2 ^ lvl - 1)
+                  ln = 2 ^ (lvl - 1)
+
+-- This one just grows a heap of size n, which is exactly a complete binary
+-- tree, and the time complexity is O(n).
+completeBinaryTree' n = gen 1
+    where gen x
+            | x > n = Empty
+            | otherwise = Branch 'x' (gen $ x * 2) (gen $ x * 2 + 1)