Traverse all possible path from root to leaves and Display all nodes

Problem:- Display all nodes from root to leaves, consider all possible paths.
Output for above Binary tree:- 12-23-11-56, 12-23-11-78, etc

public static void pathFromtRootToleafs(Node root, Vector<Integer> vector,
   int index) {
  if (root == null)
   return;
  vector.insertElementAt(root.getData(), index);
  index++;
  pathFromtRootToleafs(root.getLeftChild(), vector, index);
  pathFromtRootToleafs(root.getRightChild(), vector, index);
  if (root.getLeftChild() == null && root.getRightChild() == null) {
   
   displayNodes(vector, index);System.out.println("");
  }
 }
Here we are doing pre-order traversal and storing nodes values in a vector till we reach leaf (left and right node are null). Once we reach at leaf node, we call display method with index value to display all nodes.

Complete Sample program:- 

package com.devinline.trees;
import java.util.Vector;

public class AllPathsFromRootToLeafs {

 /**
  * To display all nodes from root to leaf - consider all possible paths
  */
 public static void main(String[] args) {
  Vector<Integer> vector = new Vector<>();
  BinaryTree bt = new BinaryTree();
  Node root = bt.createTree();
  pathFromtRootToleafs(root, vector, 0);
 }

 public static void pathFromtRootToleafs(Node root, Vector<Integer> vector,
   int index) {
  if (root == null)
   return;
  vector.insertElementAt(root.getData(), index);
  index++;
  pathFromtRootToleafs(root.getLeftChild(), vector, index);
  pathFromtRootToleafs(root.getRightChild(), vector, index);
  if (root.getLeftChild() == null && root.getRightChild() == null) {
   
   displayNodes(vector, index);System.out.println("");
  }
 }

 private static void displayNodes(Vector<Integer> vector, int index) {
  for (int i = 0; i < index; i++) {
   System.out.print(vector.get(i) + " ");
  }
 }
}
class BinaryTree {
 Node root;

 public BinaryTree() {
  root = null;
 }
 public Node createTree() {
  if (root == null) {
   root = new Node(12);
  }
  root.setLeftChild(new Node(23));
  root.setRightChild(new Node(18));
  root.getLeftChild().setLeftChild(new Node(11));
  root.getLeftChild().setRightChild(new Node(43));
  root.getRightChild().setLeftChild(new Node(12));
  root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
  root.getLeftChild().getLeftChild().setRightChild(new Node(78));
  root.getRightChild().getLeftChild().setRightChild(new Node(98));
  root.getRightChild().setRightChild(new Node(99));
  return root;
 } 
}

class Node {

 private int data;
 private Node leftChild;
 private Node rightChild;

 public Node(int data) {
  this.data = data;
  leftChild = null;
  rightChild = null;
 }

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

 public Node getLeftChild() {
  return leftChild;
 }

 public void setLeftChild(Node leftChild) {
  this.leftChild = leftChild;
 }

 public Node getRightChild() {
  return rightChild;
 }

 public void setRightChild(Node rightChild) {
  this.rightChild = rightChild;
 }

}

Sample output:
-
12 23 11 56
12 23 11 78
12 23 43
12 18 12 98
12 18 99

2 Comments

Previous Post Next Post