Morris Preorder Traversal
Hard Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Morris Preorder Traversal of a Binary Tree, Binary Tree, Preorder Traversal, In-order Traversal, Tree Traversal, Iterative Algorithm, Time Complexity, Space Complexity, In-place Algorithm, Pointer, in-place algorithms, morris traversal, tree operations, traversal optimization, preorder traversal, tree data structure, tree traversal, Flatten Binary Tree to Linked List, Morris Traversal (O(1) Space).
Given the root of a Binary Tree, implement Morris Preorder Traversal and return an array containing its preorder sequence. Morris Preorder Traversal is a tree traversal algorithm that achieves O(1) space complexity without using recursion or an external data structure like a stack. The algorithm should efficiently visit each node in the binary tree in preorder sequence (Root, Left, Right). Input Format: The input will be given as a space separated string representing the level order traversal of the binary tree. 1 denotes a null child. For example, 4 2 5 3 1 7 6 1 9 1 1 8 1 1 represents the following tree: Output Format: Return an array of integers representing the preorder traversal of the given binary tree. Examples: Example 1: Input: 4 2 5 3 1 7 6 1 9 1 1 8 1 1 Output: [4, 2, 3, 9, 1, 5, 7, 6, 8] Example 2: Input: 1 2 3 4 5 6 7 1 1 8 1 1 1 9 10 Output: [1, 2, 4, 5, 8, 3, 6, 7, 9, 10]