CODEWITHSUNDEEP
pythonrecursiontreeiteration
chase37
chase37

Reputation: 1

Convert recursive tree walking function to iterative

How can the following recursive function walk() be converted to an iterative function?

Walking the nodes in the same order iteratively is easy using a stack, but I'm unable to figure out how to write an iterative function that will print both the opening and closing tags of each node like the recursive version does.

Code:

class Node(object):
    def __init__(self, name, children=[]):
        self.name = name
        self.children = children

def walk(node):
    print('<', node.name, '>', sep='')
    for n in node.children:
        walk(n)
    print('</', node.name, '>', sep='')

root = \
Node('html', [
    Node('head'),
    Node('body', [
        Node('div'),
        Node('p', [
            Node('a'),
        ])
    ]),
])

walk(root)

Output:

<html>
<head>
</head>
<body>
<div>
</div>
<p>
<a>
</a>
</p>
</body>
</html>

Code that traverses the tree iteratively:

The function visits the nodes in the correct order, but obviously does not print the closing tags.

def walk(node):
    stack = []
    stack.append(node)
    while len(stack) > 0:
        node = stack.pop()
        for child in reversed(node.children):
            stack.append(child)
        print(node.name)

Upvotes: 0

Views: 509

Answers (2)

RandyTek
RandyTek

Reputation: 4754

It is kind of post-order tree treversal as you have to visit the parent node after visiting children.

I modified a few lines of your existing code:

class Node(object):
def __init__(self, name, children=[]):
    self.name = name
    self.children = children

# def walk(node):
#     print('<', node.name, '>', sep='')
#     for n in node.children:
#         walk(n)
#     print('</', node.name, '>', sep='')

def walk(node):
    stack = []
    stack.append((node, 'start'))
    while len(stack) > 0:
        node, status = stack.pop()
        if status == 'start':
            stack.append((node, 'end'))
            for child in reversed(node.children):
                stack.append((child, 'start'))
            print('<', node.name, '>', sep='')
        else: # status == 'end'
            print('</', node.name, '>', sep='')

root = \
Node('html', [
    Node('head'),
    Node('body', [
        Node('div'),
        Node('p', [
            Node('a'),
        ])
    ]),
])

walk(root)

Upvotes: 0

mata
mata

Reputation: 69082

The problem is that for this to work you also need to record on the stack where the node ends. A possible solution would be:

def walk(root):
    stack = []
    stack.append(root)
    indent = 0
    while stack:
        node = stack.pop()
        if isinstance(node, Node):
            print('    ' * indent, "<", node.name, ">", sep="")
            indent += 1
            stack.append(node.name)
            stack.extend(reversed(node.children))
        else:
            indent -= 1
            print('    ' * indent, "</", node, ">", sep="")

I've added indenting so the output is nicer:

<html>
    <head>
    </head>
    <body>
        <div>
        </div>
        <p>
            <a>
            </a>
        </p>
    </body>
</html>

Upvotes: 0

Related Questions