• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.



Prerequisite:


The concept of Morris Inorder Traversal is explained in the video below. It is highly recommended that you please read the chapter on Threaded Binary Tree first, if you already haven't done so, and then watch the video for a better understanding. Please excuse my speech impediment while watching the video. Thank you for your patience.




Working Code:


Java code:



This is a Premium content.
Please subscribe to Algorithms course to access the code.





Python code:



This is a Premium content.
Please subscribe to Algorithms course to access the code.





Further Optimization:


The above implementation has a major problem:
  • We are modifying the right child pointer of the leaf nodes but never recovering them. This results in side-effects which are not desired in a Clean Code, unless and until we are explicitly told that side-effect is fine as per the given requirements. we are told that

We will be solving the above mentioned problem in the code below. Every time we visit a node we will compute it's inorder predecessor and check whether the right child pointer of the predecessor is null or already point to the current node. If it is already pointing to the current node that means it is the second visit and we recover the modified right child pointer by pointing it back to null. When we visit a node for the first time we just compute the predecessor and modify the predecessor's right child pointer so that we can come back to the current node to visit it once the left subtree of the current node is entirely processed. In our second visit to the a node we actually visit it and process it.

Java code:



This is a Premium content.
Please subscribe to Algorithms course to access the code.





Python code:



This is a Premium content.
Please subscribe to Algorithms course to access the code.





Time Complexity:

We are visiting each node twice (1st visit: compute predecessor and modify predecessor's right child pointer. 2nd Visit: Visit/Process the current node and recover its predecessor's modified right child pointer and move on to the current node's right child node). So overall time complexity O(2n) = O(n). Notice that in the first implementation we visit each node only once so the time complexity of the first implementation is O(n) and not O(2n).

Space Complexity:

O(1). No extra space for traversal.


Related chapters:



The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave