class Node(object): def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right @classmethod def build(cls, value, levels): ''' Builds a tree where a BFS would count from O to 2^levels - 2, assuming value starts at 0 ''' if levels < 0:return None return cls(value, left=cls.build(1 + (value<<1), levels - 1), right=cls.build(2 + (value<<1), levels - 1)) @staticmethod def print_node(node): print node.value, def first_visit(node, stack, handler): ''' Handles visiting a node for the first time. Pushes a command to visit the node again onto the stack, then pushes a command to visit the left node onto the stack. ''' if not node:return stack.insert(0, lambda:second_visit(node, stack, handler)) stack.insert(0, lambda:first_visit(node.left, stack, handler)) def second_visit(node, stack, handler): ''' Handles visiting a node for the second time, e.g. after its left branch has been entirely visited. Sends the node through the handler and then adds the right node to the visitation stack. ''' handler(node) stack.insert(0, lambda:first_visit(node.right, stack, handler)) def traverse(node, handler): ''' Performs a non-recursive in-order traversal, in O(log N) space. ''' stack = [] first_visit(node, stack, handler) while stack: stack.pop(0)() # build(0, 2) creates the following tree: # 0 # 1 2 # 3 4 5 6 # # traverse prints out: # 3 1 4 0 5 2 6 traverse(Node.build(0, 2), Node.print_node) print