➜ ~

Playing Hacks and Stuffs!

---

Project maintained by h4ckyou Hosted on GitHub Pages — Theme by mattgraham

Binary Tree Postorder Traversal

We are going to be given a binary tree and our goal is to return the postorder traversal of its node’s values

I already solved the other ways of traversing binary trees one and two you can check it out!

So for this method the rule is:

• Traverse the left subtree recurisvely postorder
• Traverse the right subtree recurisvely postorder
• Traverse the current node

Let’s take this binary tree as an example:

The parent node which I’ll refer as the key is 3 and it has two children nodes connected to it 2 and 4

For us to Traverse using Postorder method I’ll do this

First I’ll traverse the left subtree so that means I’ll need to visit all the left nodes from the left node connected to the key and add to my list

In this case there just two left nodes in the left subtree

So the list result would be [1, 2]

Now we move to the right subtree which is starting from 4

The node of value 4 has two children which are 6 and 5

Since 6 is a left node we’ll first visit it before moving to the right node that’s because the rule says we should traverse the left before right then current node

At this point we’ve applied the first and second rule so our list should hold [1, 2, 6, 5]

To accomplish the last rule we’ll visit the remaining current nodes

Therefore the final result will be [1, 2, 6, 5, 4, 3]

Here’s my solve script: link

Leetcode Submission Script

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        
        return (Solution.postorderTraversal(self, root.left) + Solution.postorderTraversal(self, root.right) + [root.val])