DSA-PROBLEMS/Flatten_binary_tree_to_linked_list.cpp at main · Harsh1118/DSA-PROBLEMS · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/*
Given the root of a binary tree, flatten the tree into a "Linked list":

The "linked list" should use the same Node class where the right child pointer points to the next node in the list and the left child
 pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Examples:

Input:
          1
        /   \
       2     5
      / \     \
     3   4     6
Output : 1 2 3 4 5 6

Explanation: After flattening, the tree looks like this -
     1
      \
       2
        \
         3
          \
           4
            \
             5
              \
               6
Here, left of each node points to NULL and right contains the next node in preorder.The inorder traversal of this flattened tree is 1 2 3 4 5 6.

Input :
        1
       / \
      3   4
         /
        2
         \
          5
Output :
1 3 4 2 5
Explanation : After flattening, the tree looks like this -
     1
      \
       3
        \
         4
          \
           2
            \
             5
Here, left of each node points to NULL and right contains the next node in preorder.The inorder traversal of this flattened tree is 1 3 4 2 5.
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)

Constraints :
1<= number of nodes in binary tree <= 105
1<= data of nodes <= 105
*/
#include<iostream>
using namespace std;

class Node
{
    public:
    int data;
    Node *left , *right;

    Node(int val)
    {
        data = val;
        left = right = NULL;
    }
};

class Solution {
  public:
    void flatten(Node *root) {
        // code here
        while(root)
        {
            if(!root->left)
            {
                root=root->right;
            }
            else
            {
                Node *curr = root->left;
                while(curr->right)
                {
                    curr=curr->right;
                }
                curr->right = root->right;
                root->right = root->left;
                root->left = NULL;
                root = root->right;
            }
        }
    }
};