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