{"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":"<p><span style=\"color: #003300;\"><strong>Programming Tree Traversals (Inorder, Preorder and Postorder)<\/strong><\/span><\/p>\n<p>Unlike <a href=\"https:\/\/www.wikitechy.com\/interview-questions\/data-structure\/what-is-data-structure\" target=\"_blank\" rel=\"noopener\">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<h3 id=\"depth-first-traversals\"><span style=\"color: #333300;\">Depth First Traversals:<\/span><\/h3>\n<p>(a)<strong> Inorder<\/strong> (Left, Root, Right) : 4 2 5 1 3<br \/>\n(b) <strong>Preorder<\/strong> (Root, Left, Right) : 1 2 4 5 3<br \/>\n(c) <strong>Postorder<\/strong> (Left, Right, Root) : 4 5 2 3 1<\/p>\n<p>Breadth First or Level Order Traversal : 1 2 3 4 5<br \/>\nPlease see this post for <a href=\"https:\/\/www.wikitechy.com\/technology\/25857-2\/\" target=\"_blank\" rel=\"noopener\">Breadth First Traversal.<\/a><\/p>\n<h3 id=\"inorder-traversal\"><span style=\"color: #003366;\"><strong>Inorder Traversal:<\/strong><\/span><\/h3>\n<pre>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<h3 id=\"uses-of-inorder\"><span style=\"color: #008080;\"><strong>Uses of Inorder<\/strong><\/span><\/h3>\n<p>In case of <a href=\"https:\/\/www.wikitechy.com\/technology\/python-program-inorder-successor-binary-search-tree\/\" target=\"_blank\" rel=\"noopener\">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.<br \/>\n<span style=\"color: #993300;\"><strong>Example:<\/strong><\/span> Inorder traversal for the above given figure is 4 2 5 1 3.<\/p>\n[ad type=\u201dbanner\u201d]<strong><br \/>\n<\/strong><\/p>\n<h3 id=\"postorder-traversal\"><span style=\"color: #003366;\"><strong>Postorder Traversal:<\/strong><\/span><\/h3>\n<pre>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<h3 id=\"uses-of-postorder\"><span style=\"color: #008080;\"><strong>Uses of Postorder<\/strong><\/span><\/h3>\n<p>Postorder traversal is used to delete the tree. . <a href=\"https:\/\/www.wikitechy.com\/technology\/python-algorithm-iterative-postorder-traversal-set-1-using-two-stacks\/\" target=\"_blank\" rel=\"noopener\">Postorder traversal<\/a> is also useful to get the <a href=\"https:\/\/www.wikitechy.com\/technology\/python-algorithm-reverse-string-using-stack\/\" target=\"_blank\" rel=\"noopener\">postfix expression<\/a> of an expression tree. Please see<a href=\"http:\/\/en.wikipedia.org\/wiki\/Reverse_Polish_notation\"> http:\/\/en.wikipedia.org\/wiki\/Reverse_Polish_notation<\/a> to for the usage of postfix expression.<\/p>\n<p><span style=\"color: #993300;\"><strong>Example:<\/strong> <\/span>Postorder traversal for the above given figure is 4 5 2 3 1.<\/p>\n[ad type=\u201dbanner\u201d]\n<strong><br \/>\n<\/strong><\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20for%20tree%20traversals%0A%20%0A%23%20A%20class%20that%20represents%20an%20individual%20node%20in%20a%0A%23%20Binary%20Tree%0Aclass%20Node%3A%0A%20%20%20%20def%20__init__(self%2Ckey)%3A%0A%20%20%20%20%20%20%20%20self.left%20%3D%20None%0A%20%20%20%20%20%20%20%20self.right%20%3D%20None%0A%20%20%20%20%20%20%20%20self.val%20%3D%20key%0A%20%0A%20%0A%23%20A%20function%20to%20do%20inorder%20tree%20traversal%0Adef%20printInorder(root)%3A%0A%20%0A%20%20%20%20if%20root%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%20First%20recur%20on%20left%20child%0A%20%20%20%20%20%20%20%20printInorder(root.left)%0A%20%0A%20%20%20%20%20%20%20%20%23%20then%20print%20the%20data%20of%20node%0A%20%20%20%20%20%20%20%20print(root.val)%2C%0A%20%0A%20%20%20%20%20%20%20%20%23%20now%20recur%20on%20right%20child%0A%20%20%20%20%20%20%20%20printInorder(root.right)%0A%20%0A%20%0A%20%0A%23%20A%20function%20to%20do%20postorder%20tree%20traversal%0Adef%20printPostorder(root)%3A%0A%20%0A%20%20%20%20if%20root%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%20First%20recur%20on%20left%20child%0A%20%20%20%20%20%20%20%20printPostorder(root.left)%0A%20%0A%20%20%20%20%20%20%20%20%23%20the%20recur%20on%20right%20child%0A%20%20%20%20%20%20%20%20printPostorder(root.right)%0A%20%0A%20%20%20%20%20%20%20%20%23%20now%20print%20the%20data%20of%20node%0A%20%20%20%20%20%20%20%20print(root.val)%2C%0A%20%0A%20%0A%23%20A%20function%20to%20do%20postorder%20tree%20traversal%0Adef%20printPreorder(root)%3A%0A%20%0A%20%20%20%20if%20root%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%20First%20print%20the%20data%20of%20node%0A%20%20%20%20%20%20%20%20print(root.val)%2C%0A%20%0A%20%20%20%20%20%20%20%20%23%20Then%20recur%20on%20left%20child%0A%20%20%20%20%20%20%20%20printPreorder(root.left)%0A%20%0A%20%20%20%20%20%20%20%20%23%20Finally%20recur%20on%20right%20child%0A%20%20%20%20%20%20%20%20printPreorder(root.right)%0A%20%0A%20%0A%23%20Driver%20code%0Aroot%20%3D%20Node(1)%0Aroot.left%20%20%20%20%20%20%3D%20Node(2)%0Aroot.right%20%20%20%20%20%3D%20Node(3)%0Aroot.left.left%20%20%3D%20Node(4)%0Aroot.left.right%20%20%3D%20Node(5)%0Aprint%20%22Preorder%20traversal%20of%20binary%20tree%20is%22%0AprintPreorder(root)%0A%20%0Aprint%20%22%5CnInorder%20traversal%20of%20binary%20tree%20is%22%0AprintInorder(root)%0A%20%0Aprint%20%22%5CnPostorder%20traversal%20of%20binary%20tree%20is%22%0AprintPostorder(root)\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<h3 id=\"output\"><span style=\"color: #339966;\">Output:<\/span><\/h3>\n<pre>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":"<p>Python &#8211;  Programming Tree Traversals (Inorder, Preorder and Postorder) &#8211; Tree &#8211; 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}]}}