Recursive binary tree and leaf sum

Question

Friends I’m having trouble solving this exercise, and I don’t know how else to do it. I even implemented the tree with recursiveness, but I couldn’t leave the NODE empty and some leaves with number, according to the exercise. Then I need to add up the items that are on the leaves.

In java.

public class No {

    public int valor;
    public No direito;
    public No esquerdo;

    public No(int valor) {
        this.valor = valor;
    }
}

Arvorebinaria.java

public class ArvoreBinaria {

    private No raiz;

    public void inserir(int valor) {
        if (raiz == null) {
            raiz = new No(valor);
        } else {
            No novo = new No(valor);
            inserir(raiz, novo);

        }

    }

    private void inserir(No arvore, No novo) {
        if (novo.valor > arvore.valor) {
            if (arvore.direito == null) {
                arvore.direito = novo;
            } else {
                inserir(arvore.direito, novo);
            }
        } else {
            if (arvore.esquerdo == null) {
                arvore.esquerdo = novo;
            } else {
                inserir(arvore.esquerdo, novo);
            }
        }
    }

EXERCISE

- Uma árvore tem nós;
- Um nó pode ou não ter outros nós;
- Um nó, não folha, tem sempre um nó do lado direito e outro do lado esquerdo
- As folhas não tem nós abaixo;
- As folhas têm associado um número inteiro

The following figure represents 3 instances of binary trees

It is intended to implement an algorithm in Java that allows the construction of an instance of this type. You must have a method that returns the sum of the tree, that is the sum of the leaves.

Tips:

• A knot, not a leaf, always has a left knot and a right knot
• After constructing a node, it will be possible to add other nodes
• Recursiveness
• Do not use Java complex type (HashMaps, Lists and etc)

Answer 1

Here’s your binary tree class. I added in the class No and in class ArvoreBinaria the methods soma(). I also put the toString() to show the tree structure.

class ArvoreBinaria {

    private No raiz;

    public void inserir(int valor) {
        if (raiz == null) {
            raiz = new No(valor);
        } else {
            No novo = new No(valor);
            inserir(raiz, novo);
        }
    }

    private void inserir(No arvore, No novo) {
        if (novo.valor > arvore.valor) {
            if (arvore.direito == null) {
                arvore.direito = novo;
            } else {
                inserir(arvore.direito, novo);
            }
        } else {
            if (arvore.esquerdo == null) {
                arvore.esquerdo = novo;
            } else {
                inserir(arvore.esquerdo, novo);
            }
        }
    }

    public int soma() {
        return raiz == null ? 0 : raiz.soma();
    }

    @Override
    public String toString() {
        return raiz == null ? "*" : raiz.toString();
    }

    private static class No {

        private int valor;
        private No direito;
        private No esquerdo;

        public No(int valor) {
            this.valor = valor;
        }

        public int soma() {
            return valor
                    + (direito == null ? 0 : direito.soma())
                    + (esquerdo == null ? 0 : esquerdo.soma());
        }

        @Override
        public String toString() {
            return (esquerdo == null ? "*" : "(" + esquerdo + ")")
                    + valor
                    + (direito == null ? "*" : "(" + direito + ")");
        }
    }
}

Here’s a test class:

class Teste {
    public static void main(String[] args) {
        ArvoreBinaria ab = new ArvoreBinaria();
        System.out.println(ab);
        ab.inserir(5);
        System.out.println(ab);
        ab.inserir(10);
        System.out.println(ab);
        ab.inserir(15);
        System.out.println(ab);
        ab.inserir(2);
        System.out.println(ab);
        ab.inserir(4);
        System.out.println(ab);
        ab.inserir(6);
        System.out.println(ab);
        ab.inserir(8);
        System.out.println(ab);
        ab.inserir(20);
        System.out.println(ab);
        System.out.println(ab.soma());
    }
}

Here’s the way out:

*
*5*
*5(*10*)
*5(*10(*15*))
(*2*)5(*10(*15*))
(*2(*4*))5(*10(*15*))
(*2(*4*))5((*6*)10(*15*))
(*2(*4*))5((*6(*8*))10(*15*))
(*2(*4*))5((*6(*8*))10(*15(*20*)))
70

Note from the output that the tree is being mounted as expected and that the sum is also correct.

See here working on ideone.