Morris Inorder Traversal
Hard Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Morris Inorder Traversal of a Binary Tree, Binary Tree, In-order Traversal, Iterative Algorithm, In-place Algorithm, Time Complexity, Space Complexity, Tree Traversal, Morris Traversal, inorder traversal, tree operations, binary tree, pointer operations, space optimization, tree data structure, Morris Traversal (O(1) Space).
Given the root of a Binary Tree, return the array containing its inorder traversal sequence using Morris Traversal. Morris Inorder Traversal is a tree traversal algorithm that achieves O(1) space complexity without recursion or an external data structure. Your algorithm should efficiently visit each node in the binary tree in inorder sequence. Input Format: The input will be a list of integers representing the binary tree in level order traversal. A value of 1 indicates a null node. Output Format: Return a list of integers representing the inorder traversal of the binary tree. Constraints: The number of nodes in the tree will be between 0 and 10^5. Node values will be between 10^9 and 10^9. Example 1: Input: [4, 2, 5, 3, 1, 7, 6, 1, 9, 1, 1, 8, 1, 1] Output: [3, 1, 9, 2, 4, 7, 5, 8, 6] Explanation: The inorder traversal (Left, Root, Right) of the given tree is [3, 1, 9, 2, 4, 7, 5, 8, 6]. Example 2: Input: [1, 2, 3, 4, 5, 6, 7, 1, 1, 8, 1, 1, 1, 9, 10] Output: [4, 2, 8, 5, 1, 6, 3, 9, 7, 10] Explanation: The inorder traversal (Left, Root, Right) of the given tree is [4, 2, 8, 5, 1, 6, 3, 9, 7, 10]. Difficulty: Medium