Print all leaves of a Binary tree

In one of the previous posts, we covered the Tree data structure and a Binary tree.

Now, we need to print all the leaves of a Binary tree.

The leaf node is a node that has no children - both the right and left child is null.

Let's say we have the following tree:

Now, let's create a BinaryTree class and construct the tree by adding the nodes:

class BinaryTree {
  Node root;

  public void createBinaryTree() {
    Node first = new Node(1);
    Node second = new Node(2);
    Node third = new Node(3);
    Node fourth = new Node(4);
    Node fifth = new Node(5);
    Node sixth = new Node(6);
    Node seventh = new Node(7);

    root = first;
    first.left = second;
    first.right = third;
    second.left = fourth;
    second.right = fifth;
    third.left = sixth;
    third.right = seventh;
  }

}

class Node {
  Node left;
  Node right;
  int value;

  public Node(int data) {
    this.value = data;
  }
}

The tree is the same as on the picture.

Print all leaf nodes of a Binary tree - solution

To find and print all leaf nodes we need to traverse the tree, and there are two ways to do that:
Breadth-first search (BFS) and Depth-First Search (DFS).

Both BFS and DFS have their own ways of traversing the tree:

Breadth-First Search:

• Level Order Traversal

 Depth-First Search:

• Preorder Traversal
• Inorder Traversal
• Postorder Traversal
  

Basically, we can use whatever method from the above list to traverse the tree and print the leaf nodes.

Method for finding the leaf nodes:

void printLeafNodes(Node root) {
    if (root == null) {
        return;
    }

    if (isLeaf(root)) {
        System.out.print(root.value + " ");
    }

    printLeafNodes(root.left);
    printLeafNodes(root.right);
}

boolean isLeaf(Node node) {
    return node.left == null && node.right == null;
}

Here, we implemented a recursive method printLeafNodes that traverses the tree in a Preorder fashion and when we determine that the node does not have any children (isLeaf method), we print it.

And that is how to print/find all leaf nodes of a Binary tree.