1

The code will give a result of 4 2 1 3 6 5 7. How do I code it to transform into a postorder traversal?

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
    
def func1(nums):
    if not nums:
        return None
    mid_val = len(nums)//2
    node = TreeNode(nums[mid_val])
    node.left = func1(nums[:mid_val])
    node.right = func1(nums[mid_val+1:])
    return node

def func2(node): 
    if not node: 
        return      
    print(node.val)
    func2(node.left) 
    func2(node.right)   

result = func1([1, 2, 3, 4, 5, 6, 7])
func2(result)
turtleee
  • 15
  • 3
  • Does this answer your question? [Post-order Graph Traversal?](https://stackoverflow.com/questions/36488968/post-order-graph-traversal) – johncitizen Jun 20 '22 at 09:03

2 Answers2

0

In the post-order tree-traversal, first the left child node, then the right child node, and finally the parent node are printed. Accordingly, if you line up the same scenario for your func2 function, you should edit your code like this.

def func2(node):
    if not node:
        return
    func2(node.left)
    func2(node.right)
    print(node.val)
Umut Emre Önder
  • 98
  • 11
  • oh right i thought of implementing another function to transform it to postorder, perfect, thanks! well I could write that as a new function too – turtleee Jun 20 '22 at 09:16
0

What about this? Is valid for non-binary trees too.

class Node:
    def __init__(self,jobName):
        self.job = jobName
        self.children = []

def postorder(node):
    if len(node.children) != 0:
        for child in node.children:
            postorder(child)
    print(node.job)
        

if __name__ == "__main__":
    tree = Node("0")
    tree.children.append(Node("00"))
    tree.children.append(Node("01"))
    tree.children.append(Node("02"))
    tree.children[0].children.append(Node("000"))
    tree.children[0].children.append(Node("001"))
    tree.children[0].children[1].children.append(Node("0010"))
    tree.children[0].children.append(Node("002"))
    tree.children[0].children[2].children.append(Node("0020"))

    postorder(tree)

000 0010 001 0020 002 00 01 02 0

Gines Rodriguez
  • 1
  • 2
  • Why check `len(node.children) != 0`? – greybeard Oct 08 '22 at 16:42
  • (You could try to make this generic: 1) [document](https://www.python.org/dev/peps/pep-0257/#what-is-a-docstring) 2) drop "business attribute" job from `Node` 3) pass a function to `postorder()` to call for every node (optionally 4) add ["aliases"](https://docs.python.org/3/howto/descriptor.html) `left` & `right`).) – greybeard Oct 08 '22 at 16:56
  • len(node.children) != 0 is for stopping when there is no child for current node. Sorry for the delay:) – Gines Rodriguez Apr 11 '23 at 07:25
  • `len(node.children) != 0 is for …` there wouldn't be a single trip though the loop without this pre-check if `children` was empty. – greybeard Apr 11 '23 at 07:36