In this tutorial we will learn how to print Root to Leaf Path of a Binary Search Tree with some examples.
What is Binary Search Tree?
Binary Search Tree is a node-based data structure which has following properties.
- Left subtree nodes always be less than the root node.
- Right subtree nodes always be greater than the root node.
- Left and right subtree is also Binary Search Tree. You can learn more about the Binary Search Tree from Here.
Code To Print Root to leaf Nodes Path
The following code contains also creating a Binary Search Tree. Then the printing path code is written. because we needed to create a Binary Search Tree before printing its leaf path. Recursion is used to print the leaf path. Recursion is the best way used in Data Structure programming.
Explanation:
1. First define a base condition (if node == null).
import java.util.ArrayList;
public class BinaryTreeBT {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// creating binary search tree
public static Node createBST(Node root, int val) {
if (root == null) {
root = new Node(val);
return root;
}
if (root.data > val) {
root.left = createBST(root.left, val);
} else {
root.right = createBST(root.right, val);
}
return root;
}
//print Root to leaf path
public static void printRoot2Leaf(Node root, ArrayList<Integer> path){
if(root == null){
return;
}
path.add(root.data);
if(root.left == null && root.right == null){
printPath(path);
}else{
printRoot2Leaf(root.left, path);
printRoot2Leaf(root.right, path);
}
path.remove(path.size()-1);
}
public static void printPath(ArrayList<Integer> path){
for(int i= 0; i<path.size(); i++){
System.out.print(path.get(i) + "->");
}
System.out.println();
}
public static void main(String[] args) {
int[] values = {12, 8, 10, 1, 3, 4, 6, 9, 15};
Node root = null;
// creating binary search tree
for(int i=0; i<values.length; i++){
root = createBST(root, values[i]);
}
printRoot2Leaf(root, new ArrayList<>());
}
}
Answer: You will get the following result.
12->8->1->3->4->6->
12->8->10->9->
12->15->
Thank you for reaching out this tutorial. You can comment in the comments section below for any doubt or question. You can learn more about it here.
