PostOrder Traversal Without Recursion Problem

Given a binary tree, find its post-order traversal without using recursion.

Example:

Input:

Output: [400, 500, 200, 300, 100]

Notes:

The nodes are labelled from 0 to number of nodes – 1.

Constraints:

1 <= number of nodes <= 105.

-109 <= node value <= 109.

Solutions

We provided two solutions where both of them are equally optimal.

The problem statement prohibits the use of recursion. Recursion uses a stack of function calls to find out the post-order traversal. We just have to iteratively model the functionality of those recursive stacks. Which data structure do you think can come to our rescue?

1) modify_the_tree_solution.cpp

As you might have guessed, we will use the stack data structure to replicate the functionality of those recursive stacks.

We have to make sure that the nodes are pushed into the stack in the same order as they are pushed in the recursive stack.

But, the problem with this approach is that the recursive stack can keep a track of the fact that whether the left and the right subtrees of the current node have been processed or not as it can keep a track of the line of code where it left the current recursive call.

This thing is not very straightforward for a normal stack. So, how to do it?

Basically, when you pop out a node from the stack, there are three possibilities:

• We have not processed the left subtree of the current node: In this case, we need to do a post-order traversal of the left subtree.
• We have processed the left subtree but not the right subtree: In this case, we need to do a post-order traversal of the right subtree.
• We have processed both the subtrees: In this case, we will append the value of the current node into our resultant array. After this, the current node is of no use. Hence, we will remove it from the stack.

So, how will we know which of the above cases does the current node lie in?

One way is to maintain two separate unordered maps mapping a node to a Boolean to denote whether the left and the right subtrees of the node have been processed or not.

But, we can avoid this extra space by making some modifications in the tree itself.

Note that, when the left child of a node is pushed into the stack, it becomes a separate subtree to work on. That is, after this step, we no longer need the information that which node was the left child of the current node.

So, the idea is to break the connection between the node and its left child before we process it. That is, when we push the left child of the node into the stack, we will break the connection between the node and the left child. This will act as a flag that the left child of that node has been already processed.

Similarly, we will do the same while processing the right child of the current node.

So, if the left child of the node is NULL, it means that its left subtree has already been processed. Similarly, if the right child of a node is NULL, it means that the right subtree has already been processed. We can then use this information to find out which of the above cases does the current node lie in.

Time Complexity:

O(number of nodes).

Each node will be processed at most thrice. First while pushing its left child into the stack, second while pushing its right child and third while pushing its own value into the resultant array.

Auxiliary Space Used:

O(number of nodes).

In the worst case, we will have all the nodes pushed into the stack.

Space Complexity:

Space used for input: O(number of nodes).

Auxiliary space used: O(number of nodes).

Space used for output: O(number of nodes).

So, total space complexity: O(number of nodes).

// -------- START --------

/*
    class TreeNode{
        int val;
        TreeNode* left_ptr;
        TreeNode* right_ptr;
    };
*/
vector < int > postorder_traversal(TreeNode * root) {
    vector < int > postorder;

    if (root == NULL) {
        return postorder;
    }

    stack < TreeNode * > helper_stack;
    helper_stack.push(root);

    while (!helper_stack.empty()) {
        TreeNode * current_node = helper_stack.top();
        if (current_node -> left_ptr) {
            helper_stack.push(current_node -> left_ptr);
            current_node -> left_ptr = NULL;
        } else if (current_node -> right_ptr) {
            helper_stack.push(current_node -> right_ptr);
            current_node -> right_ptr = NULL;
        } else {
            postorder.push_back(current_node -> val);
            helper_stack.pop();
        }
    }

    return postorder;
}

// -------- END --------

2) without_tree_modification_solution.cpp

In the previous solution, we had to keep a track of the above-stated three cases for all the nodes and this was the reason we had to modify the actual tree. This was needed because we had to make sure that the node was processed only after its child nodes had been processed. Can you think of a tree traversal where we do not need to keep a track of this information?

In the pre-order traversal, the node is processed before both of its child nodes. The general ordering is:

Current node -> Process the left subtree -> Process the right subtree.

In the pre-order traversal, a node has to be processed when it is encountered and the processing for its left and right child is done only after this. Therefore, we do not need to keep a track of whether the left or right child of the node has been processed or not.

So, if we somehow are able to convert the pre-order traversal of the tree into post-order, we are done!

Consider the following modified pre-order traversal:

Current node -> Process the right subtree -> Process the left subtree.

If we reverse such a traversal, we get:

Process the left subtree -> Process the right subtree -> Current node.

This is the post-order traversal and that is what we want!

Therefore, if we find such a modified pre-order traversal of the tree, reversing it will give us the post-order traversal of that tree.

Similar to the first solution, we will use the stack data structure to replicate the functionality of the recursive stack. When a node is popped out of the stack, its value is pushed into the resultant array and then we push the child nodes of the current node into the stack. Finally, we will reverse the generated ordering and return it.

Time Complexity:

O(number of nodes).

Each node will be processed exactly once.

Auxiliary Space Used:

O(number of nodes).

In the worst case, we will have all the nodes pushed into the stack.

Space Complexity:

Space used for input: O(number of nodes).

Auxiliary space used: O(number of nodes).

Space used for output: O(number of nodes).

So, total space complexity: O(number of nodes).

// -------- START --------

/*
    class TreeNode{
        int val;
        TreeNode* left_ptr;
        TreeNode* right_ptr;
    };
*/
vector < int > postorder_traversal(TreeNode * root) {
    vector < int > postorder;

    if (root == NULL) {
        return postorder;
    }

    stack < TreeNode * > helper_stack;
    helper_stack.push(root);

    while (!helper_stack.empty()) {
        TreeNode * current_node = helper_stack.top();
        helper_stack.pop();
        postorder.push_back(current_node -> val);

        // Despite doing a Pre-order traversal of the type:
        // Current Node -> Process the Right child -> Process the Left child,
        // we are pushing the left child of the node first into the stack and then the
        // right child. This is because, the node that is pushed later is popped out
        // first from the stack.
        if (current_node -> left_ptr) {
            helper_stack.push(current_node -> left_ptr);
        }
        if (current_node -> right_ptr) {
            helper_stack.push(current_node -> right_ptr);
        }
    }

    reverse(postorder.begin(), postorder.end());
    return postorder;
}

// -------- END --------

‍