Left View of Binary Search Tree [New approach]

left_view_BST.cpp

/*
Problems:
https://practice.geeksforgeeks.org/problems/left-view-of-binary-tree/1
*/

/*
SAMPLE INPUT
1
8
5 4 7 1 2 8 9 10

EXPECTED OUTPUT
left view = 5 4 1 2 10
*/

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

int N;
int height;
int ans[1022];
map < int, int > store_height;

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

struct Node *root;

Node* Insert_Node(Node *root, int x) {
    if (root == NULL) {
        Node *temp = new Node;
        temp->data = x;
        temp->right = NULL;
        temp->left = NULL;
        root = temp;
    } else if (x > root->data) root->right = Insert_Node(root->right, x);
    else if (x <= root->data) root->left = Insert_Node(root->left, x);
    
    return root;
}

void print_tree(Node *root) {
    if (root) {
        cout << root->data << " ";
        print_tree(root->left);
        print_tree(root->right);
    }
}

void cal_height(Node *root, int H) {
    if (root) {
        H++;
        
        height = max(H, height);
        
        if (ans[H] == 0) {
            ans[H] = root->data;
        }
        
        store_height[root->data] = H;
        cal_height(root->left, H);
        cal_height(root->right, H);
    }
}

void solve() {
    cin >> N;
    
    root = NULL;
    
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        
        root = Insert_Node(root, x);
    }
    
    print_tree(root); cout << endl;
    
    height = 0;
    cal_height(root, height);
    
    for (auto X: store_height) {
        cout << X.first << " " << X.second << endl;
    }
    
    cout << height << endl;
    
    cout << "left view = ";
    for (int i = 1; i <= height; i++) {
        cout << ans[i] << " ";
    }
    
    cout << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}