{"id":27145,"date":"2018-01-03T21:52:56","date_gmt":"2018-01-03T16:22:56","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27145"},"modified":"2018-01-03T21:52:56","modified_gmt":"2018-01-03T16:22:56","slug":"python-program-level-order-tree-traversal","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-program-level-order-tree-traversal\/","title":{"rendered":"Python program – Level Order Tree Traversal"},"content":{"rendered":"

Level order traversal of a tree is breadth first traversal for the tree.<\/p>\n

Level order traversal of the above tree is 1 2 3 4 5<\/p>\n

\n

Recommended: Please solve it on “PRACTICE<\/u><\/i><\/b>” first,<\/h2>\n

before moving on to the solution.<\/h2>\n<\/div>\n

METHOD 1 (Use function to print a given level)<\/strong><\/p>\n

Algorithm:<\/strong>
\nThere are basically two functions in this method. One is to print all nodes at a given level (printGivenLevel), and other is to print level order traversal of the tree (printLevelorder). printLevelorder makes use of printGivenLevel to print nodes at all levels one by one starting from root.<\/p>\n

\/*Function to print level order traversal of tree*\/\r\nprintLevelorder(tree)<\/strong>\r\nfor d = 1 to height(tree)\r\n   printGivenLevel(tree, d);\r\n\r\n\/*Function to print all nodes at a given level*\/\r\nprintGivenLevel(tree, level)<\/strong>\r\nif tree is NULL then return;\r\nif level is 1, then\r\n    print(tree->data);\r\nelse if level greater than 1, then\r\n    printGivenLevel(tree->left, level-1);\r\n    printGivenLevel(tree->right, level-1);<\/pre>\n[ad type=”banner”]\n
 
 <\/div> 
# Recursive Python program for level order traversal of Binary Tree # A node structureclass Node:     # A utility function to create a new node    def __init__(self, key):        self.data = key         self.left = None        self.right = None  # Function to  print level order traversal of treedef printLevelOrder(root):    h = height(root)    for i in range(1, h+1):        printGivenLevel(root, i)  # Print nodes at a given leveldef printGivenLevel(root , level):    if root is None:        return    if level == 1:        print "%d" %(root.data),    elif level > 1 :        printGivenLevel(root.left , level-1)        printGivenLevel(root.right , level-1)  """ Compute the height of a tree--the number of nodes    along the longest path from the root node down to    the farthest leaf node"""def height(node):    if node is None:        return 0    else :        # Compute the height of each subtree         lheight = height(node.left)        rheight = height(node.right)         #Use the larger one        if lheight > rheight :            return lheight+1        else:            return rheight+1 # Driver program to test above functionroot = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(5) print "Level order traversal of binary tree is -"printLevelOrder(root) #This code is contributed by Nikhil Kumar Singh(nickzuck_007)<\/code><\/pre> <\/div>\n
Output:<\/p>\n
Level order traversal of binary tree is - \r\n1 2 3 4 5<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Python Program – Level Order Tree Traversal – Level order traversal of a tree is breadth first traversal for the tree. There are basically two functions <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80140,1,4148],"tags":[80969,80907,80905,80909,80903,80906,80962,80910],"class_list":["post-27145","post","type-post","status-publish","format-standard","hentry","category-binay-tree","category-coding","category-python","tag-breadth-first-traversal-of-a-tree-in-c","tag-level-order-traversal-in-spiral-form","tag-level-order-traversal-java","tag-level-order-traversal-leetcode","tag-level-order-traversal-of-a-binary-tree-in-c-code","tag-level-order-traversal-of-binary-tree-using-queue-in-c","tag-level-order-traversal-using-queue","tag-print-tree-level-by-level-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27145","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27145"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27145\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27145"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27145"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27145"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}