This approach involves a recursive pre-order traversal of the tree. The idea is to recursively flatten the left and right subtrees, then append the flattened left subtree between the root and the flattened right subtree.
The steps are as follows:
This leverage the pre-order traversal principle: Root → Left → Right.
Time Complexity: O(n) where n is the number of nodes in the tree since each node is visited once.
Space Complexity: O(n) due to the recursive call stack on an unbalanced tree.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val)
3 this.left = (left===undefined ? null : left)
4 this.right = (right===undefined ? null : right)
5}
6
7var flatten = function(root) {
8 if (!root) return;
9
10 let left = root.left;
11 let right = root.right;
12
13 root.left = null;
14 flatten(left);
15 flatten(right);
16
17 root.right = left;
18 let current = root;
19 while (current.right !== null) {
20 current = current.right;
21 }
22 current.right = right;
23};This JavaScript solution flattens the binary tree recursively. It processes left and right subtrees individually before merging them inline to form the resultant linked list version of the tree.
This approach simplifies the recursive method by using a stack to maintain state information. By using controlled use of stack structures, we can modify the tree iteratively.
The algorithm progresses with these steps:
This achieves similar logic as recursion but without directly using the call stack by using our custom stack for maintaining traversal state.
Time Complexity: O(n) because every node is processed once.
Space Complexity: O(n), matching the worst-case stack usage when all nodes are in a single path.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10struct StackNode {
11 struct TreeNode* node;
12 struct StackNode* next;
13};
14
15void push(struct StackNode** stack, struct TreeNode* node) {
16 struct StackNode* new_node = (struct StackNode*)malloc(sizeof(struct StackNode));
17 new_node->node = node;
18 new_node->next = *stack;
19 *stack = new_node;
20}
21
22struct TreeNode* pop(struct StackNode** stack) {
23 if (!*stack) return NULL;
24 struct StackNode* tmp = *stack;
25 struct TreeNode* node = tmp->node;
26 *stack = tmp->next;
27 free(tmp);
28 return node;
29}
30
31void flatten(struct TreeNode* root) {
32 if (!root) return;
33 struct StackNode* stack = NULL;
34 push(&stack, root);
35
36 while (stack) {
37 struct TreeNode* curr = pop(&stack);
38
39 if (curr->right) {
40 push(&stack, curr->right);
41 }
42 if (curr->left) {
43 push(&stack, curr->left);
44 }
45
46 if (stack) {
47 curr->right = stack->node;
48 }
49 curr->left = NULL;
50 }
51}This C code leverages a custom stack to iteratively implement pre-order traversal. Nodes are processed such that when a node is visited, it pushes its right and left children onto the stack. The list is reordered inline using right field connections.