{"id":27070,"date":"2018-01-02T22:17:20","date_gmt":"2018-01-02T16:47:20","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27070"},"modified":"2018-10-31T16:50:30","modified_gmt":"2018-10-31T11:20:30","slug":"python-programming-tree-traversals-inorder-preorder-postorder","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-tree-traversals-inorder-preorder-postorder\/","title":{"rendered":"Programming Tree Traversals (Inorder, Preorder and Postorder)"},"content":{"rendered":"

Programming Tree Traversals (Inorder, Preorder and Postorder)<\/strong><\/span><\/p>\n

Unlike linear data structures<\/a> (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. Following are the generally used ways for traversing trees.<\/p>\n

Depth First Traversals:<\/span><\/h3>\n

(a) Inorder<\/strong> (Left, Root, Right) : 4 2 5 1 3
\n(b) Preorder<\/strong> (Root, Left, Right) : 1 2 4 5 3
\n(c) Postorder<\/strong> (Left, Right, Root) : 4 5 2 3 1<\/p>\n

Breadth First or Level Order Traversal : 1 2 3 4 5
\nPlease see this post for Breadth First Traversal.<\/a><\/p>\n

Inorder Traversal:<\/strong><\/span><\/h3>\n
Algorithm Inorder(tree)\r\n   1. Traverse the left subtree, i.e., call Inorder(left-subtree)\r\n   2. Visit the root.\r\n   3. Traverse the right subtree, i.e., call Inorder(right-subtree)\r\n<\/pre>\n
Uses of Inorder<\/strong><\/span><\/h3>\n
In case of binary search trees<\/a> (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder itraversal s reversed, can be used.
\nExample:<\/strong><\/span> Inorder traversal for the above given figure is 4 2 5 1 3.<\/p>\n[ad type=”banner”]
\n<\/strong><\/p>\n
Postorder Traversal:<\/strong><\/span><\/h3>\n
Algorithm Postorder(tree)\r\n   1. Traverse the left subtree, i.e., call Postorder(left-subtree)\r\n   2. Traverse the right subtree, i.e., call Postorder(right-subtree)\r\n   3. Visit the root.\r\n<\/pre>\n
Uses of Postorder<\/strong><\/span><\/h3>\n
Postorder traversal is used to delete the tree. . Postorder traversal<\/a> is also useful to get the postfix expression<\/a> of an expression tree. Please see http:\/\/en.wikipedia.org\/wiki\/Reverse_Polish_notation<\/a> to for the usage of postfix expression.<\/p>\n
Example:<\/strong> <\/span>Postorder traversal for the above given figure is 4 5 2 3 1.<\/p>\n[ad type=”banner”]\n
\n<\/strong><\/p>\n
 
 <\/div> 
# Python program to for tree traversals # A class that represents an individual node in a# Binary Treeclass Node:    def __init__(self,key):        self.left = None        self.right = None        self.val = key  # A function to do inorder tree traversaldef printInorder(root):     if root:         # First recur on left child        printInorder(root.left)         # then print the data of node        print(root.val),         # now recur on right child        printInorder(root.right)   # A function to do postorder tree traversaldef printPostorder(root):     if root:         # First recur on left child        printPostorder(root.left)         # the recur on right child        printPostorder(root.right)         # now print the data of node        print(root.val),  # A function to do postorder tree traversaldef printPreorder(root):     if root:         # First print the data of node        print(root.val),         # Then recur on left child        printPreorder(root.left)         # Finally recur on right child        printPreorder(root.right)  # Driver coderoot = Node(1)root.left      = Node(2)root.right     = Node(3)root.left.left  = Node(4)root.left.right  = Node(5)print "Preorder traversal of binary tree is"printPreorder(root) print "\\nInorder traversal of binary tree is"printInorder(root) print "\\nPostorder traversal of binary tree is"printPostorder(root)<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
Output:<\/span><\/h3>\n
Preorder traversal of binary tree is\r\n1 2 4 5 3 \r\nInorder traversal of binary tree is\r\n4 2 5 1 3 \r\nPostorder traversal of binary tree is\r\n4 5 2 3 1<\/pre>\n","protected":false},"excerpt":{"rendered":"
Python –  Programming Tree Traversals (Inorder, Preorder and Postorder) – Tree – Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) <\/p>\n","protected":false},"author":1,"featured_media":31291,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80140],"tags":[80710,80711,80801,80799,80797,80714,80798,80800],"class_list":["post-27070","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-binay-tree","tag-binary-tree-traversal-program-in-c","tag-inorder-preorder-postorder-traversal-examples-pdf","tag-inorder-preorder-postorder-traversal-examples-ppt","tag-inorder-traversal-algorithm","tag-inorder-traversal-example","tag-inorder-traversal-without-recursion","tag-tree-traversal-in-data-structure","tag-tree-traversal-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27070","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=27070"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27070\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31291"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27070"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27070"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27070"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}