Morris Inorder Traversal
Optimizing Space Complexity of Inorder Binary Tree Traversal from Average Time O(N) for Balanced Binary Tree and Worst case O(logN) for Chained or Skewed Binary Tree to O(1) using concept of Threaded Binary Tree, , where N = total number of nodes in the tree
-
Algorithms and Data Structures: TheAlgorist.com
-
System Design: DistributedComputing.dev
-
Low Level Design: LowLevelDesign.io
-
Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
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:
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 (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:
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
