LeetCode Binary Tree Preorder Traversal: Iterative Using Stack

Overview

Both recursive and iterative using stack methods are are discussed to solve LeetCode Binary Tree Preorder Traversal with details to make the code compact.

LeetCode Binary Tree Preorder Traversal

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

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

1
    \
     2
    /
   3

return [1,2,3].

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

Solution Analysis: Iterative using Stack

As already mentioned in the problem description, the recursive solution is trivial, I don’t bother to discuss this one but talk a little about the iterative solution. A straightforward way to convert from recursive solution into an iterative one is by using Stack. Yes, stack is what we need to implement the iterative solution. Just recall the preorder traversal, we handle the root first, then root->left, then root->right, so when it comes to using a stack, we just push the initial root into the stack first, and then we repeatedly pop out the top node from the stack and put the value into our result, and then we push the right child first and then the left child into the stack, not we need to push the RIGHT CHILD FIRST. So here comes the code of both the recursive and iterative implementation:

class Solution {
public:
	void preorder_recursively(TreeNode *root, vector<int> *pvecPreOrder)
	{
		if (NULL == pvecPreOrder)
			throw runtime_error("NULL Pointer To Preorder Result!");

		if (NULL == root)
			return ;

		pvecPreOrder->push_back(root->val);
		preorder_recursively(root->left, pvecPreOrder);
		preorder_recursively(root->right, pvecPreOrder);
	}

	void preorder_iteratively(TreeNode *root, vector<int> *pvecPreOrder)
	{
		if (NULL == pvecPreOrder)
			throw runtime_error("NULL Pointer To Preorder Result!");

		if (NULL == root)
			return ;

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

        vector<int> preorderTraversal(TreeNode *root) {
		vector<int> vecResultOrder;
		// preorder_recursively(root, &vecResultOrder);
		preorder_iteratively(root, &vecResultOrder);
		return vecResultOrder;
        }
};

LeetCode Binary Tree Preorder Traversal Key Remarks:

As I said at the beginning, the algorithm is not that difficult to come up with, but there are several noteworthy points to make the code more elegant:

(1) using exception or other error handling techniques to make the code more robust

(2) avoid declaring temporary variables in a while or for loop. As in the recursive implementation, I just use the variable root to get the current popped out node, some people might want to declare a temporary variable say TreeNode * pCurrentNode = stk.top() which I consider to be less efficient.

(3) be careful on the order to push the two children of the root, the correct preorder traversal is like root, then left child, then right child, so we have to push the right child of the root first into the stack.

Summary

Both recursive and iterative using stack methods are are discussed to solve LeetCode Binary Tree Preorder Traversal with details to make the code compact.

 

Written on July 20, 2014