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

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.

root leaf path binary tree — Fig 1: Root to leaf path binary tree

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

S. No.	Root to leaf path	Value
1	A -> B -> D	100->50->25
2	A -> B -> E	100->50->80
3	A -> C -> F	100->150->125
4	A -> C -> G	100->150->160

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.

root leaf path — Fig 2: Root to leaf paths

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

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

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

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

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

1.) Root2Leaf Class:

2.) Node class:

3.) App Class:

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

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

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

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

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

1.) Root2Leaf Class:

2.) Node class:

3.) App Class:

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

You may also like: