Solution: With stack, we can iteratively traverse the tree. Here explain a way to traverse the tree without stack. The main idea is to use threaded tree. The key is to leverage the right child pointer of a node that is null. Then set this null-valued right child pointer to the in-order successor of the node. The detail of the algorithm is as follow:
- Inspect a node n, if the node doesn't have a left child, visit this node, then proceed to its right child.
- If the node n has left child, there are two situations. The first is that the predecessor of n has not been processed. Then we need to find a right_most node that will be the predecessor of n set right_most's right child to be n. If n's left child has a right child, right_most is left child's right-most child; if n's left child doesn't have a right child, right_most is left child itself. Then we proceed to n's left child.
- The second situation is that the predecessor of n has been processed. We can tell this by keep following n's left child's right child pointer until a right child pointer points to n or the pointer is null. If the pointer points to n, it means the predecessor of n has been processed, then we visit n, proceed to its right child. We can do one extra thing here, before moving forward, we can set the right child of n's predecessor to be null, since previously we modified its value to thread the tree. By doing this, we can keep the tree unmodified after traversal.
- The algorithm stops when we find the current node is null
void Non_recursive_tree_traversal(TreeNode *root) { if(!root) return; TreeNode *cur = root; while(cur) { // if no left child, visit itself if(!cur->left) { visit(cur); cur = cur->right; } // left child is there else { TreeNode *pp = cur->left; while(pp->right) { if(pp->right == cur) break; pp = pp->right; } // if cur's predecessor has been visited if(pp->right == cur) { visit(cur); // revert the right pointer to null pp->right = NULL; cur = cur->right; } else if(!pp->right) { // if the right child pointer is null // set its value to thread the tree pp->right = cur; cur = cur->left; } } } }
Thanks for the code... I have written an article which explains the same thing and helps with java programs for the same.
ReplyDeleteFor people who might be looking more into detail here it is http://techieme.in/techieme/iterative-tree-traversals/