Find All Paths from Root to Leaf Nodes in Binary Tree using Java

In this example I am going to show you how to find all paths from root to leaf nodes in binary tree. So I am going to find each path from root to leaf node using Java program.

A binary tree is a non-linear data structure type tree with at most two children for each parent. Every node in a binary tree has a left and right reference along with data. The type of data can be as per the application’s requirement. The node at the top of the tree hierarchy is called root node. The root node holds child/children nodes or sub-node(s).

A binary tree can be visually represented with the following image:

The above tree has a root node with data or value 2 and has a height 3.

Binary tree is used to implement binary search trees and binary heaps and these are used for searching and sorting.

Prerequisites

Java

Find All Paths from Root to Leaf Nodes

Now I am going to write Java code to find all paths from root node to the leaf node. A node in a binary tree can be represented by the following class:

class Node<E> {

	E data;
	Node<E> left;
	Node<E> right;

	public Node(E data) {
		this.data = data;
	}

}

E is the type of the data you want to use. Node can have left and right references.

Next I am going to print the path from root node to leaf node using recursion.

public static void printPathRootToLeaf(Node<Integer> node, Integer[] path, int len) {
	if (node == null) {
		return;
	}

	path[len] = node.data;
	
	len++;

	if (node.left == null && node.right == null) {
		printArrayElements(path, len);
		return;
	}

	printPathRootToLeaf(node.left, path, len);
	printPathRootToLeaf(node.right, path, len);
}

In the above method I am checking if left and right references of a particular node are null, then leaf node is reached and hence I print the elements from root to the leaf node.

The printArrayElements() method can be defined as follows:

private static void printArrayElements(Integer[] path, int len) {
	String sep = "";
	for (int i = 0; i < len; i++) {
		System.out.print(sep + path[i]);
		sep = " -> ";
	}
	System.out.println();
}

Testing the Program

Finally I create the following nodes in a binary tree and call the method printPathRootToLeaf(). The whole source code can be downloaded from the Source Code section later.

Node<Integer> rootNode = new Node<>(45);
Node<Integer> node20 = new Node<>(25);
Node<Integer> node10 = new Node<>(15);
Node<Integer> node30 = new Node<>(30);
Node<Integer> node60 = new Node<>(60);
Node<Integer> node50 = new Node<>(50);
Node<Integer> node70 = new Node<>(75);
Node<Integer> node5 = new Node<>(5);
Node<Integer> node55 = new Node<>(55);

rootNode.left = node20;
rootNode.right = node60;

node20.left = node10;
node20.right = node30;

node60.left = node50;
node60.right = node70;
node10.left = node5;
node50.right = node55;

printPathRootToLeaf(rootNode, new Integer[10], 0);

Running the above program will give you the following output:

45 -> 25 -> 15 -> 5
45 -> 25 -> 30
45 -> 60 -> 50 -> 55
45 -> 60 -> 75

Source Code

Download

Leave a Comment