Untitled

// ==================== Aproach 1 ====================
vector<vector<int>> getTreeTraversal(BinaryTreeNode<int> *root) {
    BinaryTreeNode<int> *curr = root;
    stack<BinaryTreeNode<int> *> st;
    vector<vector<int>> inPrePostRes(3);

    while (!st.empty() || curr != NULL) {
        if (curr != NULL) {
            inPrePostRes[1].push_back(curr -> data);
            st.push(curr);
            st.push(curr);
            curr = curr -> left;
        } else {
            curr = st.top();
            st.pop();

            if (st.size() > 0 && curr == st.top()) {
                inPrePostRes[0].push_back(curr -> data);
                curr = curr -> right;
            } else {
                inPrePostRes[2].push_back(curr -> data);
                curr = NULL;
            }
        }
    }

    return inPrePostRes;
}





// ==================== Aproach 2 ====================

void inorderTraversal(BinaryTreeNode<int> *root, vector<int> &inorderArr) {
    BinaryTreeNode<int> *curr = root;

    while(curr != NULL) {
        if (curr -> left == NULL) { // LST doesn’t exist so curr comes in inorder and then move to RST.
            inorderArr.push_back(curr -> data);
            curr = curr -> right;
        } else {
            BinaryTreeNode<int> *rightMost = curr -> left;
            bool connectThread = true;

            // Find rightMost element of curr's LST. Two cases are possible.
            // case 1. RightMost element reached -> then thread it i.e. point its right child to curr.
            // case 2. RightMost element reached but its already threaded -> This implies we have already visited LST. So remove thread & move on to curr's RST.
            while (rightMost -> right != NULL) {
                if (rightMost -> right == curr) { // case 2
                    rightMost -> right = NULL;
                    inorderArr.push_back(curr -> data);
                    curr = curr -> right;
                    connectThread = false;
                    break;
                }
                rightMost = rightMost -> right;
            }

            if (connectThread) { // case 1
                rightMost -> right = curr;
                curr = curr -> left;
            }
        }
    }
}

void preorderTraversal(BinaryTreeNode<int> *root, vector<int> &preorderArr) {
    BinaryTreeNode<int> *curr = root;

    while (curr != NULL) {
        if (curr -> left == NULL) { // LST doesn’t exist so curr comes in preorder and then move to RST.
            preorderArr.push_back(curr -> data);
            curr = curr -> right;
        } else {
            BinaryTreeNode<int> *rightMost = curr -> left;
            bool createThread = true;

            // Find rightMost element of curr's LST. Two cases are possible.
            // case 1. RightMost element reached -> then thread it i.e. point its right child to curr.
            // case 2. RightMost element reached but its already threaded -> This implies we have already visited LST. So remove thread & move on to curr's RST.
            while (rightMost -> right != NULL) { // case 2
                if (rightMost -> right == curr) {
                    rightMost -> right = NULL;
                    curr = curr -> right;
                    createThread = false;
                    break;
                }
                rightMost = rightMost -> right;
            }

            if (createThread) { // case 1
                rightMost -> right = curr;
                preorderArr.push_back(curr -> data);
                curr = curr -> left;
            }
        }
    }
}

 // Post order is = root, right, left -> and then reverse the output.
void postorderTraversal(BinaryTreeNode<int> *root, vector<int> &postorderArr) {
    BinaryTreeNode<int> *curr = root;

    while (curr != NULL) {
        if (curr -> right == NULL) {
            postorderArr.push_back(curr -> data);
            curr = curr -> left;
        } else {
            BinaryTreeNode<int> *leftMost = curr -> right;
            bool createThread = true;

            while (leftMost -> left != NULL) {
                if (leftMost -> left == curr) {
                    leftMost -> left = NULL;
                    curr = curr -> left;
                    createThread = false;
                    break;
                }
                leftMost = leftMost -> left;
            }

            if (createThread) {
                leftMost -> left = curr;
                postorderArr.push_back(curr -> data);
                curr = curr -> right;
            }
        }
    }

    reverse(postorderArr.begin(), postorderArr.end());
}

vector<vector<int>> getTreeTraversalAprroch2(BinaryTreeNode<int> *root){
    vector<vector<int>> traversal(3);
    inorderTraversal(root, traversal[0]);

    preorderTraversal(root, traversal[1]);

    postorderTraversal(root, traversal[2]); // Post order is = root, right, left -> and then reverse the output.

    return traversal;
}