#include<bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node*left;
Node*right;
};
Node* construct_recursive(int* arr,int n,int index){
if(index == n){
return NULL;
}
int value = arr[index];
if(value == -1){
return NULL;
}
//Node creation
Node* root = new Node();
root->data = value;
//left Tree construction(recursive faith)
Node* left = construct_recursive(arr,n, index+1);
//right tree construction(recursive faith)
Node*right = construct_recursive(arr, n,index+1);
root->left = left;
root->right = right;
return root;
}
class Pair{
public:
int state;
Node*node;
};
Node* construct(int*arr, int n){
Node*root = new Node();
root->data = arr[0];
Pair rootPair;
rootPair.state = 1;
rootPair.node = root;
stack<Pair> s;
s.push(rootPair);
int i = 1;
while(!s.empty()){
Pair* topPair = &s.top();
if(topPair->state == 1){
//push left child
if(arr[i]!=-1){
Node*leftChild = new Node();
leftChild->data = arr[i];
topPair->node->left = leftChild;
Pair leftChildPair;
leftChildPair.state = 1;
leftChildPair.node = leftChild;
s.push(leftChildPair);
}
i++;
topPair->state++;
}
else if(topPair->state == 2){
if(arr[i]!=-1){
Node*rightChild = new Node();
rightChild->data = arr[i];
topPair->node->right = rightChild;
Pair rightChildPair;
rightChildPair.state = 1;
rightChildPair.node = rightChild;
s.push(rightChildPair);
}
i++;
topPair->state++;
}
else if(topPair->state == 3){
s.pop();
}
}
return root;
}
void display(Node*root){
if(root == NULL){
return;
}
// if(root == NULL){
// return;
// }
// if(root->left!=NULL){
// cout<<root->left->data<<"<----"<<root->data;
// }
// else{
// cout<<-1<<"<----"<<root->data;
// }
// if(root->right!=NULL){
// cout<<"---->"<<root->right->data<<endl;
// }
// else{
// cout<<"---->"<<-1<<endl;
// }
// -----!!!better way to write above code!!!------
string rt = "<----" + to_string(root->data) + "---->";
string left = root->left==NULL?"-1":to_string(root->left->data);
string right = root->right==NULL?"-1":to_string(root->right->data);
cout<<left<<rt<<right<<endl;
display(root->left);
display(root->right);
}
string tree2str(Node* root) {
if(root == NULL){
return "$";
}
string ls = tree2str(root->left);
string rs = tree2str(root->right);
string leftNew = ls != "$"?"("+ls+")":"";
string rightNew = rs != "$"?"("+rs+")":"";
string completeString = to_string(root->data)+leftNew + rightNew;
return completeString;
}
int main(){
//taking array as input
int n;
cin>>n;
int* arr = new int[n];
for(int i = 0;i<n;i++){
cin>>arr[i];
}
// Node* root = construct_recursive(arr,n,0);
Node*root = construct(arr, n);
display(root);
string s= tree2str(root);
cout<<s<<endl;
} Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}