forked from Pheonix-001/Hacktoberfest_2022
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Flatten Binary Tree to Linked List
54 lines (51 loc) · 1.06 KB
/
Flatten Binary Tree to Linked List
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
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
Node *left, *right;
};
Node* newNode(int key)
{
Node* node = new Node;
node->key = key;
node->left = node->right = NULL;
return (node);
}
void flatten(struct Node* root)
{
if (root == NULL || root->left == NULL && root->right == NULL)
return;
if (root->left != NULL) {
flatten(root->left);
struct Node* tmpRight = root->right;
root->right = root->left;
root->left = NULL;
struct Node* t = root->right;
while (t->right != NULL)
t = t->right;
t->right = tmpRight;
}
flatten(root->right);
}
void inorder(struct Node* root)
{
if (root == NULL)
return;
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
int main()
{
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->right->right = newNode(6);
flatten(root);
cout << "The Inorder traversal after flattening binary tree ";
inorder(root);
return 0;
}
// This code is contributed by Sahil Sharma (sahilsharma029)