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

Overview

For this problem, I actually found six different kinds of implementations, 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 first two approaches and I will discuss the third one which is less straightforward than the first two in a separate post.

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?

Solution and Source Code:

(1) Recursive method: this one is trivial and quite straightforward, and the following is the accepted code:

class Solution {
public:
	void postorder_recursively(TreeNode *root, vector *pvecPostorder)
	{
		if (NULL == pvecPostorder)
			throw runtime_error("NULL pointer to the reuslt!");
		if (NULL == root) return ;

		postorder_recursively(root->left, pvecPostorder);
		postorder_recursively(root->right, pvecPostorder);
		pvecPostorder->push_back(root->val);
	}
        vector postorderTraversal(TreeNode *root) {
		vector vecResult;
		postorder_iteratively2(root, &vecResult);
		return vecResult;
        }
};

(2) Reverse way of preorder traversal: this method is still sort of straightforward. See the following example:

1
       / \
      2   3
         / \
        4   5

The postorder traversal: 2->4->5->3->1
A normal preorder traversal is Root->Left Child->Right Child, if we always traverse the right child first, i.e., Root->Right Child->Left Child, in the above example, our “Variant Preorder traversal” is: 1->3->5->4->2
We could see, it is exactly the reversed order of postorder traversal. So here comes our idea, do our “Variant Preorder traversal” in the iterative way first, than we reverse the variant preorder list and finally got our correct postorder traversal. And there could be are two different implementations, one using two stacks, one just using one stack followed by a reverse call, both of them use the same idea. Here comes the code:

void postorder_iteratively2(TreeNode *root, vector *pvecPostorder)
	{
		if (NULL == pvecPostorder)
			throw runtime_error("NULL pointer to the reuslt!");
		if (NULL == root) return ;

		stack stk;
		stk.push(root);
		while (!stk.empty()) {
			root = stk.top(); stk.pop();
			pvecPostorder->push_back(root->val);
			if (root->left) stk.push(root->left);
			if (root->right) stk.push(root->right);
		}
		std::reverse(pvecPostorder->begin(), pvecPostorder->end());
	}

	void postorder_iteratively3(TreeNode *root, vector *pvecPostorder)
	{
		if (NULL == pvecPostorder)
			throw runtime_error("NULL pointer to the reuslt!");
		if (NULL == root) return ;

		stack stk;
		stack stk_vals;
		stk.push(root);
		while (!stk.empty()) {
			root = stk.top(); stk.pop();
			stk_vals.push(root->val);
			if (root->left) stk.push(root->left);
			if (root->right) stk.push(root->right);
		}
		while (!stk_vals.empty()) {
			pvecPostorder->push_back(stk_vals.top());
			stk_vals.pop();
		}
	}

Although if we search the internet, the method of using two stacks is quite popular, I doubt that it might not be a good implementation since essentially the second stack is just a way to reverse the preorder list explicitly, and it cost more memory. I think postorder_iteratively2() is a more elegant one.

(3) Simulate the recursive approach by using an explicit stack: The one is much less straightforward than the first two methods, and to my knowledge, there could be three different implementations. All of them use different approaches to indicate the traversal order (traverse down or up). I will discuss this in a separate post later.

Updated: Please check this “leetcode: Binary Tree Postorder Traversal Solution Analysis 2” out for the analysis of method (3).

More Tips and Remarks:

Implement Preorder traversal is normally easy, so a good hint to come up with the iterative implementation of the postorder traversal is by imitating the iterative implementation of the preorder traversal at the first place, and then you might want a trial and error. My experience is that method (2) and (3) could be found from imitating and adjusting the code of preorder traversal.

Summary

There are six different kinds of implementations falling into three categories: (1) recursive method (2) reverse way of preorder traversal (3) simulate the behavior of the recursive method by using a stack. In this post, I discuss the first two approaches.

Written on July 23, 2014