Added medium/preorder_traversal

bradhanson · bradhanson · commit 8310d9255bdd · 2018-07-12T15:43:16.000-04:00
diff --git a/medium/preorder_traversal.js b/medium/preorder_traversal.js
@@ -0,0 +1,41 @@
+/**
+ * Using the JavaScript language, have the function preorderTraversal(strArr)
+ * take the array of strings stored in strArr, which will represent a binary
+ * tree with integer values in a format similar to how a binary heap is
+ * implemented with NULL nodes at any level represented with a #. Your goal is
+ * to return the pre-order traversal of the tree with the elements separated by
+ * a space. For example: if strArr is ["5", "2", "6", "1", "9", "#", "8", "#",
+ * "#", "#", "#", "4", "#"] then this tree looks like the following tree:
+ *
+ * [Image of Example Tree](https://i.imgur.com/Lcy6mtO.png)
+ *
+ * For the input above, your program should return the string 5 2 1 9 6 8 4
+ * because that is the pre-order traversal of the tree.
+ * @param  {array} strArr
+ * @return {string}
+ */
+function preorderTraversal(strArr) {
+    // https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation
+
+    const preorderArr = preorder(strArr);
+
+    return preorderArr.join(' ');
+}
+
+function preorder(strArr, index = 0) {
+    const currentNode = strArr[index];
+
+    if (index >= strArr.length || currentNode === '#') {
+        return [];
+    }
+
+    const left = preorder(strArr, 2 * index + 1);
+    const right = preorder(strArr, 2 * index + 2);
+
+    const nodeAndChildren = [];
+    nodeAndChildren.push(currentNode, ...left, ...right);
+
+    return nodeAndChildren;
+}
+
+module.exports = preorderTraversal;
diff --git a/medium/preorder_traversal.test.js b/medium/preorder_traversal.test.js
@@ -0,0 +1,10 @@
+const preorderTraversal = require('./preorder_traversal');
+
+describe('preorderTraversal()', () => {
+    test('correctly returns preorder traversal given binary heap', () => {
+        expect(preorderTraversal(['4', '1', '5', '2', '#', '#', '#'])).toBe(
+            '4 1 2 5'
+        );
+        expect(preorderTraversal(['2', '6', '#'])).toBe('2 6');
+    });
+});
