To print the leaves and return number of leaves in a tree

Question

I am writing a recursive method in Java trying to print all the leaves and return the number of leaves of a binary tree. Here is my code:

public int printAndCountLeaves(Node nd)
{
    int size = 0;
    Node left = nd.getLeft();
    Node right = nd.getRight();
    if(left != null && right != null)
        {
            size = size + printAndCountLeaves(left);
            size = size + printAndCountLeaves(right);
        }
        else
        {
            System.out.println(data);
            return (size + 1);
        }

    return size;

}

And here is the Node Class:

public class Node
{
    double data;
    Node left;//left child
    Node right;//right child
    Node parent;
    //Assume proper constructors and getters
}

Would my code work for printing all the leaves and returning the number of leaves of a complete binary tree?

Answer 1

You would definitely need to add 1 to count each time you make the recursive call not just when its child nodes are null. Also you may want to do some error checking for instance if the tree you send your method is empty. Also print the node each time in the if statement the way you have it now it will only print the nodes at the bottom.

size++;
size += printAndCountLeaves(left) + printAndCountLeaves(right);

Answer 2

I guess this could be easier recursive method to print/count only leaf nodes of a binary tree. We can generalize this for any tree.

class Node {
    int key;
    Node left, right;

    public Node() {}

    public Node(int key) {
        this.key = key;
    }
}

// Consider this is global
List<Integer> list = new ArrayList<>();

void findLeaves(Node node) {
    if (null == node) return;

    findLeaves(node.left);

    if (null == node.left && null == node.right) list.add(node.key);

    findLeaves(node.right);
}