Pre, In, Post Order Traversal

Related problem:

144 Binary Tree Preorder Traversal
94 Binary Tree Inorder Traversal
145 Binary Tree Postorder Traversal
99 Recover Binary Search Tree

在写tree的算法之前，前中后序遍历的 recursive 写法和 iterative 写法必须熟练：

You can find the definitions for the three traversals here

• Recursive Solution (Trivial Solution) :

/*
 Definition for a binary tree node.
 struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
 */
//preOrder
void preorder(TreeNode* root) {
        if (!root) return; // '!root' means 'when root == nullptr'
        cout << root -> val << endl;
        preorder(root -> left);
        preorder(root -> right);
}
//inOrder
void inorder(TreeNode* root) {
        if (!root) return;
        inorder(root -> left);
        cout << root -> val << endl;
        inorder(root -> right);
}
//postOrder
void postorder(TreeNode* root) {
        if (!root) return;
        postorder(root -> left);
        postorder(root -> right);
        cout << root -> val << endl;
}

But you will never get a chance to use these recursive version in a real interview, what really matters is the iterative solution below:

---

• Iterative Solution:
  The meaning of pre/in/post is pretty straight forward in the recursive solution: it is the position where we put the cout << root -> val << endl; that distinguish those three traversals. But you need to get this from a different view in iterative solution.

My thoughts：

preorder: we need to make sure the value in the current TreeNode has been visited before we get to left and right subtree, and we need to make sure the whole left subtree has been visited before we visit right subtree.

---

Inorder: we need to make sure the whole left subtree has been visited before we visit current node, then we visit right subtree node.

---

postorder: we need to make sure all the children nodes for the current node has been visited before we visit current node, and the left subtree is visited before right subtree.

• preorder:

class Solution {
    void pushLeft(TreeNode* root, stack<TreeNode*>& nodes, vector<int>& res) {
    // this function here push all the LEFT node we can get from the input node
        while (root) {
            nodes.emplace(root); // emplace c++11
            res.emplace_back(root -> val); // visit the node once we meet it
            root = root -> left;
        }
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        stack<TreeNode*> nodes; // store the parent node, 
                               //all nodes in the stack has already been visited
        pushLeft(root, nodes, res);
        while (!nodes.empty()) {
            TreeNode* cur = nodes.top() -> right; // cause nodes in the stack 
// has already been visited, we just need to visit the right subtree
            nodes.pop();
            if (cur) // visit the left subtree for the right children
                pushLeft(cur, nodes, res);
        }
        return res;
    }
};

---

• inorder:

class Solution {
      void pushLeft(TreeNode* root, stack<TreeNode*>& nodes) {
  // this function here push all the LEFT node we can get from the input node
        while (root) {
            nodes.emplace(root); // emplace c++11
            root = root -> left;
        }
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        stack<TreeNode*> nodes; // store the parent node, 
                             //all nodes in the stack has already been visited
        pushLeft(root, nodes);
        while (!nodes.empty()) {
            TreeNode* cur = nodes.top() -> right; 
            // nodes in the stack has not been visited yet  

            res.emplace_back(nodes.top() -> val); // a node can get to the top postion
// if and only if it doesn't have a left children or all its left subtree has been
// visited, so it is safe to visit top node now

            nodes.pop(); // once we visited the node, pop it

            if (cur) // store the left subtree for the right children
                pushLeft(cur, nodes);
        }
        return res;
    }
};

---

Notice: the only difference between above two iterative algorithms is the position of res.emplace_back(nodes.top() -> val), so actually I'm using the same idea used in recursive solution. But it's gonna be a different story when it comes to postorder.

• postorder

class Solution {
void pushLeft(TreeNode* root, stack<pair<TreeNode*, bool>>& nodes) {
      while (root) {
          nodes.emplace(root, root -> right == nullptr);
          root = root -> left;
      }
}
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) 
            return res;
        stack<pair<TreeNode*, bool>> nodes;
        pushLeft(root, nodes);
        while (!nodes.empty()) {
            if (!nodes.top().second) {
                nodes.top().second = true;
                pushLeft(nodes.top().first -> right, nodes);
            } else {
                res.emplace_back(nodes.top().first -> val);
                nodes.pop();
            }
        }
        return res;
    }
};

Explanation:

Since we push all the left nodes until the left subtree is empty, the top element nodes.top() in the stack is either guaranteed to have an empty left children, or all nodes in its left subtree has been visited. So we only need to record whether its right children has been visited or not. Once its right subtree has been visited, we can safely visit nodes.top() and pop the top.

---

Morris Traversal:

This algorithm takes O(n) time complexity and O(1) space complexity to complete inorder traversal and preorder traversal. It reconstruct the tree during traversal and recover it after finished traversal.
Detailed explanation: Morris Inorder Tree Traversal

This algorithm can only be used to solve pre/in order.

class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode* current = root;
        TreeNode* first = NULL;
        TreeNode* second = NULL;
        TreeNode* pre = NULL;
        while (current) {
            if (!current -> left) {
                if (pre && pre -> val > current -> val) {
                    if (!first) {
                        first = pre;
                        second = current;
                    } else {
                        second = current;
                    }
                }
                pre = current;
                current = current -> right;
            } else {
                TreeNode* predecessor = current -> left;
                while (predecessor -> right && predecessor -> right != current)
                    predecessor = predecessor -> right;
                if (predecessor -> right) {
                    if (pre && pre -> val > current -> val) {
                        if (!first) {
                            first = pre;
                            second = current;
                        } else {
                            second = current;
                        }
                    }
                    pre = current;
                    predecessor -> right = nullptr;
                    current = current -> right;
                } else {
                    predecessor -> right = current;
                    current = current -> left;
                }
            }
        }
        swap(first -> val, second -> val);
    }
};

Explanation:

Problem #99 require O(n) time complexity and O(1) space complexity, but need to traverse the whole tree to get those wrong nodes. Recursive algorithm uses system stack which is also counted as occupying memory, therefore, Morris Traversal is qualified here.

• If there are two nodes swapped by mistake in a BST, the inorder sequence of this tree will be interrupted.
• If pre -> val > current -> val , then there must be a wrong node between pre and current.
  1.if it is the first time to meet an interruption, pre is wrong.
  2.if it is the second time to meet an interruption, current is wrong.
• Swap the wrong nodes back to its right position.

---