Answers for "sorted array to bst"

unsorted array to bst

#include<iostream>
using namespace std;
typedef struct node
{
    int value;
    node * pLeft;
    node * pRight;
    node(int val = 0)
    {
        value = val;
        pRight = NULL;
        pLeft = NULL;
    }
}node;
 
void insert(node ** pRoot, int val)
{
    if(*pRoot == NULL)
        *pRoot = new node(val);
    else if((*pRoot)->value <= val)
        insert(&((*pRoot)->pRight), val);
    else if((*pRoot)->value > val)
        insert(&((*pRoot)->pLeft), val);
}
 
node * getBST(int * arr, int size)
{
    node * pRoot = NULL;
    for(int i = 0; i < size; i++)
        insert(&pRoot, arr[i]);
    return pRoot;
}
 
void inOrderTraversal(node * pRoot)
{
    if(pRoot && pRoot->pLeft)
        inOrderTraversal(pRoot->pLeft);
    if(pRoot)
        std::cout<<pRoot->value<<" , ";
    if(pRoot && pRoot->pRight)
        inOrderTraversal(pRoot->pRight);
 
}
int main()
{
    int arr[] = {10,5,15,5,6,7,8,89};
    node * pRoot = getBST(arr, sizeof(arr)/sizeof(int));
    inOrderTraversal(pRoot);
    std::cout<<std::endl;
    return 0;
}

bst to sorted array

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Node of the binary tree
struct node {
    int data;
    node* left;
    node* right;
    node(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};
 
// Function to print flattened
// binary Tree
void print(node* parent)
{
    node* curr = parent;
    while (curr != NULL)
        cout << curr->data << " ", curr = curr->right;
}
 
// Function to perform in-order traversal
// recursively
void inorder(node* curr, node*& prev)
{
    // Base case
    if (curr == NULL)
        return;
    inorder(curr->left, prev);
    prev->left = NULL;
    prev->right = curr;
    prev = curr;
    inorder(curr->right, prev);
}
 
// Function to flatten binary tree using
// level order traversal
node* flatten(node* parent)
{
    // Dummy node
    node* dummy = new node(-1);
 
    // Pointer to previous element
    node* prev = dummy;
 
    // Calling in-order traversal
    inorder(parent, prev);
 
    prev->left = NULL;
    prev->right = NULL;
    node* ret = dummy->right;
 
    // Delete dummy node
    delete dummy;
    return ret;
}
 
// Driver code
int main()
{
    node* root = new node(5);
    root->left = new node(3);
    root->right = new node(7);
    root->left->left = new node(2);
    root->left->right = new node(4);
    root->right->left = new node(6);
    root->right->right = new node(8);
 
    // Calling required function
    print(flatten(root));
 
    return 0;
}