Microsoft interview question
Write an algorithm that does an in-order traversal of a tree recursively. Now, write the same algorithm iteratively.
Interview Answers
Anonymous
// recursive void InorderTraversal( Node *root) { if ( root== NULL) return ; // status 2 InorderTraversal( root->left ); // status 1 Print (root); InorderTraversal(root->right); // status 0 } // NON-Recursive Version for Pre/In/Post-Order the idea behind this method is to employ a stack to emulate the recursion void NonRecTraversal( Node *root ) { if ( root == NULL ) return ; stack stk; bool flag = 2;// the key: keep track of the status of the top element stk.push(root); while( !stk.empty()) { if ( flag == 2 ) { /* Print (node) ; this is preorder */ if ( stk.top()->left != NULL ) stk.push(stk.top()->left ); else flag = 1; } else if ( flag == 1) { /* Print (node) ; this is inorder */ if ( stk.top()->right != NULL) { stk.push(stk.top()->right); flag = 2; } else flag = 0; } else { /* Print (node) ; this is postorder */ Node *temp = stk.top(); Stk.pop(); If ( !stk.empty() && stk.top()->left == temp ) Flag = 1; // come back from left child Else Flag = 0; // come back from right child } } }