can we code inorder,preorder and postorder in single code in python ? without using recursion

i want to code all binary tree orders in single code (preorder,postorder,inorder) in O(N) time complexity and O(N) space , using single stack and without recursion.

anybody can help me ?

Answer

You can use a stack and accompany every pushed node with an order-identification (“pre”, “in” or “post”). The code can then check if this matches the required traversal order to decide whether to yield the node’s value or not.

Code:

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

    def traversal(self, order="pre"):
        stack = [(self, "pre")]
        while stack:
            node, nodeorder = stack.pop()
            if nodeorder == order:
                yield node.value
            if nodeorder == "pre":
                stack.append((node, "in"))
                if node.left:
                    stack.append((node.left, "pre"))
            elif nodeorder == "in":
                stack.append((node, "post"))
                if node.right:
                    stack.append((node.right, "pre"))

So traversal should get as second argument either “pre”, “in” or “post”, depending on the order you want.

Example tree:

         4
        / 
       2   5
      /    
     1   3   7
            /
           6

…and corresponding code:

root = Node(4,
    Node(2,
        Node(1),
        Node(3)
    ),
    Node(5,
        None,
        Node(7,
            Node(6)
        )
    )
)

print(*root.traversal("pre"))   # 4 2 1 3 5 7 6
print(*root.traversal("in"))    # 1 2 3 4 5 6 7
print(*root.traversal("post"))  # 1 3 2 6 7 5 4