earlonrails · May 7, 2018 00:22 · May 7, 2018
diff --git a/bft.rb b/bft.rb
@@ -0,0 +1,61 @@
+#!/usr/bin/env ruby
+def bft(root)
+  buffer = ""
+  curr_level = 1
+  root[:level] = curr_level
+  q = [root]
+
+  while(q.any?) do
+    node = q.shift
+    if (node[:level] > curr_level)
+      curr_level += 1
+      buffer << "\n"
+    end
+    buffer << node[:value]
+
+    if node[:left]
+      node[:left][:level] = node[:level] + 1
+      q << node[:left]
+    end
+    if node[:right]
+      node[:right][:level] = node[:level] + 1
+      q << node[:right]
+    end
+  end
+
+  buffer
+end
+
+require 'minitest/autorun'
+
+describe 'bft' do
+  before do
+    @tree = {
+      root: {
+        value: "2",
+        left: {
+          value: "3",
+          left: {
+            value: "1"
+          }
+        },
+        right: {
+          value: "4",
+          left: {
+            value: "2"
+          },
+          right: {
+            value: "5"
+          }
+        }
+      }
+    }
+  end
+
+  describe "#bft" do
+    it "should output the tree in levels" do
+      results = bft(@tree[:root])
+      results.must_equal("2\n34\n125")
+    end
+  end
+end