From 560bb4c29cbbfd940e2773df0ff28d0315b16517 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 9 Jun 2019 16:51:07 -0500
Subject: tree traversal done (in/pre/post) orders

Not too bad since I worked it out in Java first
---
 sources/tree_traversal.py | 126 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 126 insertions(+)
 create mode 100644 sources/tree_traversal.py

(limited to 'sources/tree_traversal.py')

diff --git a/sources/tree_traversal.py b/sources/tree_traversal.py
new file mode 100644
index 0000000..b75b0f7
--- /dev/null
+++ b/sources/tree_traversal.py
@@ -0,0 +1,126 @@
+# python3
+import queue
+import sys
+
+
+def in_order(key, left, right):
+    keyIndexStack = []
+    result = []
+    walkLeft = True
+
+    currentIndex = 0
+    keyIndexStack.append(currentIndex)
+    while len(keyIndexStack) != 0 or right[currentIndex] != -1:
+        if walkLeft:
+            if left[currentIndex] != -1:
+                currentIndex = left[currentIndex]
+                keyIndexStack.append(currentIndex)
+            else:
+                result.append(key[keyIndexStack.pop()])
+                walkLeft = False
+        else:
+            if right[currentIndex] != -1:
+                currentIndex = right[currentIndex]
+                keyIndexStack.append(currentIndex)
+                walkLeft = True
+            else:
+                if len(keyIndexStack) != 0:
+                    currentIndex = keyIndexStack.pop()
+                    result.append(key[currentIndex])
+    return result
+
+
+def pre_order(key, left, right):
+    keyIndexStack = []
+    keyIndexQueue = queue.Queue()
+    result = []
+
+    walkLeft = True
+    currentIndex = 0
+    keyIndexStack.append(currentIndex)
+    keyIndexQueue.put(currentIndex)
+
+    while len(keyIndexStack) != 0 or right[currentIndex] != -1:
+        if walkLeft:
+            if left[currentIndex] != -1:
+                currentIndex = left[currentIndex]
+                keyIndexQueue.put(currentIndex)
+                keyIndexStack.append(currentIndex)
+            else:
+                keyIndexStack.pop()
+                walkLeft = False
+                result.append(key[keyIndexQueue.get()])
+        else:
+            if right[currentIndex] != -1:
+                currentIndex = right[currentIndex]
+                keyIndexQueue.put(currentIndex)
+                keyIndexStack.append(currentIndex)
+                walkLeft = True
+            else:
+                if len(keyIndexStack) != 0:
+                    currentIndex = keyIndexStack.pop()
+                    result.append(key[keyIndexQueue.get()])
+    return result
+
+
+def post_order(key, left, right):
+    keyIndexStack = []
+    peekedSet = set([])
+    result = []
+
+    walkLeft = True
+    currentIndex = 0
+    keyIndexStack.append(currentIndex)
+    while len(keyIndexStack) != 0:
+        if currentIndex in peekedSet:
+            result.append(key[currentIndex])
+            peekedSet.remove(currentIndex)
+            keyIndexStack.pop()
+            if len(keyIndexStack) == 0:
+                break
+            currentIndex = keyIndexStack[-1]
+            continue
+        if walkLeft:
+            if left[currentIndex] != -1:
+                currentIndex = left[currentIndex]
+                keyIndexStack.append(currentIndex)
+            else:
+                if right[currentIndex] == -1:
+                    result.append(key[currentIndex])
+                    walkLeft = False
+                    keyIndexStack.pop()
+                    currentIndex = keyIndexStack[-1]
+                else:
+                    peekedSet.add(currentIndex)
+                    currentIndex = right[currentIndex]
+                    keyIndexStack.append(currentIndex)
+        else:
+            if right[currentIndex] != -1:
+                peekedSet.add(currentIndex)
+                currentIndex = right[currentIndex]
+                keyIndexStack.append(currentIndex)
+                walkLeft = True
+            else:
+                result.append(key[currentIndex])
+                i = keyIndexStack.pop();
+                if i != currentIndex:
+                    result.append(key[i])
+                if len(keyIndexStack) == 0:
+                    break
+                currentIndex = keyIndexStack[-1]
+    return result
+
+
+if __name__ == '__main__':
+    n = int(sys.stdin.readline())
+    key = [0 for i in range(n)]
+    left = [0 for i in range(n)]
+    right = [0 for i in range(n)]
+    for i in range(n):
+        [a, b, c] = map(int, sys.stdin.readline().split())
+        key[i] = a
+        left[i] = b
+        right[i] = c
+    print(" ".join(str(x) for x in in_order(key, left, right)))
+    print(" ".join(str(x) for x in pre_order(key, left, right)))
+    print(" ".join(str(x) for x in post_order(key, left, right)))
-- 
cgit v1.2.3