Code From Class 2026/04/20

#include<iostream>
struct TN{ //Tree node
public:
    long c; // content
    TN* aL; // address of the left child
    TN* aR; // address of the right child
};
void dfs(TN* aRoot){// Depth-first search
    if(aRoot==nullptr){return;}
    dfs(aRoot->aL);
    std::cout<<aRoot->c<<" ";
    dfs(aRoot->aR);
}
void freeTheMemory(TN* aRoot){
    if(aRoot==nullptr){return;}
    freeTheMemory(aRoot->aL);
    freeTheMemory(aRoot->aR);
    delete aRoot;
}
TN* insert(TN* aOldRoot, long x){
    if(aOldRoot==nullptr){
        TN* aNewRoot=new TN;
        aNewRoot->c=x;
        aNewRoot->aL=nullptr;
        aNewRoot->aR=nullptr;
        return aNewRoot;
    }
    if(x<aOldRoot->c){
        aOldRoot->aL=insert(aOldRoot->aL,x);
    }
    else{
        if(aOldRoot->c<x){
            aOldRoot->aR=insert(aOldRoot->aR,x);
        }
    }
    return aOldRoot;
}
TN* find(TN* aRoot, long x){
    if(aRoot==nullptr){return nullptr;}
    if(x<(aRoot->c)){return find(aRoot->aL,x);}
    if((aRoot->c)<x){return find(aRoot->aR,x);}
    return aRoot;
}
int mainProblems123(){
    TN* a100; TN* a500; TN* a700; TN* a1000;
    TN* a2000; TN* a5000; TN* a3000; TN* a7;
    a100=new TN; a500=new TN; a700=new TN; a1000=new TN;
    a2000=new TN; a5000=new TN; a3000=new TN; a7=new TN;
    a100->c=100; a500->c=500; a700->c=700; a1000->c=1000;
    a2000->c=2000; a5000->c=5000; a3000->c=3000; a7->c=7;
    a100->aL=a500; a100->aR=a700; a500->aL=a1000; a500->aR=nullptr;
    a700->aL=a2000; a700->aR=a5000; a2000->aL=a3000; a2000->aR=a7;
    a5000->aL=nullptr; a5000->aR=nullptr; a3000->aL=nullptr;
    a3000->aR=nullptr; a7->aL=nullptr; a7->aR=nullptr;
    dfs(a100);
    std::cout<<"\n";
    freeTheMemory(a100);
    return 0;
}
int main(){
    TN* aRoot=nullptr;
    long x;
    std::cin>>x;
    while(x>-1){
        aRoot=insert(aRoot,x);
        std::cin>>x;
    }
    dfs(aRoot);
    std::cout<<"\n";
    std::cout<<"Searching. Insert x repeatedly for search.\n";
    std::cout<<"Insert a negative number to exit.\n";
    std::cin>>x;
    while(x>-1){
        if(find(aRoot,x)==nullptr){
            std::cout<<"Not found\n";
        }
        else{
            std::cout<<"Found!!!\n";
        }
        std::cin>>x;
    }
    freeTheMemory(aRoot);
    return 0;
}