#include <stdio.h>
#include <stdlib.h>

// Definição da estrutura para um nó da árvore
struct No {
    int dado;
    struct No* esq;
    struct No* dir;
};

// Função para criar um novo nó
struct No* novoNo(int dado) {
    struct No* No = (struct No*)malloc(sizeof(struct No));
    No->dado = dado;
    No->esq = NULL;
    No->dir = NULL;
    return No;
}

// Função para inserir de forma binária (apenas para construir a árvore, não é otimizada)
struct No* inserir(struct No* No, int dado) {
    if (No == NULL) return novoNo(dado);
    if (dado < No->dado)
        No->esq = inserir(No->esq, dado);
    else
        No->dir = inserir(No->dir, dado);
    return No;
}

// Função para buscar um valor na árvore
int buscar(struct No* raiz, int valor) {
    // Caso especial: raiz é nula ou o valor está na raiz
    if (raiz == NULL) return 0;
    if (raiz->dado == valor) return 1;

    // O valor é maior que o dado na raiz
    if (raiz->dado < valor) return buscar(raiz->dir, valor);

    return buscar(raiz->esq, valor);
}

// Função principal para demonstração
int main() {
    struct No* raiz = NULL;
    raiz = inserir(raiz, 50);
    inserir(raiz, 30);
    inserir(raiz, 20);
    inserir(raiz, 40);
    inserir(raiz, 70);
    inserir(raiz, 60);
    inserir(raiz, 80);

    int valor = 70;
    if(buscar(raiz, valor))
        printf("Encontrado o valor %d na árvore.\n", valor);
    else
        printf("Valor %d não encontrado na árvore.\n", valor);

    return 0;
}