Level Order tree traversal

kumaya · kumaya · commit 341e36f8e9aa · 2017-08-23T19:01:35.000+05:30
diff --git a/TreeADT/reverseLevelOrderTraversal.py b/TreeADT/reverseLevelOrderTraversal.py
@@ -0,0 +1,43 @@
+# Reverse Level order tree traversal
+
+from BinaryTree import TreeNode
+
+
+def reverseLevelOrderTraversal(root):
+    S = []
+    Q = []
+
+    # add first node in queue as entry point
+    Q.append(root)
+
+    while len(Q) > 0:
+        root = Q.pop(0)
+        S.append(root)
+
+
+        # If right node, add to queue
+        # Right first, since we want to pop it later as comparred to left nodes
+        if root.right_node:
+            Q.append(root.right_node)
+
+        # If left node, add to queue
+        if root.left_node:
+            Q.append(root.left_node)
+
+
+    while len(S) > 0:
+        root = S.pop()
+        print root.data,
+
+
+if __name__ == "__main__":
+    bTree = TreeNode(1)
+    bTree.left_node = TreeNode(2)
+    bTree.right_node = TreeNode(3)
+    bTree.left_node.left_node = TreeNode(4)
+    bTree.left_node.right_node = TreeNode(5)
+    bTree.right_node.left_node = TreeNode(6)
+    bTree.left_node.left_node.left_node = TreeNode(12)
+
+    print "Reverse Level order traversal: ",
+    reverseLevelOrderTraversal(bTree)
diff --git a/TreeADT/reverseParentTree.py b/TreeADT/reverseParentTree.py
@@ -1,43 +1,45 @@
-# Reverse Level order tree traversal
-
-from BinaryTree import TreeNode
-
-
-def reverseLevelOrderTraversal(root):
-    S = []
-    Q = []
-
-    # add first node in queue as entry point
-    Q.append(root)
-
-    while len(Q) > 0:
-        root = Q.pop(0)
-        S.append(root)
-
-
-        # If right node, add to queue
-        # Right first, since we want to pop it later as comparred to left nodes
-        if root.right_node:
-            Q.append(root.right_node)
-
-        # If left node, add to queue
-        if root.left_node:
-            Q.append(root.left_node)
-
-
-    while len(S) > 0:
-        root = S.pop()
-        print root.data,
-
-
-if __name__ == "__main__":
-    bTree = TreeNode(1)
-    bTree.left_node = TreeNode(2)
-    bTree.right_node = TreeNode(3)
-    bTree.left_node.left_node = TreeNode(4)
-    bTree.left_node.right_node = TreeNode(5)
-    bTree.right_node.left_node = TreeNode(6)
-    bTree.left_node.left_node.left_node = TreeNode(12)
-
-    print "Reverse Level order traversal: ",
-    reverseLevelOrderTraversal(bTree)
+"""
+@Problem Statement:
+One of the many ways of representing a tree is to have an array(of length same as number of nodes), 
+where each element in the node denotes the parent of that node.
+{-1, 0, 0, 1, 1} would represent a tree with -
+    * 0 as root
+    * 1 and 2 as children of 0
+    * 3 and 4 as children of 1
+Given a similar representation, print reverse level order traversal of the corresponding tree.
+Level order traversal of a tree is where we traverse levels of tree one by one.
+@Input:
+N: Length of tree
+treeNode: representation of tree
+"""
+
+
+def reverse_parent_tree(tree, root):
+    # base case for recursive call
+    if len(tree) == 0:
+        return
+
+    ret = tree
+    tree = []
+    for node in ret:
+        if node in root:
+            tree += root[node]
+    reverse_parent_tree(tree, root)
+    print " ".join(ret)
+
+
+# N = 5
+# treeNode = ['-1', '0', '0', '2', '1']
+N = 9
+treeNode = ['8', '7', '0', '5', '5', '8', '7', '0', '-1']
+parent = {}
+
+for index,val in enumerate(treeNode):
+    if val in parent:
+        parent[val].append(str(index))
+    else:
+        parent[val] = [str(index)]
+
+# print parent
+
+reverse_parent_tree(parent['-1'], parent)
diff --git a/TreeADT/treeTraversal.py b/TreeADT/treeTraversal.py
@@ -54,6 +54,17 @@ def post_order_traversal(root):
         post_order_traversal(root.right_node)
         print root.data,
 
+def level_order_traversal(root):
+    Q = []
+    Q.append(root)
+    while len(Q) > 0:
+        root = Q.pop(0)
+        print root.data,
+        if root.left_node:
+            Q.append(root.left_node)
+        if root.right_node:
+            Q.append(root.right_node)
+
 
 if __name__ == "__main__":
     bTree = TreeNode(1)
@@ -73,4 +84,9 @@ def post_order_traversal(root):
     print ""
     print "*"*80
     print "PostOrder Tree traversal"
-    post_order_traversal(bTree)
+    post_order_traversal(bTree)
+
+    print ""
+    print "*"*80
+    print "LevelOrder Tree traversal"
+    level_order_traversal(bTree)
diff --git a/reverseParentTree.py b/reverseParentTree.py
