LeetCode Binary Tree Postorder Traversal: 6 Implementations in 3 Categories Part 2

Overview

As I discussed in last post I actually found six different kinds of implementations for this problem, but all of them fall into three categories: (1) recursive method which is trivial (2) reverse way of preorder traversal, quite elegant way (3) simulate the behavior of the recursive method by using a stack, and the key of this method is to understand when shall we print a node value. In this post, I discuss the third one which is less straightforward than the first two. Let’s recall the following problem description first.

LeetCode Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Analysis: Simulate with Stack

So I will discuss the (3) category which simulate the recursive approach with stack in detail here, for the first two, please check my last post . In this third approach, we try to simulate the behavior of the recursive method by using an explicit stack. The key point here is that we need to understand clearly when we should print a node value. Recall the recursive method, it is quite straightforward, after all the left and right subtrees of root node is processed, we print root->val and that’s it!

After understanding the above key point, the remaining problem is how should we know the the processing of root’s subtrees are finished, i.e., we now start to traverse up along the tree from the right child to root. More concretely, using an explicit stack to do the recursive traversal, there could be only two cases, at first we traverse down along three from the root to its left and right subtrees, in this case, we shall keep the root in the stack. And the other case is that we traverse back after processing the subtrees, in this case, the root value should be printed and the root node itself finishes processing so it needs to be popped out. This is the algorithm logic, and there are three ways to indicate whether we are travelling down or travelling up:

(a) by using a pre pointer pointing to the previous visited node, this is quite popular way if you search the internet

(b) by setting the root->left = NULL and root->right = NULL if we got a node with at least one subtree is non-empty, and whenever we got a node with bother its left and right children are empty, we need to print it out and pop it out of the stack. This method will destroy the input and is not recommended.

(c) everything we push a node into stack twice, and we check a POPPED out node if it is the same as the current top of the stack, if it is, then it is our first time to see this node (i.e., traverse down), we push its subtrees into the stack. If it is not the same as the current top of the stack, then it must be traverse up, we need to print it out.

(*) there is a forth implementation too: using an explicit array of flags to indicate whether a node is visited or not, if it is visited already, then it must be traverse up. This method I will leave you guys to implement it. The following are the code for methods (a) to (c) although the essential algorithm logic key is the same for all of them:

// (a) using pre pointer
        void postorder_iteratively_a(TreeNode *root, vector<int> *pvecPostorder)
	{
		if (NULL == pvecPostorder)
			throw runtime_error("NULL pointer to the reuslt!");
		if (NULL == root) return ;

		stack<TreeNode *> stk;
		stk.push(root);
		TreeNode *pre  = NULL;
		TreeNode *curr = NULL;
		while(!stk.empty()) {
			curr = stk.top();
			if (NULL == curr->left && NULL == curr->right) {
				pvecPostorder->push_back(curr->val);
				stk.pop();
			}
			else {
				if (NULL != pre && (curr->left == pre || curr->right == pre)) {
					pvecPostorder->push_back(curr->val);
					stk.pop();
				}
				else {
					if (curr->right) stk.push(curr->right);
					if (curr->left) stk.push(curr->left);
				}
			}
			pre = curr;
		}
	}

        // (b) destroying the input
        void postorder_iteratively_b(TreeNode *root, vector<int> *pvecPostorder)
	{
		if (NULL == pvecPostorder)
			throw runtime_error("NULL pointer to the reuslt!");
		if (NULL == root) return ;

		stack<TreeNode *> stk;
		stk.push(root);
		while (!stk.empty()) {
			root = stk.top();
			if (NULL == root->left && NULL == root->right) {
				pvecPostorder->push_back(root->val);
				stk.pop();
				continue ;
			}
			if (root->right) stk.push(root->right);
			if (root->left) stk.push(root->left);

			root->left = NULL;
			root->right = NULL;
		}
	}

        // (c) pushing twice
        void postorder_iteratively_c(TreeNode *root, vector<int> *pvecPostorder)
	{
		if (NULL == pvecPostorder)
			throw runtime_error("NULL pointer to the reuslt!");
		if (NULL == root) return ;

		stack<TreeNode *> stk;
		stk.push(root);
		stk.push(root);
		while (!stk.empty()) {
			root = stk.top(); stk.pop();
			if (!stk.empty() && stk.top() == root) {
				if (root->right) stk.push(root->right), stk.push(root->right);
				if (root->left) stk.push(root->left), stk.push(root->left);
			}
			else
				pvecPostorder->push_back(root->val);
		}
	}

Tips and Remarks:

Note in all of the tree implementations, we always push the right child first, then we push the left child, this is because postorder is Left Child->ROOT->Right Child, so the left child will be processed first next time we popping out nodes from the stack, this pushing order also make the traverse up/down cases simpler, in my code, there could only be two cases, traverse down and traverse up (must be from right child to root), you can think about why? So I think this post is sort of misleading and make things more complex by giving three case (left child back to root, right child back to root, root to left and right child).

Summary

There are 6 different implementations for this problem, but all of them fall into 3 categories: (1) recursive method which is trivial (2) reverse way of preorder traversal (3) simulate the behavior of the recursive method by using a stack. In this post, details of how to simulate the recursive postorder traversal by stack is discussed which is the third category and is less straightforward than the first two: 1. using prev pointer 2. push twice 3. setting child to NULL 4. Extra array.

Written on July 24, 2014