The time complexity of Morris Traversal is O(n), where n is the number of nodes in the binary tree. Morris Traversal achieves linear time complexity, making it an efficient in-place algorithm for inorder tree traversal.
Here's why Morris Traversal has a time complexity of O(n):
-
Traversal Operation per Edge:
- Each edge in the binary tree is traversed exactly twice—once to set the threaded link (to establish the connection to the inorder successor or predecessor) and once to reset the threaded link.
-
Total Number of Operations:
- The total number of operations for all edges in the tree is proportional to the number of nodes (n). In the worst case, every edge is traversed twice.
-
Constant Factor:
- The algorithm involves a constant amount of work per edge traversal, as the operations for establishing and resetting the threaded links are constant-time operations.
Therefore, the overall time complexity is O(n), making Morris Traversal particularly useful when there are constraints on using extra space (like a stack) for tree traversal. It achieves an efficient in-order traversal without the need for additional data structures, making it a space-efficient and linear-time solution.
