/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

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

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

};

struct Node* newNode(int val){
    struct Node* temp = new Node;
    temp->data = val;
    temp->left = NULL;
    temp->right = NULL;
}

Node* insert(Node* node , int val){
    if(node == NULL){
        return newNode(val);
    }
    if(val<node->data){
        node->left = insert(node->left , val);
    }
    else if(val>node->data){
        node->right = insert(node->right , val);
    }
    return node;
}


void ExternalNodes(Node* root ){

    if(root==NULL){
        return;
    }
    if(root->left==NULL&& root->right == NULL){
        cout<<root->data<<" ";
    }

    ExternalNodes(root->left );
    ExternalNodes(root->right );

}


void InternalNodes(Node* root ){

    if(root==NULL){
        return;
    }
    if(root->left!=NULL || root->right != NULL){
        cout<<root->data<<" ";
    }

    InternalNodes(root->left );
    InternalNodes(root->right );

}

int height(Node* root){
    if(root==NULL){
        return 0;
    }
    return 1+ max(height(root->left),height(root->right));
}

void Tree(int a[] , int n){
    struct Node* root = NULL;
    root = insert(root,a[0]);
    for(int i=1 ; i<n;i++){
        root = insert(root,a[i]);
    }
    int b[n] ;
    cout<<"External Nodes"<<endl;
    ExternalNodes(root);

    cout<<"\nInterrnal Nodes"<<endl;
    InternalNodes(root );

    cout<<"\nHeight of Tree"<<endl;
    cout<<height(root);


}


int main(){
    int n;
    cout<<"Enter the number of elements: ";
    cin>>n;
    int a[n];
    cout<<"Enter the elements: "<<endl;
    for(int i=0 ; i<n;i++){
        cin>>a[i];
    }
    Tree(a,n);


}