Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited once during the flattening process.

Space Complexity: O(log₂N), where N is the number of nodes in the Binary Tree. There are no additional data structures or space used but the auxiliary stack space is used during recursion. Since the recursion depth can be at most equal to the height to the Binary Tree, the space complexity is O(H) where H is the height of the Binary Tree. In the ideal case, H = log2N and in the worst case H = N (skewed tree).

Better Approach

Algorithm

Base Case: If the root node is null, return as there is no tree to flatten.
Initialize Stack: Create a stack to perform an iterative traversal of the binary tree. Push the root node onto the stack to start the traversal.
Iterative Traversal with Stack:
- While the stack is not empty, repeat the following steps:
- Pop the top node from the stack.
- If the popped node has a right child, push it onto the stack to process it after the left child nodes.
- If the popped node has a left child, push it onto the stack.
- If the stack is not empty after pushing the left child, connect the right pointer of the current node (popped from the stack) to the top node of the stack. This creates the linked list structure by setting the next pointer.
- Set the left pointer of the current node to null as we need to form a right-skewed linked list.
Once the stack becomes empty, the traversal is complete, and the binary tree is flattened into a right next linked list structure.