Repository: keon/algorithms
Pull request #346 (2018-06-10 04:14:40)

Created Preorder & Postorder traversals in tree
I created two tree traversal algorithms - preorder & postorder. Each of them has two functions recursive and non-recursive. I added sample test in the same file, which is same as inorder traversal.

- [X] **If creating a new file :**
  - [X] added links to it in the README files ?
  - [X] included tests with it ?
  - [X] added description (overview of algorithm, time and space compleixty, and possible edge case) in docstrings ?


coveralls: ## Pull Request Test Coverage Report for [Build 597](https://coveralls.io/builds/17410889)

* **0** of **0**   changed or added relevant lines in **0** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage increased (+**0.04%**) to **69.587%**

---



|  Totals | [![Coverage Status](https://coveralls.io/builds/17410889/badge)](https://coveralls.io/builds/17410889) |
| :-- | --: |
| Change from base [Build 589](https://coveralls.io/builds/17408969): |  0.04% |
| Covered Lines: | 3272 |
| Relevant Lines: | 4702 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/README.md b/README.md
index c954e5f..d85ec44 100644
--- a/README.md
+++ b/README.md
@@ -68,6 +68,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [rotate](algorithms/arrays/rotate.py)
     - [summarize_ranges](algorithms/arrays/summarize_ranges.py)
     - [three_sum](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
 - [backtrack](algorithms/backtrack)
@@ -87,6 +89,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [subsets](algorithms/backtrack/subsets.py)
     - [subsets_unique](algorithms/backtrack/subsets_unique.py)
 - [bfs](algorithms/bfs)
+    - [maze_search](algorithms/bfs/maze_search.py)
     - [shortest_distance_from_all_buildings](algorithms/bfs/shortest_distance_from_all_buildings.py)
     - [word_ladder](algorithms/bfs/word_ladder.py)
 - [bit](algorithms/bit)
@@ -136,6 +139,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
 - [graph](algorithms/graph)
+    - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
     - [clone_graph](algorithms/graph/clone_graph.py)
     - [cycle_detection](algorithms/graph/cycle_detection.py)
@@ -303,6 +307,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)
@@ -324,6 +330,11 @@ If you want to uninstall algorithms, it is as simple as:
     - [pretty_print](algorithms/tree/pretty_print.py)
     - [same_tree](algorithms/tree/same_tree.py)
     - [tree](algorithms/tree/tree.py)
+- [unix](algorithms/unix)
+    - [path](algorithms/unix/path/)
+        - [join_with_slash](algorithms/unix/path/join_with_slash.py)
+        - [full_path](algorithms/unix/path/full_path.py)
+        - [split](algorithms/unix/path/split.py)
 - [union-find](algorithms/union-find)
     - [count_islands](algorithms/union-find/count_islands.py)
 
diff --git a/README_CN.md b/README_CN.md
index 43032d9..b675f6f 100644
--- a/README_CN.md
+++ b/README_CN.md
@@ -85,6 +85,8 @@ pip3 uninstall -y algorithms
     - [rotate：反转数组](algorithms/arrays/rotate.py)
     - [summarize_ranges：数组范围](algorithms/arrays/summarize_ranges.py)
     - [three_sum：三数和为零](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum：两数和](algorithms/arrays/two_sum.py)
     - [move_zeros: 0后置问题](algorithms/arrays/move_zeros.py)
 - [backtrack：回溯](algorithms/backtrack)
@@ -104,6 +106,7 @@ pip3 uninstall -y algorithms
     - [subsets：子集](algorithms/backtrack/subsets.py)
     - [subsets_unique：唯一子集](algorithms/backtrack/subsets_unique.py)
 - [bfs：广度优先搜索](algorithms/bfs)
+    - [maze_search](algorithms/bfs/maze_search.py)
     - [shortest_distance_from_all_buildings：所有建筑物的最短路径：](algorithms/bfs/shortest_distance_from_all_buildings.py)
     - [word_ladder：词语阶梯](algorithms/bfs/word_ladder.py)
 - [bit：位操作](algorithms/bit)
@@ -139,6 +142,7 @@ pip3 uninstall -y algorithms
     - [regex_matching：正则匹配](algorithms/dp/regex_matching.py)
     - [word_break：单词分割](algorithms/dp/word_break.py)
 - [graph：图](graph)
+    - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [2-sat：2-sat](algorithms/graph/satisfiability.py)
     - [clone_graph：克隆图](algorithms/graph/clone_graph.py)
     - [cycle_detection：判断圈算法](algorithms/graph/cycle_detection.py)
@@ -287,6 +291,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
index 529ce79..e21dca3 100644
--- a/README_GE.md
+++ b/README_GE.md
@@ -75,6 +75,8 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [rotate](algorithms/arrays/rotate.py)
     - [summarize_ranges](algorithms/arrays/summarize_ranges.py)
     - [three_sum](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
 - [backtrack](algorithms/backtrack)
@@ -94,6 +96,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [subsets](algorithms/backtrack/subsets.py)
     - [subsets_unique](algorithms/backtrack/subsets_unique.py)
 - [bfs](algorithms/bfs)
+    - [maze_search](algorithms/bfs/maze_search.py)
     - [shortest_distance_from_all_buildings](algorithms/bfs/shortest_distance_from_all_buildings.py)
     - [word_ladder](algorithms/bfs/word_ladder.py)
 - [bit](algorithms/bit)
@@ -143,6 +146,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
 - [graph](algorithms/graph)
+    - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
     - [clone_graph](algorithms/graph/clone_graph.py)
     - [cycle_detection](algorithms/graph/cycle_detection.py)
@@ -309,6 +313,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
index b81f9ce..636d79f 100644
--- a/README_JP.md
+++ b/README_JP.md
@@ -69,6 +69,8 @@ if __name__ == "__main__":
     - [rotate](algorithms/arrays/rotate.py)
     - [summarize_ranges](algorithms/arrays/summarize_ranges.py)
     - [three_sum](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
 - [backtrack : バックトラッキング](algorithms/backtrack)
@@ -88,6 +90,7 @@ if __name__ == "__main__":
     - [subsets](algorithms/backtrack/subsets.py)
     - [subsets_unique](algorithms/backtrack/subsets_unique.py)
 - [bfs : 幅優先探索](algorithms/bfs)
+    - [maze_search](algorithms/bfs/maze_search.py)
     - [shortest_distance_from_all_buildings](algorithms/bfs/shortest_distance_from_all_buildings.py)
     - [word_ladder](algorithms/bfs/word_ladder.py)
 - [bit : ビット](algorithms/bit)
@@ -137,6 +140,7 @@ if __name__ == "__main__":
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
 - [graph : グラフ](algorithms/graph)
+    - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
     - [clone_graph](algorithms/graph/clone_graph.py)
     - [cycle_detection](algorithms/graph/cycle_detection.py)
@@ -303,6 +307,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
index 8487541..b38cdd4 100644
--- a/README_KR.md
+++ b/README_KR.md
@@ -68,6 +68,8 @@ if __name__ == "__main__":
     - [rotate](algorithms/arrays/rotate.py)
     - [summarize_ranges](algorithms/arrays/summarize_ranges.py)
     - [three_sum](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
 - [backtrack : 백트래킹](algorithms/backtrack)
@@ -87,6 +89,7 @@ if __name__ == "__main__":
     - [subsets](algorithms/backtrack/subsets.py)
     - [subsets_unique](algorithms/backtrack/subsets_unique.py)
 - [bfs : 너비 우선 탐색](algorithms/bfs)
+    - [maze_search](algorithms/bfs/maze_search.py)
     - [shortest_distance_from_all_buildings](algorithms/bfs/shortest_distance_from_all_buildings.py)
     - [word_ladder](algorithms/bfs/word_ladder.py)
 - [bit : 비트](algorithms/bit)
@@ -134,6 +137,7 @@ if __name__ == "__main__":
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
 - [graph : 그래프](algorithms/graph)
+    - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
     - [clone_graph](algorithms/graph/clone_graph.py)
     - [cycle_detection](algorithms/graph/cycle_detection.py)
@@ -298,6 +302,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/arrays/__init__.py b/algorithms/arrays/__init__.py
index 64ba130..7e57f63 100644
--- a/algorithms/arrays/__init__.py
+++ b/algorithms/arrays/__init__.py
@@ -11,4 +11,6 @@ from .plus_one import *
 from .rotate import *
 from .summarize_ranges import *
 from .three_sum import *
+from .trimmean import *
+from .top_1 import *
 from .two_sum import *
diff --git a/algorithms/arrays/top_1.py b/algorithms/arrays/top_1.py
new file mode 100644
index 0000000..dea9aa2
--- /dev/null
+++ b/algorithms/arrays/top_1.py
@@ -0,0 +1,32 @@
+"""
+this algorithms receive array and check most_frequent_value(a.k.a mode). Also, sometimes it can be have numerous most_frequent_value,
+so this funtion returns list. This result can be used as finding representative value on array.
+
+This algorithms get array, and make dictionary of it, find most frequent count, and make result list.
+
+For example) top_1([1, 1, 2, 2, 3, 4]) will return [1, 2]
+
+Complexity: O(n)
+"""
+def top_1(arr):
+    values = {}
+    #reserve each value which first appears on keys
+    #reserve how many time each value appears by index number on values
+    result = []
+    f_val = 0
+
+    for i in arr:
+        if i in values:
+            values[i] += 1
+        else:
+            values[i] = 1
+
+    f_val = max(values.values())
+        
+    for i in values.keys():
+        if values[i] == f_val:
+            result.append(i)
+        else:
+            continue
+    
+    return result
diff --git a/algorithms/arrays/trimmean.py b/algorithms/arrays/trimmean.py
new file mode 100644
index 0000000..4cea0db
--- /dev/null
+++ b/algorithms/arrays/trimmean.py
@@ -0,0 +1,22 @@
+"""
+When make reliable means, we need to neglect best and worst value. For example, when making average score on athletes we need this option.
+So, this algorithms, fix some percentage to neglect when making mean. For example, if you suggest 20%, it will neglect best 10% value, and
+worst 10% value.
+
+This algorithm gets array and percentage to neglect. After sorted, if index of array is larger or smaller or wanted ratio, we don't
+compute it.
+
+Compleity: O(n)
+"""
+def trimmean(arr, per):
+    ratio = per/200
+    # /100 for easy calculation by *, and /2 for easy adaption to best and worst parts.
+    cal_sum = 0
+    # sum value to be calculated to trimmean.
+    arr.sort()
+    neg_val = int(len(arr)*ratio)
+    arr = arr[neg_val:len(arr)-neg_val]
+    for i in arr:
+        cal_sum += i
+    #print(cal_sum, len(arr))
+    return cal_sum/len(arr)
diff --git a/algorithms/bfs/__init__.py b/algorithms/bfs/__init__.py
new file mode 100644
index 0000000..b3d3b0c
--- /dev/null
+++ b/algorithms/bfs/__init__.py
@@ -0,0 +1,3 @@
+from .maze_search import *
+from .shortest_distance_from_all_buildings import *
+from .word_ladder import *
diff --git a/algorithms/bfs/maze_search.py b/algorithms/bfs/maze_search.py
new file mode 100644
index 0000000..efa65c3
--- /dev/null
+++ b/algorithms/bfs/maze_search.py
@@ -0,0 +1,33 @@
+'''
+BFS time complexity : O(|E|)
+BFS space complexity : O(|V|)
+
+do BFS from (0,0) of the grid and get the minimum number of steps needed to get to the lower right column
+
+only step on the columns whose value is 1
+
+if there is no path, it returns -1
+'''
+
+def maze_search(grid):
+    dx = [0,0,-1,1]
+    dy = [-1,1,0,0]
+    n = len(grid)
+    m = len(grid[0])
+    q = [(0,0,0)]
+    visit = [[0]*m for _ in range(n)]
+    if grid[0][0] == 0:
+        return -1
+    visit[0][0] = 1
+    while q:
+        i, j, step = q.pop(0)
+        if i == n-1 and j == m-1:
+            return step
+        for k in range(4):
+            x = i + dx[k]
+            y = j + dy[k]
+            if x>=0 and x<n and y>=0 and y<m:
+                if grid[x][y] ==1 and visit[x][y] == 0:
+                    visit[x][y] = 1
+                    q.append((x,y,step+1))
+    return -1
diff --git a/algorithms/graph/__init__.py b/algorithms/graph/__init__.py
index bfb208e..f94f12c 100644
--- a/algorithms/graph/__init__.py
+++ b/algorithms/graph/__init__.py
@@ -1,1 +1,2 @@
 from .tarjan import *
+from .check_bipartite import *
diff --git a/algorithms/graph/check_bipartite.py b/algorithms/graph/check_bipartite.py
new file mode 100644
index 0000000..dacc003
--- /dev/null
+++ b/algorithms/graph/check_bipartite.py
@@ -0,0 +1,39 @@
+"""
+
+Bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets.
+(https://en.wikipedia.org/wiki/Bipartite_graph)
+
+Time complexity is O(|E|)
+Space complexity is O(|V|)
+
+"""
+
+def check_bipartite(adj_list):
+
+    V = len(adj_list)
+
+    # Divide vertexes in the graph into set_type 1 and 2
+    # Initialize all set_types as -1
+    set_type = [-1 for v in range(V)]
+    set_type[0] = 0
+
+    q = [0]
+
+    while q:
+        v = q.pop(0)
+
+        # If there is a self-loop, it cannot be bipartite
+        if adj_list[v][v]:
+            return False
+
+        for u in range(V):
+            if adj_list[v][u]:
+                if set_type[u] == set_type[v]:
+                    return False
+                elif set_type[u] == -1:
+                    # set type of u opposite of v
+                    set_type[u] = 1 - set_type[v]
+                    q.append(u)
+
+    return True
+
diff --git a/algorithms/queues/priority_queue.py b/algorithms/queues/priority_queue.py
index a28ae96..76b0815 100644
--- a/algorithms/queues/priority_queue.py
+++ b/algorithms/queues/priority_queue.py
@@ -3,37 +3,54 @@ Implementation of priority queue using linear array.
 Insertion - O(n)
 Extract min/max Node - O(1)
 """
-import collections
+import itertools
 
 
 class PriorityQueueNode:
-	def __init__(self, data, priority):
-		self.data = data
-		self.priority = priority
+    def __init__(self, data, priority):
+        self.data = data
+        self.priority = priority
+
+    def __repr__(self):
+        return "{}: {}".format(self.data, self.priority)
 
-	def __repr__(self):
-		return str(self.data) + ": " + str(self.priority)
 
 class PriorityQueue:
-	def __init__(self):
-		self.priority_queue_list = collections.deque()
-
-	def __repr__(self):
-	    return "PriorityQueue({!r})".format(list(self.priority_queue_list))
-
-	def size(self):
-		return len(self.priority_queue_list)
-
-	def push(self, item, priority=None):
-		priority = item if priority is None else priority
-		node = PriorityQueueNode(item, priority)
-		for index, current in enumerate(self.priority_queue_list):
-			if current.priority > node.priority:
-				self.priority_queue_list.insert(index, node)
-				return
-		# when traversed complete queue
-		self.priority_queue_list.append(node)
-
-	def pop(self):
-		# remove and return the first node from the queue
-		return self.priority_queue_list.popleft()
+    def __init__(self, items=None, priorities=None):
+        """Create a priority queue with items (list or iterable).
+        If items is not passed, create empty priority queue."""
+        self.priority_queue_list = []
+        if items is None:
+            return
+        if priorities is None:
+            priorities = itertools.repeat(None)
+        for item, priority in zip(items, priorities):
+            self.push(item, priority=priority)
+
+    def __repr__(self):
+        return "PriorityQueue({!r})".format(self.priority_queue_list)
+
+    def size(self):
+        """Return size of the priority queue.
+        """
+        return len(self.priority_queue_list)
+
+    def push(self, item, priority=None):
+        """Push the item in the priority queue.
+        if priority is not given, priority is set to the value of item.
+        """
+        priority = item if priority is None else priority
+        node = PriorityQueueNode(item, priority)
+        for index, current in enumerate(self.priority_queue_list):
+            if current.priority < node.priority:
+                self.priority_queue_list.insert(index, node)
+                return
+        # when traversed complete queue
+        self.priority_queue_list.append(node)
+
+    def pop(self):
+        """Remove and return the item with the lowest priority.
+        """
+        # remove and return the first node from the queue
+        return self.priority_queue_list.pop().data
+
diff --git a/algorithms/tree/traversal/__init__.py b/algorithms/tree/traversal/__init__.py
new file mode 100644
index 0000000..df3c88c
--- /dev/null
+++ 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
index 4883c0f..17cadaf 100644
--- 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
new file mode 100644
index 0000000..b89293b
--- /dev/null
+++ 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
new file mode 100644
index 0000000..45346ba
--- /dev/null
+++ 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/algorithms/unix/__init__.py b/algorithms/unix/__init__.py
new file mode 100644
index 0000000..68b785c
--- /dev/null
+++ b/algorithms/unix/__init__.py
@@ -0,0 +1,3 @@
+from .path.join_with_slash import *
+from .path.full_path import *
+from .path.split import *
diff --git a/algorithms/unix/path/full_path.py b/algorithms/unix/path/full_path.py
new file mode 100644
index 0000000..3bf109e
--- /dev/null
+++ b/algorithms/unix/path/full_path.py
@@ -0,0 +1,6 @@
+"""
+Get a full absolute path a file
+"""
+import os
+def full_path(file):
+    return os.path.abspath(os.path.expanduser(file))
diff --git a/algorithms/unix/path/join_with_slash.py b/algorithms/unix/path/join_with_slash.py
new file mode 100644
index 0000000..beec8d1
--- /dev/null
+++ b/algorithms/unix/path/join_with_slash.py
@@ -0,0 +1,18 @@
+"""
+Both URL and file path joins use slashes as dividers between their parts.
+For example:
+
+path/to/dir + file --> path/to/dir/file
+path/to/dir/ + file --> path/to/dir/file
+http://algorithms.com/ + part --> http://algorithms.com/part
+http://algorithms.com + part --> http://algorithms/part
+"""
+import os
+
+def join_with_slash(base, suffix):
+    # Remove / trailing
+    base = base.rstrip('/')
+    # Remove / leading
+    suffix = suffix.lstrip('/').rstrip()
+    full_path = "{}/{}".format(base, suffix)
+    return full_path
diff --git a/algorithms/unix/path/split.py b/algorithms/unix/path/split.py
new file mode 100644
index 0000000..168b120
--- /dev/null
+++ b/algorithms/unix/path/split.py
@@ -0,0 +1,23 @@
+"""
+Splitting a path into 2 parts
+Example:
+Input: https://algorithms/unix/test.py   (for url)
+Output:
+    part[0]: https://algorithms/unix
+    part[1]: test.py
+
+Input: algorithms/unix/test.py          (for file path)
+Output:
+    part[0]: algorithms/unix
+    part[1]: test.py
+"""
+import os
+
+def split(path):
+    parts = []
+    split_part = path.rpartition('/')
+    # Takt the origin path without the last part
+    parts.append(split_part[0])
+    # Take the last element of list
+    parts.append(split_part[2])
+    return parts


Test patch:
diff --git a/tests/test_array.py b/tests/test_array.py
index ed398bc..e3f6f6d 100644
--- a/tests/test_array.py
+++ b/tests/test_array.py
@@ -12,7 +12,9 @@ from algorithms.arrays import (
     summarize_ranges,
     three_sum,
     two_sum,
-    max_ones_index
+    max_ones_index,
+    trimmean,
+    top_1
 )
 
 import unittest
@@ -306,6 +308,20 @@ class TestSuite(unittest.TestCase):
         self.assertTupleEqual((0, 3), two_sum([-3, 5, 2, 3, 8, -9], target=0))
 
         self.assertIsNone(two_sum([-3, 5, 2, 3, 8, -9], target=6))
+        
+class TestTrimmean(unittest.TestCase):
+
+    def test_trimmean(self):
+
+        self.assertEqual(trimmean([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 20), 5.5)
+        self.assertEqual(trimmean([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], 20), 6.0)
+        
+class TestTop1(unittest.TestCase):
+    
+    def test_top_1(self):
+        self.assertListEqual(top_1([1 , 1, 2, 2, 3]), [1, 2])
+        self.assertListEqual(top_1([1, 2, 3, 324, 234, 23, 23, 1, 23, 23]), [23])
+
 
 
 if __name__ == '__main__':
diff --git a/tests/test_bfs.py b/tests/test_bfs.py
new file mode 100644
index 0000000..129d6d0
--- /dev/null
+++ b/tests/test_bfs.py
@@ -0,0 +1,18 @@
+from algorithms.bfs import (
+    maze_search,
+    shortest_distance_from_all_buildings,
+    word_ladder
+)
+
+import unittest
+
+class TestMazeSearch(unittest.TestCase):
+    
+    def test_maze_search(self):
+        grid_1 = [[1,0,1,1,1,1],[1,0,1,0,1,0],[1,0,1,0,1,1],[1,1,1,0,1,1]]
+        self.assertEqual(14, maze_search(grid_1))
+        grid_2 = [[1,0,0],[0,1,1],[0,1,1]]
+        self.assertEqual(-1, maze_search(grid_2))
+        
+if __name__ == "__main__":
+    unittest.main()
diff --git a/tests/test_graph.py b/tests/test_graph.py
index 63937db..d402b86 100644
--- a/tests/test_graph.py
+++ b/tests/test_graph.py
@@ -1,4 +1,5 @@
 from algorithms.graph import Tarjan
+from algorithms.graph import check_bipartite
 
 import unittest
 
@@ -42,3 +43,17 @@ class TestTarjan(unittest.TestCase):
 
         g = Tarjan(example)
         self.assertEqual(g.sccs, [['A', 'B', 'E'], ['C', 'D'], ['F', 'G'], ['H']])
+
+        
+class TestCheckBipartite(unittest.TestCase):
+    
+    def test_check_bipartite(self):
+        
+        adj_list_1 = [[0, 0, 1], [0, 0, 1], [1, 1, 0]]
+        self.assertEqual(True, check_bipartite(adj_list_1))
+        
+        adj_list_2 = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0]]
+        self.assertEqual(True, check_bipartite(adj_list_2))
+        
+        adj_list_3 = [[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]]
+        self.assertEqual(False, check_bipartite(adj_list_3))
diff --git a/tests/test_queues.py b/tests/test_queues.py
index 2c85c45..b5b49ef 100644
--- a/tests/test_queues.py
+++ b/tests/test_queues.py
@@ -1,11 +1,12 @@
+import unittest
+
 from algorithms.queues import (
     ArrayQueue, LinkedListQueue,
     max_sliding_window,
     reconstruct_queue,
-    PriorityQueue, PriorityQueueNode
+    PriorityQueue
 )
 
-import unittest
 
 class TestQueue(unittest.TestCase):
     """
@@ -70,10 +71,9 @@ class TestQueue(unittest.TestCase):
 
         self.assertTrue(queue.is_empty())
 
-class TestSuite(unittest.TestCase):
 
+class TestSuite(unittest.TestCase):
     def test_max_sliding_window(self):
-
         array = [1, 3, -1, -3, 5, 3, 6, 7]
         self.assertEqual(max_sliding_window(array, k=5), [5, 5, 6, 7])
         self.assertEqual(max_sliding_window(array, k=3), [3, 3, 5, 5, 6, 7])
@@ -85,24 +85,23 @@ class TestSuite(unittest.TestCase):
         self.assertEqual(max_sliding_window(array, k=2), [8, 10, 10, 9, 9, 15, 15, 90, 90])
 
     def test_reconstruct_queue(self):
-        self.assertEqual([[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]],
-                         reconstruct_queue([[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]))
+        self.assertEqual([[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]],
+                         reconstruct_queue([[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]))
 
-"""
-    TODO: Refactor PriorityQueue because insert method does not work for python3.4
-class TestPriorityQueue(unittest.TestCase):
 
-        Test suite for the PriorityQueue data structures.
+class TestPriorityQueue(unittest.TestCase):
+    """Test suite for the PriorityQueue data structures.
+    """
 
     def test_PriorityQueue(self):
-        queue = PriorityQueue()
-        queue.push(3)
-        queue.push(4)
-        queue.push(1)
-        queue.push(6)
-        self.assertEqual(4,queue.size())
-        self.assertEqual(str(1) + ": " + str(1),str(queue.pop()))
-"""
-if __name__ == "__main__":
+        queue = PriorityQueue([3, 4, 1, 6])
+        self.assertEqual(4, queue.size())
+        self.assertEqual(1, queue.pop())
+        self.assertEqual(3, queue.size())
+        queue.push(2)
+        self.assertEqual(4, queue.size())
+        self.assertEqual(2, queue.pop())
+
 
+if __name__ == "__main__":
     unittest.main()
diff --git a/tests/test_tree.py b/tests/test_tree.py
new file mode 100644
index 0000000..a9d53ca
--- /dev/null
+++ 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))
diff --git a/tests/test_unix.py b/tests/test_unix.py
new file mode 100644
index 0000000..a243889
--- /dev/null
+++ b/tests/test_unix.py
@@ -0,0 +1,35 @@
+from algorithms.unix import (
+    join_with_slash,
+    full_path,
+    split
+)
+import os
+import unittest
+class TestUnixPath(unittest.TestCase):
+    def test_join_with_slash(self):
+        self.assertEqual("path/to/dir/file", join_with_slash("path/to/dir/", "file"))
+        self.assertEqual("path/to/dir/file", join_with_slash("path/to/dir", "file"))
+        self.assertEqual("http://algorithms/part", join_with_slash("http://algorithms", "part"))
+        self.assertEqual("http://algorithms/part", join_with_slash("http://algorithms/", "part"))
+
+    def test_full_path(self):
+        file_name = "file_name"
+        # Test full path relative
+        expect_path = "{}/{}".format(os.getcwd(), file_name)
+        self.assertEqual(expect_path, full_path(file_name))
+        # Test full path with expanding user
+        # ~/file_name
+        expect_path = "{}/{}".format(os.path.expanduser('~'), file_name)
+        self.assertEqual(expect_path, full_path("~/{}".format(file_name)))
+
+    def test_split(self):
+        # Test url path
+        path = "https://algorithms/unix/test.py"
+        expect_result = split(path)
+        self.assertEqual("https://algorithms/unix", expect_result[0])
+        self.assertEqual("test.py", expect_result[1])
+        # Test file path
+        path = "algorithms/unix/test.py"
+        expect_result = split(path)
+        self.assertEqual("algorithms/unix", expect_result[0])
+        self.assertEqual("test.py", expect_result[1])