Sample Code in C++<\/h2>\n

<\/div>

#include <stdio.h> #include <stdlib.h> \/* A binary tree tNode has data, pointer to left child and a pointer to right child *\/struct traversalNode { \tint data; \tstruct traversalNode* left; \tstruct traversalNode* right; }; \/* Function to traverse binary tree without recursion and without stack *\/void MorrisTraversal(struct traversalNode* root) { \tstruct traversalNode *current, *pre; \tif (root == NULL) \t\treturn; \tcurrent = root; \twhile (current != NULL) { \t\tif (current->left == NULL) { \t\t\tprintf("%d ", current->data); \t\t\tcurrent = current->right; \t\t} \t\telse { \t\t\t\/* Find the inorder predecessor of current *\/\t\t\tpre = current->left; \t\t\twhile (pre->right != NULL && pre->right != current) \t\t\t\tpre = pre->right; \t\t\t\/* Make current as right child of its inorder \t\t\tpredecessor *\/\t\t\tif (pre->right == NULL) { \t\t\t\tpre->right = current; \t\t\t\tcurrent = current->left; \t\t\t} \t\t\t\/* Revert the changes made in if part to restore \t\t\tthe original tree i.e., fix the right child \t\t\tof predecssor *\/\t\t\telse { \t\t\t\tpre->right = NULL; \t\t\t\tprintf("%d ", current->data); \t\t\t\tcurrent = current->right; \t\t\t} \/* End of if condition pre->right == NULL *\/\t\t} \/* End of if condition current->left == NULL*\/\t} \/* End of while *\/} \/* UTILITY FUNCTIONS *\/\/* Helper function that allocates a new tNode with the given data and NULL left and right pointers. *\/struct traversalNode* newtraversalNode(int data) { \tstruct traversalNode* node = new traversalNode; \tnode->data = data; \tnode->left = NULL; \tnode->right = NULL; \treturn (node); } \/* Driver program to test above functions*\/int main() { \t\/* Constructed binary tree is \t\t\t12 \t\t\/ \\ \t\t13\t 14 \t\/ \\ \t15\t 16 *\/\tstruct traversalNode* root = newtraversalNode(12); \troot->left = newtraversalNode(13); \troot->right = newtraversalNode(14); \troot->left->left = newtraversalNode(15); \troot->left->right = newtraversalNode(16); \tMorrisTraversal(root); \treturn 0; } <\/code><\/pre> <\/div>\n
\n
\n
Output<\/h2>\n<\/div>\n<\/div>\n
\n
\n
\n
15 13 16 12 14 \r\n<\/span><\/code><\/pre>\n<\/figure>\n<\/div>\n<\/div>\n
\n
\n
\n
Time Complexity : O(n) If we investigate, we can see that each edge of the tree is crossed at-most multiple times.<\/li>\n
Also, in most pessimistic scenario same number of additional edges (as info tree) are made and evacuated.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
Answer : To traverse the tree using Morris Traversal…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"passster_activate_protection":false,"passster_protect_child_pages":"","passster_protection_type":"password","passster_password":"","passster_activate_overwrite_defaults":"","passster_headline":"","passster_instruction":"","passster_placeholder":"","passster_button":"","passster_id":"","passster_activate_misc_settings":"","passster_redirect_url":"","passster_hide":"no","passster_area_shortcode":"","gtb_hide_title":false,"gtb_wrap_title":false,"gtb_class_title":"","gtb_remove_headerfooter":false,"footnotes":""},"categories":[3028],"tags":[195,971,491,221,3594,3598,3588,368,3596,3577,203,199,214,198,363,3057,3591,205,222,484,3054,196,212,3595,3592,3575,3586,3589,3593,3582,3590,3583,3581,3573,3580,3585,3579,3587,3578,207,366,204,3584,3574,3576,206,972,200,3055,197,3597,968,3056,285,969],"class_list":["post-507","post","type-post","status-publish","format-standard","hentry","category-data-structure","tag-accenture-interview-questions-and-answers","tag-altimetrik-india-pvt-ltd-interview-questions-and-answers","tag-applied-materials-interview-questions-and-answers","tag-bharti-airtel-interview-questions-and-answers","tag-binary-search-tree-inorder-traversal","tag-binary-search-tree-traversal-inorder-preorder-postorder-example","tag-binary-tree-inorder-traversal","tag-bmc-software-interview-questions-and-answers","tag-bst-inorder-traversal","tag-c-tree-traversal-without-recursion","tag-capgemini-interview-questions-and-answers","tag-casting-networks-india-pvt-limited-interview-questions-and-answers","tag-cgi-group-inc-interview-questions-and-answers","tag-chetu-interview-questions-and-answers","tag-ciena-corporation-interview-questions-and-answers","tag-collabera-te-interview-questions-and-answers","tag-construct-binary-tree-from-preorder-and-inorder-traversal","tag-dell-international-services-india-pvt-ltd-interview-questions-and-answers","tag-flipkart-interview-questions-and-answers","tag-genpact-interview-questions-and-answers","tag-globallogic-india-pvt-ltd-interview-questions-and-answers","tag-ibm-interview-questions-and-answers","tag-indecomm-global-services-interview-questions-and-answers","tag-inorder-preorder-postorder-traversal","tag-inorder-preorder-postorder-traversal-examples-pdf","tag-inorder-preorder-postorder-traversal-without-recursion-in-c","tag-inorder-traversal","tag-inorder-traversal-algorithm","tag-inorder-traversal-example","tag-inorder-traversal-iterative-python","tag-inorder-traversal-java","tag-inorder-traversal-python","tag-inorder-traversal-with-recursion","tag-inorder-traversal-without-recursion","tag-inorder-traversal-without-recursion-and-stack","tag-inorder-traversal-without-recursion-in-c","tag-inorder-traversal-without-recursion-using-stack-in-c","tag-inorder-tree-traversal","tag-inorder-tree-traversal-without-recursion","tag-mphasis-interview-questions-and-answers","tag-netapp-interview-questions-and-answers","tag-oracle-corporation-interview-questions-and-answers","tag-postorder-traversal-algorithm-using-stack","tag-postorder-traversal-without-recursion","tag-preorder-traversal-without-recursion","tag-sap-labs-india-pvt-ltd-interview-questions-and-answers","tag-sapient-consulting-pvt-ltd-interview-questions-and-answers","tag-tech-mahindra-interview-questions-and-answers","tag-tracxn-technologies-pvt-ltd-interview-questions-and-answers","tag-unitedhealth-group-interview-questions-and-answers","tag-what-is-inorder-traversal","tag-wipro-infotech-interview-questions-and-answers","tag-wm-global-technology-services-india-pvt-ltd-limited-wmgts-interview-questions-and-answers","tag-xoriant-solutions-pvt-ltd-interview-questions-and-answers","tag-yodlee-infotech-pvt-ltd-interview-questions-and-answers"],"yoast_head":"\n