Print paths from root to leaf nodes in binary tree (Java/ recursive)

• Given a binary tree, we would like to print all possible paths from root to leaf nodes.
  • We will perform preOrder traversal using depth first search recursive algorithm.
• Let us take a quick example to elaborate the problem statement. (refer Fig 1).
  • Binary tree is rooted at node A and having leaf nodes D, E ,F & G.

The root to leaf paths in a binary tree are as follows:

Brief algorithm to print root to leaf paths is as follow:

• Traverse the binary tree using preOrder traversal.
  • Keep on storing node information in an array (while traversing the binary tree).
• When we reach a leaf node, print the root to leaf path.

Algorithm: print root to leaf paths in java (recursive)

• Start the traversal of tree from Root Node
• Push 100 (Node A) to an array.
  • We did not encounter the leaf node
• Start preOrder traversal of Node A’s left subtree.
  • Push 50 (Node B) to an array.
  • Node B is not a leaf node.
  • Traverse left subtree of Node B.
    • Push 25 (Node D) to an array & Node D is a leaf node
    • Print the array and output will 100, 50, 25 (root to leaf path)
      • return from here
  • Traverse right subtree of Node B.
    • Push 80 (Node E) to an array & Node E is a leaf node
    • Print the array and output will 100, 50, 80 (root to leaf path)
      • return from here
• Start preOrder traversal of Node A’s right subtree (Node C)
  • The logical flow will be same as that of left child flow i.e. Node B
  • Traverse left subtree of Node C & output will be 100, 150, 125
  • Traverse right subtree of Node C & output will be 100, 150, 160

Code- print all paths from root to leaf nodes in a binary tree

1.) Root2Leaf  Class:

• Root2Leaf class is responsible for find all paths from root to leaf nodes.
• Traverse the binary tree using depth first search recursive algorithm.
  • We will traverse the binary tree using preOrder traversal.

package org.learn.Question;

import java.util.Arrays;
import org.learn.PrepareTree.Node;

public class Root2Leaf {
	private static int nPath ;
	public static void root2LeafPath(Node root, int[] path) {
		nPath = 0;
		processPath(root, path,0);
	}
	private static void processPath(Node root, int[] path,int index) {
		if(null == root) {
			return;
		}
		path[index++] = root.data;
		if(root.left == null && root.right == null) {
			print(path,index);
			return;
		}
		processPath(root.left,path,index);
		processPath(root.right,path,index);		
		return;
	}
	
	private static void print(int[] path,int index) {
		System.out.printf("Root to Leaf path %d : ",++nPath);
		System.out.println(Arrays.toString(Arrays.copyOf(path,index)));
		return;
	}
}

2.) Node class:

• Node class representing the Nodes of a binary tree

package org.learn.PrepareTree;

public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int num) {
		this.data = num;
		this.left = null;
		this.right = null;
	}

	public Node() {
		this.left = null;
		this.right = null;
	}
}

3.) App Class:

•  We are creating binary tree in main method.
• We are using Root2Leaf class to print all paths from root to leaf nodes.

package org.learn.Client;

import org.learn.Question.Node;
import org.learn.Question.Root2Leaf;

public class App {
	public static void main(String[] args) {
		// root level 0
		Node A = Node.createNode(100);
		// Level 1
		Node B = Node.createNode(50);
		Node C = Node.createNode(150);
		// Level 2
		Node D = Node.createNode(25);
		Node E = Node.createNode(80);
		Node F = Node.createNode(125);
		Node G = Node.createNode(160);

		// connect Level 0 and 1
		A.left = B;
		A.right = C;
		// connect level 1 and level 2
		B.left = D;
		B.right = E;
		C.left = F;
		C.right = G;

		int[] path = new int[512];
		Root2Leaf.root2LeafPath(A, path);
	}
}

Output – root to leaf path in a binary tree (recursive)

Root to Leaf path 1 :  100 50 25
Root to Leaf path 2 :  100 50 80
Root to Leaf path 3 :  100 150 125
Root to Leaf path 4 :  100 150 160

Download code – print root to leaf path binary tree recursive algorithm java