post order general tree traversal in Python

Question

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.

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?

The children would be an array instead of a general "left" and "right", but yes, you can. — Chrispresso
– Chrispresso, Commented Apr 9, 2021 at 4:38

Chrispresso · Accepted Answer · 2021-04-09 04:45:46Z

1

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

answered Apr 9, 2021 at 4:45

Chrispresso

4,3382 gold badges22 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Michael Rovinsky · Accepted Answer · 2021-04-09 04:48:32Z

1

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)

answered Apr 9, 2021 at 4:48

Michael Rovinsky

7,2957 gold badges17 silver badges33 bronze badges

Collectives™ on Stack Overflow

post order general tree traversal in Python

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related