🙏

জয়  শ্রী  রাম

🕉

---

Prerequisite:

• Threaded Binary Tree

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:

Login to Access Content

Python code:

Login to Access Content

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:

Login to Access Content

Python code:

Login to Access Content

Time Complexity:

We are visiting each node twice (1^st visit: compute predecessor and modify predecessor's right child pointer. 2^nd 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:

• Morris Preorder Traversal
• Morris Postorder Traversal
• Iterative Tree Traversal

Instructor: