CODEWITHSUNDEEP
pythontreenodespostorder
Tony H
Tony H

Reputation: 53

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?

Upvotes: 0

Views: 935

Answers (2)

Michael Rovinsky
Michael Rovinsky

Reputation: 7210

You can do it recursively:

def updateNodeSize(node):
    if 'children' not in node:
        if 'size' in node:
            return node['size']
        return 0

    maxSize = 0
    for child in node['children']:
        maxSize = max(maxSize, updateNodeSize(child))
    node['size'] = maxSize
    return maxSize


updateNodeSize(root)

Upvotes: 1

Chrispresso
Chrispresso

Reputation: 4071

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

Upvotes: 1

Related Questions