Skip to content

Commit 7a21ac5

Browse files
geon0325goswami-rahul
geon0325
authored and
goswami-rahul
committed
Created Preorder & Postorder traversals in tree (keon#346)
* Create postorder.py * Create preorder.py * Update README.md * Update README_CN.md * Update README_GE.md * Update README_JP.md * Update README_KR.md * Update inorder.py * Update postorder.py * Update preorder.py * Create __init__.py * Update preorder.py * Update postorder.py * Create test_tree.py * Update test_tree.py * Update __init__.py * Update __init__.py * Update test_tree.py
1 parent d4ec1ed commit 7a21ac5

File tree

10 files changed

+141
-0
lines changed

10 files changed

+141
-0
lines changed

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -307,6 +307,8 @@ If you want to uninstall algorithms, it is as simple as:
307307
- [traversal](algorithms/tree/traversal)
308308
- [inorder](algorithms/tree/traversal/inorder.py)
309309
- [level_order](algorithms/tree/traversal/level_order.py)
310+
- [postorder](algorithms/tree/traversal/postorder.py)
311+
- [preorder](algorithms/tree/traversal/preorder.py)
310312
- [zigzag](algorithms/tree/traversal/zigzag.py)
311313
- [trie](algorithms/tree/trie)
312314
- [add_and_search](algorithms/tree/trie/add_and_search.py)

‎README_CN.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -291,6 +291,8 @@ pip3 uninstall -y algorithms
291291
- [traversal：遍历](algorithms/tree/traversal)
292292
- [inorder：中序遍历](algorithms/tree/traversal/inorder.py)
293293
- [level_order：层次遍历](algorithms/tree/traversal/level_order.py)
294+
- [postorder](algorithms/tree/traversal/postorder.py)
295+
- [preorder](algorithms/tree/traversal/preorder.py)
294296
- [zigzag：锯齿形遍历](algorithms/tree/traversal/zigzag.py)
295297
- [tree：树](algorithms/tree/tree.py)
296298
- [trie：字典树](algorithms/tree/trie)

‎README_GE.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -313,6 +313,8 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
313313
- [traversal](algorithms/tree/traversal)
314314
- [inorder](algorithms/tree/traversal/inorder.py)
315315
- [level_order](algorithms/tree/traversal/level_order.py)
316+
- [postorder](algorithms/tree/traversal/postorder.py)
317+
- [preorder](algorithms/tree/traversal/preorder.py)
316318
- [zigzag](algorithms/tree/traversal/zigzag.py)
317319
- [trie](algorithms/tree/trie)
318320
- [add_and_search](algorithms/tree/trie/add_and_search.py)

‎README_JP.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -307,6 +307,8 @@ if __name__ == "__main__":
307307
- [traversal](algorithms/tree/traversal)
308308
- [inorder](algorithms/tree/traversal/inorder.py)
309309
- [level_order](algorithms/tree/traversal/level_order.py)
310+
- [postorder](algorithms/tree/traversal/postorder.py)
311+
- [preorder](algorithms/tree/traversal/preorder.py)
310312
- [zigzag](algorithms/tree/traversal/zigzag.py)
311313
- [trie](algorithms/tree/trie)
312314
- [add_and_search](algorithms/tree/trie/add_and_search.py)

‎README_KR.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -302,6 +302,8 @@ if __name__ == "__main__":
302302
- [traversal : 트리 순회](algorithms/tree/traversal)
303303
- [inorder](algorithms/tree/traversal/inorder.py)
304304
- [level_order](algorithms/tree/traversal/level_order.py)
305+
- [postorder](algorithms/tree/traversal/postorder.py)
306+
- [preorder](algorithms/tree/traversal/preorder.py)
305307
- [zigzag](algorithms/tree/traversal/zigzag.py)
306308
- [trie : 트라이](algorithms/tree/trie)
307309
- [add_and_search](algorithms/tree/trie/add_and_search.py)

‎algorithms/tree/traversal/__init__.py‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
from .preorder import *
2+
from .postorder import *

‎algorithms/tree/traversal/inorder.py‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,7 @@
1+
'''
2+
Time complexity : O(n)
3+
'''
4+
15
class Node:
26

37
def __init__(self, val, left=None, right=None):

‎algorithms/tree/traversal/postorder.py‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
'''
2+
Time complexity : O(n)
3+
'''
4+
5+
class Node:
6+
7+
def __init__(self, val, left=None, right=None):
8+
self.val = val
9+
self.left = left
10+
self.right = right
11+
12+
13+
def postorder(root):
14+
res_temp = []
15+
res = []
16+
if not root:
17+
return res
18+
stack = []
19+
stack.append(root)
20+
while stack:
21+
root = stack.pop()
22+
res_temp.append(root.val)
23+
if root.left:
24+
stack.append(root.left)
25+
if root.right:
26+
stack.append(root.right)
27+
while res_temp:
28+
res.append(res_temp.pop())
29+
return res
30+
31+
# Recursive Implementation
32+
def postorder_rec(root, res=None):
33+
if root is None:
34+
return []
35+
if res is None:
36+
res = []
37+
postorder_rec(root.left, res)
38+
postorder_rec(root.right, res)
39+
res.append(root.val)
40+
return res
41+

‎algorithms/tree/traversal/preorder.py‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
'''
2+
Time complexity : O(n)
3+
'''
4+
5+
class Node:
6+
7+
def __init__(self, val, left=None, right=None):
8+
self.val = val
9+
self.left = left
10+
self.right = right
11+
12+
13+
def preorder(root):
14+
res = []
15+
if not root:
16+
return res
17+
stack = []
18+
stack.append(root)
19+
while stack:
20+
root = stack.pop()
21+
res.append(root.val)
22+
if root.right:
23+
stack.append(root.right)
24+
if root.left:
25+
stack.append(root.left)
26+
return res
27+
28+
# Recursive Implementation
29+
def preorder_rec(root, res=None):
30+
if root is None:
31+
return []
32+
if res is None:
33+
res = []
34+
res.append(root.val)
35+
preorder_rec(root.left, res)
36+
preorder_rec(root.right, res)
37+
return res
38+

‎tests/test_tree.py‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
from algorithms.tree.traversal import (
2+
preorder,
3+
preorder_rec,
4+
postorder,
5+
postorder_rec
6+
)
7+
8+
import unittest
9+
10+
class Node:
11+
12+
def __init__(self, val, left=None, right=None):
13+
self.val = val
14+
self.left = left
15+
self.right = right
16+
17+
18+
class TestTraversal(unittest.TestCase):
19+
20+
def test_preorder(self):
21+
n1 = Node(100)
22+
n2 = Node(50)
23+
n3 = Node(150)
24+
n4 = Node(25)
25+
n5 = Node(75)
26+
n6 = Node(125)
27+
n7 = Node(175)
28+
n1.left, n1.right = n2, n3
29+
n2.left, n2.right = n4, n5
30+
n3.left, n3.right = n6, n7
31+
self.assertEqual([100, 50, 25, 75, 150, 125, 175], preorder(n1))
32+
self.assertEqual([100, 50, 25, 75, 150, 125, 175], preorder_rec(n1))
33+
34+
def test_postorder(self):
35+
n1 = Node(100)
36+
n2 = Node(50)
37+
n3 = Node(150)
38+
n4 = Node(25)
39+
n5 = Node(75)
40+
n6 = Node(125)
41+
n7 = Node(175)
42+
n1.left, n1.right = n2, n3
43+
n2.left, n2.right = n4, n5
44+
n3.left, n3.right = n6, n7
45+
self.assertEqual([25, 75, 50, 125, 175, 150, 100], postorder(n1))
46+
self.assertEqual([25, 75, 50, 125, 175, 150, 100], postorder_rec(n1))

0 commit comments

Comments
 (0)