pythontreenodespostorder

post order general tree traversal in Python


Is it possible to traverse a general tree (that is, a tree with multiple children) in a post order way using Python. Essentially, I want to traverse a tree like the one below from the lowest left going up in the tree and compare each node .size with its parents .size in terms of which one is largest, if the child is larger, I change the node .max_size to the child's .size. The root will always have the value of the largest in the tree stored in it.

enter image description here

My Question: is there a way to traverse a general tree in post order (for this example: E, F, B, C, D, A)? If so, what would be the way to do so?


Solution

  • Not sure why you need the size stuff. You can do this:

    In [254]: class Node:
         ...:     def __init__(self, val: str):
         ...:         self.val = val
         ...:         self.children = []
         ...:
    
    In [255]: A = Node('A')
    In [256]: B = Node('B')
    In [257]: C = Node('C')
    In [258]: D = Node('D')
    In [259]: E = Node('E')
    In [260]: F = Node('F')
    In [261]: A.children = [B,C,D]
    In [262]: B.children = [E,F]
    In [263]: root = A
    # General post order but iterating over the children instead of doing left/right
    In [264]: def post_order(root: Node):
         ...:     if root is not None:
         ...:         for child in root.children:
         ...:             post_order(child)
         ...:         print(root.val)
         ...:
    
    In [265]: post_order(A)
    E
    F
    B
    C
    D
    A