Add 'universe/' from commit '8ad51b24dd8719840aac47134835ea25cfe1b0b8'

git-subtree-dir: universe
git-subtree-mainline: 15110e6de9f85537c7847267caa35fa068aea001
git-subtree-split: 8ad51b24dd8719840aac47134835ea25cfe1b0b8

1 files changed, 65 insertions, 0 deletions

diff --git a/universe/data_structures_and_algorithms/dft.py b/universe/data_structures_and_algorithms/dft.py
new file mode 100644
index 000000000000..127d48c1864b
--- /dev/null
+++ b/universe/data_structures_and_algorithms/dft.py
@@ -0,0 +1,65 @@
+from random import choice
+
+
+class Node(object):
+    def __init__(self, value=None, left=None, right=None):
+        self.value = value
+        self.left = left
+        self.right = left
+
+
+def p(node, indent=0):
+    print(indent * ' ' + '|-' + str(node.value))
+    if node.left is not None:
+        p(node.left, indent=indent + 2)
+    if node.right is not None:
+        p(node.right, indent=indent + 2)
+
+
+# read trees (i.e. traversing, parsing)
+# write trees (i.e. generating, printing)
+def random(d=0):
+    left = None
+    right = None
+
+    if choice([True, False]):
+        left = random(d + 1)
+
+    if choice([True, False]):
+        right = random(d + 1)
+
+    return Node(
+        value=d,
+        left=left,
+        right=right,
+    )
+
+
+################################################################################
+# DFTs can be:
+# - imperative (mutable)
+# - functional (immutable)
+# - iterative
+# - recursive
+################################################################################
+
+
+# Iterative
+def traverse(node, f):
+    stack = [(node, 0)]
+
+    while len(stack):
+        node, depth = stack.pop()
+        f(node, depth)
+        print(depth)
+
+        if node.left is not None:
+            stack.append((node.left, depth + 1))
+        if node.right is not None:
+            stack.append((node.right, depth + 1))
+
+
+print('----------------------------------------------------------------------')
+for _ in range(10):
+    traverse(random(), lambda _, d: print(d))
+print()