## Morris Traversal

void MorrisTraversal(TreeNode *root) { TreeNode* current = root; while(current!=NULL) { if(current->left==NULL) { cout<<current->value<<" "; current = current->right; } else { TreeNode* pre = current->left; while(pre->right!=NULL && pre->right!=current) { pre = pre->right; } if(pre->right==NULL) { pre->right = current; current = current->left; } else { pre->right =NULL; cout<<current->value<<" "; current = current->right; } } } }

Advertisements

## Level Order Traversal in Tree

It’s a pretty popular algorithm based interview question and it helps to have studied graphs because Breadth First Search and a bit of STL makes this program very easy to implement. The example of level order traversal is to print the nodes in the following order : –

struct node { int value; struct node *left; struct node *right; }; typedef struct node TreeNode; void printLevelOrderTraversal(TreeNode* &root) { queue<TreeNode*> q; TreeNode* current; current = root; while(current!=NULL) { printf("%d\n",current->value); if(current->left) q.push(current->left); if(current->right) q.push(current->right); current = q.front(); q.pop(); } }