From 626a548f0ef51b5ee1d3ba049330317f94c89f99 Mon Sep 17 00:00:00 2001
From: Determinant <ted.sybil@gmail.com>
Date: Tue, 30 May 2017 01:28:36 -0400
Subject: ...

---
 61-69/63.hs | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)
 create mode 100644 61-69/63.hs

(limited to '61-69/63.hs')

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)
-- 
cgit v1.2.3