{"id":12468,"date":"2021-02-12T17:47:55","date_gmt":"2021-02-12T17:47:55","guid":{"rendered":"https:\/\/www.askpython.com\/?p=12468"},"modified":"2021-02-22T16:43:41","modified_gmt":"2021-02-22T16:43:41","slug":"postorder-tree-traversal-in-python","status":"publish","type":"post","link":"https:\/\/www.askpython.com\/python\/examples\/postorder-tree-traversal-in-python","title":{"rendered":"Postorder Tree Traversal in Python"},"content":{"rendered":"\n

In this article, we will study the concept and algorithm for postorder tree traversal. Then we will implement the algorithm for postorder traversal in python and run it on a binary tree<\/a>.<\/p>\n\n\n\n

What is Postorder Tree Traversal?<\/h2>\n\n\n\n

Postorder traversal is a depth-first tree traversal algorithm<\/a>. In depth-first traversal, we start at the root node and then we explore a branch of the tree till the end and then we backtrack and traverse another branch.<\/p>\n\n\n\n

In the postorder traversal, first, we traverse the left child or left subtree of the current node and then we traverse the right child or right subtree of the current node. At last, we traverse the current node. <\/p>\n\n\n\n

We perform this operation recursively till all the nodes are traversed. We use postorder traversal to delete a binary tree. We can also use postorder tree traversal to find postfix expression from an expression tree.<\/strong><\/p>\n\n\n\n

Postorder Traversal Algorithm<\/h2>\n\n\n\n

Following is the algorithm for postorder traversal.<\/p>\n\n\n\n

  • Algorithm postorder:<\/strong><\/li>
  • Input: Reference to Root Node<\/li>
  • Output: Prints All the nodes of the tree<\/li>
  • Start.<\/li>
  • If the root is empty, return.<\/li>
  • Traverse left subtree of the root.\/\/ postorder(root.leftChild)<\/li>
  • Traverse the right subtree of the root.\/\/ postorder(root.rightChild)<\/li>
  • Traverse the root node. \/\/print value at node
    End.<\/li><\/ul>\n\n\n\n

    Postorder Traversal Algorithm implementation in python<\/h2>\n\n\n\n

    Now we will implement the above algorithm to print nodes of the following binary tree in postorder traversal.<\/p>\n\n\n\n

    \"Askpython31
    Binary Tree<\/figcaption><\/figure>\n\n\n\n

    In the following code, first the above binary tree has been created and then postorder traversal of the binary tree is printed.<\/p>\n\n\n

    \nclass BinaryTreeNode:\n  def __init__(self, data):\n    self.data = data\n    self.leftChild = None\n    self.rightChild=None\n    \ndef insert(root,newValue):\n    #if binary search tree is empty, make a new node and declare it as root\n    if root is None:\n        root=BinaryTreeNode(newValue)\n        return root\n    #binary search tree is not empty, so we will insert it into the tree\n    #if newValue is less than value of data in root, add it to left subtree and proceed recursively\n    if newValue<root.data:\n        root.leftChild=insert(root.leftChild,newValue)\n    else:\n        #if newValue is greater than value of data in root, add it to right subtree and proceed recursively\n        root.rightChild=insert(root.rightChild,newValue)\n    return root\ndef postorder(root):\n    #if root is None return\n        if root==None:\n            return\n        #traverse left subtree\n        postorder(root.leftChild)\n        #traverse right subtree\n        postorder(root.rightChild)  \n        #traverse root\n        print(root.data)                 \nroot= insert(None,15)\ninsert(root,10)\ninsert(root,25)\ninsert(root,6)\ninsert(root,14)\ninsert(root,20)\ninsert(root,60)\nprint("Printing values of binary tree in postorder Traversal.")\npostorder(root)\n<\/pre><\/div>\n\n\n
    Output:<\/p>\n\n\n
    \nPrinting values of binary tree in postorder Traversal.\n6\n14\n10\n20\n60\n25\n15\n<\/pre><\/div>\n\n\n
    Here, we can see that every child of a node is traversed before the current node is processed. So we can use postorder traversal to delete a binary tree as we can start deleting nodes from a leaf and go upto the root.<\/strong><\/p>\n\n\n\n
    Conclusion<\/h2>\n\n\n\n
    In this article, We have learned the concept of postorder tree traversal. We also studied the algorithm and implemented it in Python to traverse a binary tree. Stay tuned for more informative articles.<\/p>\n","protected":false},"excerpt":{"rendered":"
    In this article, we will study the concept and algorithm for postorder tree traversal. Then we will implement the algorithm for postorder traversal in python and run it on a binary tree. What is Postorder Tree Traversal? Postorder traversal is a depth-first tree traversal algorithm. In depth-first traversal, we start at the root node and […]<\/p>\n","protected":false},"author":20,"featured_media":12643,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-12468","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-examples"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/12468","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/comments?post=12468"}],"version-history":[{"count":0,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/12468\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media\/12643"}],"wp:attachment":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media?parent=12468"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/categories?post=12468"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/tags?post=12468"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}