How to traverse a tree in Python

I was preparing for an interview. So here's my summary of tree traverse in Python.



1. Using recursion

#! /usr/bin/python

class Node:
        def __init__(self,value,left=None,right=None):
                self.value=value;self.left=left;self.right=right

def traverse(node):
        if node==None: return
        print node.value
        traverse(node.left)
        traverse(node.right)

def main():
        n1=Node(1)
        n2=Node(2)
        n3=Node(3,n1,n2)
        n4=Node(4)
        n5=Node(5,n3,n4)
        traverse(n5)

if __name__ == "__main__":
        main()
"""
Result:

5
3
1
2
4
"""

You may ask: Can I traverse a tree w/o recursion? Surely you can! The easiest way to do so is using a stack. Python has a build-in type--list. It has append() and pop() that can be used as stack push and stack pop.

2. No recursion:

#! /usr/bin/python

def treeWalker(node):
        lifo=[]
        while True:
                print node.value
                if node.left!=None:
                        lifo.append(node)
                        node=node.left
                else:
                        try:
                                node=lifo.pop()
                        except:
                                return None
                        node=node.right

class Node:
        def __init__(self, value, left=None, right=None):
                self.value=value;self.left=left;self.right=right

if __name__ == "__main__":
        n1=Node(1)
        n2=Node(2)
        n3=Node(3,n1,n2)
        n4=Node(4)
        n5=Node(5,n3,n4)
        treeWalker(n5)

"""
Result:
5
3
1
2
4
"""