[LeetCode] Binary Tree Preorder && Inorder && Postorder Traversal

Tree traversal is quite standard problems. For each of the traversals, both recursive and Iterative methods are described.

Binary Tree Preorder Traversal

Problem Statement (link):

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?

Analysis:
Recursive method is trivial as implemented in Sol 1.

In iterative method, a stack is used to store nodes temporarily. In each loop, the current top node in stack is popped and push_back in output vector, then we push its right child and left child in stack if not NULL. The push order is reversed compare to pre-order traversal as stack has the first-in-last-out property. This process continues until the stack is empty.

Code:
Sol 1 - Recursive:

vector<int> preorderTraversal(TreeNode *root) {
    vector<int> out;
    recur(root, out);
    return out;
}
void recur(TreeNode *node, vector<int>& out) {
    if (node==NULL) return;
    out.push_back(node->val);
    recur(node->left, out);
    recur(node->right, out);
}

Sol 2 - Iterative:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        stack<TreeNode*> nodeS;
        vector<int> valV;
        if (root == NULL) return valV;
        nodeS.push(root);
        while(!nodeS.empty()) {
            TreeNode *node = nodeS.top();
            nodeS.pop();
            valV.push_back(node->val);

            // Note the push order is reversed as the push order is exact reversed of pop order
            if (node->right != NULL) {
                nodeS.push(node->right);
            }
            if (node->left != NULL) {
                nodeS.push(node->left);
            }
        }
        return valV;
    }
};

Binary Tree Inorder Traversal

Problem Statement (link):

Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?

Analysis:
A good analysis article about in-order traversal is here.

Recursive method is trivial as implemented in Sol 1.

In the iterative method, a stack is used to store nodes temporarily. We store nodes if it's not NULL, and traverse to its left child; we pop the nodes and store in output vector if current node is NULL, and traverse to its right child. As in Sol 2.

Code:
Sol 1 - Recursive:

vector<int> inorderTraversal(TreeNode *root) {
    vector<int> valV;
    inOrder(root, valV);
    return valV;
}

void inOrder(TreeNode *node, vector<int> &valV) {
    if (node==NULL) return;
    inOrder(node->left, valV);
    valV.push_back(node->val);
    inOrder(node->right, valV);
}

Sol 2 - Iterative:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
using namespace std;
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> output;
        if (root==NULL) return output;
        stack<TreeNode*> nodeS;
        TreeNode* node = root;
        while (node!=NULL || !nodeS.empty()) {
            if(node!=NULL) {
                nodeS.push(node);
                node = node->left;
            }
            else {
                node = nodeS.top();
                nodeS.pop();
                output.push_back(node->val);
                node = node->right;
            }
        }
    }
};

Binary Tree Postorder Traversal

Problem Statement (link):

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:
A very good article about the post-order traversal is here.

The recursive solution is trivial as implemented in Sol 1.

In the iterative method, two stacks are used - one stack method exists but a bit complicated. When traversing the tree from left child to right child, we push nodes into a nodeStack, then pop each node into outputStack. See Sol 2 below.

Code:
Sol 1: Recursive

vector<int> postorderTraversal(TreeNode *root) {
    vector<int> out;
    recur(root, out);
    return out;
}
void recur(TreeNode *node, vector<int>& out) {
    if(node==NULL) return;
    recur(node->left, out);
    recur(node->right, out);
    out.push_back(node->val);
}

Sol 2: Iterative

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> output;
        if (root==NULL) return output;
        // use two stacks
        stack<TreeNode *> nodeStack;
        stack<TreeNode *> outputStack;
        TreeNode* node = root;
        nodeStack.push(node);
        while(!nodeStack.empty()) {
            node = nodeStack.top();
            outputStack.push(node);
            nodeStack.pop();
            if (node->left != NULL) nodeStack.push(node->left);
            if (node->right != NULL) nodeStack.push(node->right);
        }
        while(!outputStack.empty()) {
            node = outputStack.top();
            output.push_back(node->val);
            outputStack.pop();
        }
    }
};