Inorder Non-threaded Binary Tree Traversal without Recursion or Stack - GeeksforGeeks
Read full article from Inorder Non-threaded Binary Tree Traversal without Recursion or Stack - GeeksforGeeks
We have discussed Thread based Morris Traversal. Can we do inorder traversal without threads if we have parent pointers available to us?
In inorder traversal, we follow “left root right”. We can move to children using left and right pointers. Once a node is visited, we need to move to parent also. For example, in the above tree, we need to move to 10 after printing 5. For this purpose, we use parent pointer. Below is algorithm.
1. Initialize current node as root
2. Initialize a flag: leftdone = false;
3. Do following while root is not NULL
a) If leftdone is false, set current node as leftmost
child of node.
b) Mark leftdone as true and print current node.
c) If right child of current nodes exists, set current
as right child and set leftdone as false.
d) Else If parent exists, If current node is left child
of its parent, set current node as parent.
If current node is right child, keep moving to ancestors
using parent pointer while current node is right child
of its parent.
e) Else break (We have reached back to root)
// Function to print inorder traversal using parent// pointervoid inorder(Node *root){ bool leftdone = false; // Start traversal from root while (root) { // If left child is not traversed, find the // leftmost child if (!leftdone) { while (root->left) root = root->left; } // Print root's data printf("%d ", root->key); // Mark left as done leftdone = true; // If right child exists if (root->right) { leftdone = false; root = root->right; } // If right child doesn't exist, move to parent else if (root->parent) { // If this node is right child of its parent, // visit parent's parent first while (root->parent && root == root->parent->right) root = root->parent; if (!root->parent) break; root = root->parent; } else break; }}