keon · goswami-rahul · Jun 10, 2018 · Jun 10, 2018 · Jun 10, 2018 · Jun 10, 2018
diff --git a/README.md b/README.md
@@ -303,6 +303,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [traversal](algorithms/tree/traversal)
         - [inorder](algorithms/tree/traversal/inorder.py)
         - [level_order](algorithms/tree/traversal/level_order.py)
+        - [postorder](algorithms/tree/traversal/postorder.py)
+        - [preorder](algorithms/tree/traversal/preorder.py)
         - [zigzag](algorithms/tree/traversal/zigzag.py)
     - [trie](algorithms/tree/trie)
         - [add_and_search](algorithms/tree/trie/add_and_search.py)

diff --git a/README_CN.md b/README_CN.md
@@ -287,6 +287,8 @@ pip3 uninstall -y algorithms
     - [traversal：遍历](algorithms/tree/traversal)
         - [inorder：中序遍历](algorithms/tree/traversal/inorder.py)
         - [level_order：层次遍历](algorithms/tree/traversal/level_order.py)
+        - [postorder](algorithms/tree/traversal/postorder.py)
+        - [preorder](algorithms/tree/traversal/preorder.py)
         - [zigzag：锯齿形遍历](algorithms/tree/traversal/zigzag.py)
     - [tree：树](algorithms/tree/tree.py)
     - [trie：字典树](algorithms/tree/trie)

diff --git a/README_GE.md b/README_GE.md
@@ -309,6 +309,8 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [traversal](algorithms/tree/traversal)
         - [inorder](algorithms/tree/traversal/inorder.py)
         - [level_order](algorithms/tree/traversal/level_order.py)
+        - [postorder](algorithms/tree/traversal/postorder.py)
+        - [preorder](algorithms/tree/traversal/preorder.py)
         - [zigzag](algorithms/tree/traversal/zigzag.py)
     - [trie](algorithms/tree/trie)
         - [add_and_search](algorithms/tree/trie/add_and_search.py)

diff --git a/README_JP.md b/README_JP.md
@@ -303,6 +303,8 @@ if __name__ == "__main__":
     - [traversal](algorithms/tree/traversal)
         - [inorder](algorithms/tree/traversal/inorder.py)
         - [level_order](algorithms/tree/traversal/level_order.py)
+        - [postorder](algorithms/tree/traversal/postorder.py)
+        - [preorder](algorithms/tree/traversal/preorder.py)
         - [zigzag](algorithms/tree/traversal/zigzag.py)
     - [trie](algorithms/tree/trie)
         - [add_and_search](algorithms/tree/trie/add_and_search.py)

diff --git a/README_KR.md b/README_KR.md
@@ -298,6 +298,8 @@ if __name__ == "__main__":
     - [traversal : 트리 순회](algorithms/tree/traversal)
         - [inorder](algorithms/tree/traversal/inorder.py)
         - [level_order](algorithms/tree/traversal/level_order.py)
+        - [postorder](algorithms/tree/traversal/postorder.py)
+        - [preorder](algorithms/tree/traversal/preorder.py)
         - [zigzag](algorithms/tree/traversal/zigzag.py)
     - [trie : 트라이](algorithms/tree/trie)
         - [add_and_search](algorithms/tree/trie/add_and_search.py)

diff --git a/algorithms/tree/traversal/__init__.py b/algorithms/tree/traversal/__init__.py
@@ -0,0 +1,2 @@
+from .preorder import *
+from .postorder import *
diff --git a/algorithms/tree/traversal/inorder.py b/algorithms/tree/traversal/inorder.py
@@ -1,3 +1,7 @@
+'''
+Time complexity : O(n)
+'''
+
 class Node:
 
     def __init__(self, val, left=None, right=None):

diff --git a/algorithms/tree/traversal/postorder.py b/algorithms/tree/traversal/postorder.py
@@ -0,0 +1,41 @@
+'''
+Time complexity : O(n)
+'''
+
+class Node:
+
+    def __init__(self, val, left=None, right=None):
+        self.val = val
+        self.left = left
+        self.right = right
+
+
+def postorder(root):
+    res_temp = []
+    res = []
+    if not root:
+        return res
+    stack = []
+    stack.append(root)
+    while stack:
+        root = stack.pop()
+        res_temp.append(root.val)
+        if root.left:
+            stack.append(root.left)
+        if root.right:
+            stack.append(root.right)
+    while res_temp:
+        res.append(res_temp.pop())
+    return res
+
+# Recursive Implementation
+def postorder_rec(root, res=None):
+    if root is None:
+        return []
+    if res is None:
+        res = []
+    postorder_rec(root.left, res)
+    postorder_rec(root.right, res)
+    res.append(root.val)
+    return res
+
diff --git a/algorithms/tree/traversal/preorder.py b/algorithms/tree/traversal/preorder.py
@@ -0,0 +1,38 @@
+'''
+Time complexity : O(n)
+'''
+
+class Node:
+
+    def __init__(self, val, left=None, right=None):
+        self.val = val
+        self.left = left
+        self.right = right
+
+
+def preorder(root):
+    res = []
+    if not root:
+        return res
+    stack = []
+    stack.append(root)
+    while stack:
+        root = stack.pop()
+        res.append(root.val)
+        if root.right:
+            stack.append(root.right)
+        if root.left:
+            stack.append(root.left)
+    return res
+
+# Recursive Implementation
+def preorder_rec(root, res=None):
+    if root is None:
+        return []
+    if res is None:
+        res = []
+    res.append(root.val)
+    preorder_rec(root.left, res)
+    preorder_rec(root.right, res)
+    return res
+
diff --git a/tests/test_tree.py b/tests/test_tree.py
@@ -0,0 +1,46 @@
+from algorithms.tree.traversal import (
+    preorder,
+    preorder_rec,
+    postorder,
+    postorder_rec
+)
+
+import unittest
+
+class Node:
+
+    def __init__(self, val, left=None, right=None):
+        self.val = val
+        self.left = left
+        self.right = right
+
+
+class TestTraversal(unittest.TestCase):
+
+    def test_preorder(self):
+        n1 = Node(100)
+        n2 = Node(50)
+        n3 = Node(150)
+        n4 = Node(25)
+        n5 = Node(75)
+        n6 = Node(125)
+        n7 = Node(175)
+        n1.left, n1.right = n2, n3
+        n2.left, n2.right = n4, n5
+        n3.left, n3.right = n6, n7
+        self.assertEqual([100, 50, 25, 75, 150, 125, 175], preorder(n1))
+        self.assertEqual([100, 50, 25, 75, 150, 125, 175], preorder_rec(n1))
+
+    def test_postorder(self):
+        n1 = Node(100)
+        n2 = Node(50)
+        n3 = Node(150)
+        n4 = Node(25)
+        n5 = Node(75)
+        n6 = Node(125)
+        n7 = Node(175)
+        n1.left, n1.right = n2, n3
+        n2.left, n2.right = n4, n5
+        n3.left, n3.right = n6, n7
+        self.assertEqual([25, 75, 50, 125, 175, 150, 100], postorder(n1))
+        self.assertEqual([25, 75, 50, 125, 175, 150, 100], postorder_rec(n1))
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,2 @@
		from .preorder import *
		from .postorder import *