# Untitled

unknown
c_cpp
a year ago
5.4 kB
0
Indexable
Never
```// ==================== Aproach 1 ====================
/*
Approach 1 Iterative - Push a node two times in stack.
The first time its poped means LST is covered (curr == st.top())
The second time its poped means LST and RST both covered so now print the root.
*/

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 ====================
// Morris Tree traversal

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;

// 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;
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;

// 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;
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;

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

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;
}```