Post order traversal of binary tree without recurs

Question

What is the algorithm for doing a post order traversal of a binary tree WITHOUT using recursion?

Answer 1

Depth first, post order, non recursive, without stack

When you have parent:

   node_t
   {
     left,
     right
     parent
   }

   traverse(node_t rootNode)
   {
     bool backthreading = false 
     node_t node = rootNode

     while(node <> 0)

        if (node->left <> 0) and backthreading = false then
               node = node->left

            continue 
        endif

         >>> process node here <<<


        if node->right <> 0 then
            lNode = node->right
            backthreading = false
        else
            node = node->parent

            backthreading = true
        endif
    endwhile

Answer 2

Here is a Python version too ::

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

def postOrderIterative(root):

    if root is None :
        return

    s1 = []
    s2 = []
    s1.append(root)

    while(len(s1)>0):
        node = s1.pop()
        s2.append(node)

        if(node.left!=None):
            s1.append(node.left)

        if(node.right!=None):
            s1.append(node.right)

    while(len(s2)>0):
        node = s2.pop()
        print(node.data)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
postOrderIterative(root)

Here is the output ::

Answer 3

Two methods to perform Post Order Traversal without Recursion:

1. Using One HashSet of Visited Nodes and One stack for backtracking:

private void postOrderWithoutRecursion(TreeNode root) {
    if (root == null || root.left == null && root.right == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    Set<TreeNode> visited = new HashSet<>();
    while (!stack.empty() || root != null) {
        if (root != null) {
            stack.push(root);
            visited.add(root);
            root = root.left;
        } else {
            root = stack.peek();
            if (root.right == null || visited.contains(root.right)) {
                System.out.print(root.val+" ");
                stack.pop();
                root = null;
            } else {
                root = root.right;
            }

        }
    }
}

Time Complexity: O(n)
Space Complexity: O(2n)

2. Using Tree Altering method:

private void postOrderWithoutRecursionAlteringTree(TreeNode root) {
    if (root == null || root.left == null && root.right == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.empty() || root != null) {
        if (root != null) {
            stack.push(root);
            root = root.left;
        } else {
            root = stack.peek();
            if (root.right == null) {
                System.out.print(root.val+" ");
                stack.pop();
                root = null;
            } else {
                TreeNode temp = root.right;
                root.right = null;
                root = temp;
            }
        }
    }
}

Time Complexity: O(n)
Space Complexity: O(n)

TreeNode Class:

public class TreeNode {
    public int val;

    public TreeNode left;

    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }
}