(93). 27.13. FLATTEN A BINARY TREE - anishsingh90/Data_Structure_And_Algorithm_In_Cpp_github.io GitHub Wiki

//FLATTEN A BINARY TREE(Binary into Linked List)

#include <bits/stdc++.h> using namespace std;

struct Node{ int data; struct Node* left; struct Node* right;

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

};

//flatten void flatten(Node* root){ if(root == NULL || (root->left == NULL && root->right == NULL)){ return; }

if(root->left != NULL){
	flatten(root->left);
	
	Node* temp = root->right;
	root->right = root->left;
	root->left = NULL;
	
	Node* t = root->right;
	while(t->right != NULL){
		t = t->right;
	}
	t->right = temp;
}
flatten(root->right);

}

//inorderPrint void inorderPrint(Node* root){ if(root == NULL){ return; } inorderPrint(root->left); cout << root->data <<" "; inorderPrint(root->right); }

int main(){

Node* root = new Node(4);
root->left = new Node(9);
root->right = new Node(5);

root->left->left = new Node(1); root->left->right = new Node(3); root->right->left = new Node(6);

cout << "Flatten is: "; flatten(root); inorderPrint(root); cout << endl;

return 0;

}

/* OUTPUT: Flatten is: 4 9 1 3 5 6 */