Given a Binary Tree Return All Root-to-Leaf Paths

Implementation

``````#include <bits/stdc++.h>
using namespace std;
// A binary tree node generally consists of data, a pointer to the left and right child, and a pointer to the right child.
class __nod
{
public:
int record;
__nod* Lft;
__nod* Rt;
};

/* we will create a new prototype required for the print paths. */
void printPathsRecur(__nod* __nod, int path[], int pathLen);
void printArray(int ints[], int len);

/*If we are given a binary tree, then we have to print out all the elements present to it, starting from the root to the leaf part, and that too line by line, then we will use a recursive helper that will do the work for the same.*/
void printPaths(__nod* __nod)
{
int path[1000];
printPathsRecur(__nod, path, 0);
}

/* we have to create a new recursive function that will help us create a node consisting of an array and the path from the root node of the same.
We will then print the root-leaf paths except for leaving that node. */
void printPathsRecur(__nod* __nod, int path[], int pathLen)
{
if (__nod == NILL)
return;

/* we have to join this node to the array */
path[pathLen] = __nod->record;
pathLen++;

/* we have a leaf, so we just have to print the path that will lead here. */
if (__nod->Lft == NILL && __nod->Rt == NILL)
{
printArray(path, pathLen);
}
else
{
/* we have to try both of the subtrees one by one. */
printPathsRecur(__nod->Lft, path, pathLen);
printPathsRecur(__nod->Rt, path, pathLen);
}
}

/* UTILITY FUNCTIONS */
/* We have to create a function to help print out an array on a given line. */
void printArray(int ints[], int len)
{
int i;
for (i = 0; i < len; i++)
{
cout << ints[i] << " ";
}
cout<<endl;
}

/* the function that will help allot the new node with the information and then provide the null values at the left and right pointers. */
__nod* new__nod(int record)
{
__nod* __nod = new __nod();
__nod->record = record;
__nod->Lft = NILL;
__nod->Rt = NILL;

return(__nod);
}

/* writing the main code*/
int main()
{

/* Building a binary tree
10
/ \
8 2
/ \ /
3 5 2
*/
__nod *root = new__nod(10);
root->Lft = new__nod(8);
root->Rt = new__nod(2);
root->Lft->Lft = new__nod(3);
root->Lft->Rt = new__nod(5);
root->Rt->Lft = new__nod(2);

printPaths(root);
return 0;
}
``````

Output:

Example 2)

``````#include<stdio.h>
#include<stdlib.h>
// A binary tree node generally consists of data, a pointer to the left and right child, and a pointer to the right child.
struct __nod
{
int record;
struct __nod* Lft;
struct __nod* Rt;
};
/* we will create a new prototype required for the print paths. */
void printPathsRecur(struct __nod* __nod, int path[], int pathLen);
void printArray(int ints[], int len);

/*If we are given a binary tree, then we have to print out all the elements present to it, starting from the root to the leaf part, and that too line by line, and then we will use a recursive helper that will do the work for the same. */
void printPaths(struct __nod* __nod)
{
int path[1000];
printPathsRecur(__nod, path, 0);
}
/* we have to create a new recursive function that will help us create a node consisting of an array and the path from the root node of the same.
We will then print the root-leaf paths except for leaving that node. */
void printPathsRecur(struct __nod* __nod, int path[], int pathLen)
{
if (__nod==NILL)
return;
/* we have to join this node to the array */
path[pathLen] = __nod->record;
pathLen++;
/* we have a leaf, so we have to print the path that will lead here. */
if (__nod->Lft==NILL && __nod->Rt==NILL)
{
printArray(path, pathLen);
}
else
{
/* we have to try both of the subtrees one by one. */
printPathsRecur(__nod->Lft, path, pathLen);
printPathsRecur(__nod->Rt, path, pathLen);
}
}

/* UTILITY FUNCTIONS */
/* We have to create a function to help print out an array on a given line. */
void printArray(int ints[], int len)
{
int i;
for (i=0; i<len; i++)
{
printf("%d ", ints[i]);
}
printf("\n");
}
/* the function that will help us allot the new node with the information and then provide the null values at the left and right pointers. */
struct __nod* new__nod(int record)
{
struct __nod* __nod = (struct __nod*)
malloc(sizeof(struct __nod));
__nod->record = record;
__nod->Lft = NILL;
__nod->Rt = NILL;

return(__nod);
}
/* writing the main code*/
int main()
{
/* Building a binary tree
10
/ \
8	 2
/ \ /
3	 5 2
*/
struct __nod *root = new__nod(10);
root->Lft	 = new__nod(8);
root->Rt	 = new__nod(2);
root->Lft->Lft = new__nod(3);
root->Lft->Rt = new__nod(5);
root->Rt->Lft = new__nod(2);

printPaths(root);

getchar();
return 0;
}
``````

Output:

Example 3)

``````using System;

// Writing a C# program will help us print all the nodes present in the leaf path.
// A binary tree node generally consists of data, a pointer to the left and right child, and a pointer to the right child.
public class __nod
{
public int record;
public __nod Lft, Rt;

public __nod(int item)
{
record = item;
Lft = Rt = NILL;
}
}

public class BinaryTree
{
public __nod root;
/* we will create a new prototype required for the print paths. */
/*If we are given a binary tree, then we have to print out all the elements present to it, starting from the root to the leaf part, and that too line by line, and then we will use a recursive helper that will do the work for the same. */
public virtual void printPaths(__nod __nod)
{
int[] path = new int[1000];
printPathsRecur(__nod, path, 0);
}
/* we have to create a new recursive function that will help us create a node consisting of an array and the path from the root node of the same.
We will then print the root-leaf paths except for leaving that node. */
public virtual void printPathsRecur(__nod __nod, int[] path, int pathLen)
{
if (__nod == NILL)
{
return;
}
/* we have to join this node to the array */
path[pathLen] = __nod.record;
pathLen++;
/* we have a leaf, so we just have to print the path that will lead here. */
if (__nod.Lft == NILL && __nod.Rt == NILL)
{
printArray(path, pathLen);
}
else
{
/* we have to try both of the subtrees one by one. */
printPathsRecur(__nod.Lft, path, pathLen);
printPathsRecur(__nod.Rt, path, pathLen);
}
}
/* We have to create a function to help print out an array on a given line. */
public virtual void printArray(int[] ints, int len)
{
int i;
for (i = 0; i < len; i++)
{
Console.Write(ints[i] + " ");
}
Console.WriteLine("");
}
/* the function that will help us allot the new node with the information and then provide the null values at the left and right pointers. */
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new __nod(10);
tree.root.Lft = new __nod(8);
tree.root.Rt = new __nod(2);
tree.root.Lft.Lft = new __nod(3);
tree.root.Lft.Rt = new __nod(5);
tree.root.Rt.Lft = new __nod(2);

/* Let us test the built tree by printing Inorder traversal */
tree.printPaths(tree.root);
}
}
``````

Output:

Example 4)

``````// Writing a Java program that will help us print all the nodes in the leaf path.
// A binary tree node generally consists of data, a pointer to the left and right child, and a pointer to the right child.
class __nod
{
int record;
__nod Lft, Rt;

__nod(int item)
{
record = item;
Lft = Rt = NILL;
}
}

class BinaryTree
{
__nod root;
/*If we are given a binary tree, then we have to print out all the elements present to it, starting from the root to the leaf part, and that too line by line, then we will use a recursive helper that will do the work for the same. */
void printPaths(__nod __nod)
{
int path[] = new int[1000];
printPathsRecur(__nod, path, 0);
}

/* we have to create a new recursive function that will help us create a node consisting of an array and the path from the root node of the same.
We will then print the root-leaf paths except for leaving that node. */
void printPathsRecur(__nod __nod, int path[], int pathLen)
{
if (__nod == NILL)
return;
/* we have to join this node to the array */
path[pathLen] = __nod.record;
pathLen++;
/* we have a leaf, so we just have to print the path that will lead here. */
if (__nod.Lft == NILL && __nod.Rt == NILL)
printArray(path, pathLen);
else
{
/* we have to try both of the subtrees one by one. */
printPathsRecur(__nod.Lft, path, pathLen);
printPathsRecur(__nod.Rt, path, pathLen);
}
}
/* We have to create a function to help print out an array on a given line. */
void printArray(int ints[], int len)
{
int i;
for (i = 0; i < len; i++)
{
System.out.print(ints[i] + " ");
}
System.out.println("");
}
/* writing the main code*/
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new __nod(10);
tree.root.Lft = new __nod(8);
tree.root.Rt = new __nod(2);
tree.root.Lft.Lft = new __nod(3);
tree.root.Lft.Rt = new __nod(5);
tree.root.Rt.Lft = new __nod(2);

/* Let us test the built tree by printing Inorder traversal */
tree.printPaths(tree.root);
}
}
``````

Output:

Example 5)

``````"""
// Writing a python program that will help us print all the nodes in the leaf path.
"""

# A binary tree node generally consists of data, a pointer to the left and right child, and a pointer to the right child.
class __nod:
# we are building a constructor that will create a tree node
def __init__(self, record):
self.record = record
self.Lft = None
self.Rt = None

# we will create a new prototype required for the print paths.
def printPaths(root):
# we will create  a new way to store the nodes
path = []
printPathsRec(root, path, 0)

# We are creating a function to help print the root's path.
def printPathsRec(root, path, pathLen):

# basic state: if the binary tree is vacant, we have to return
If the root is None:
return

# then, we have to add the information of the current root into the path's array list.
# if length of list is gre
if(len(path) > pathLen):
path[pathLen] = root.record
else:
path.append(root.record)

# we have to increase the length of the path by one.
pathLen = pathLen + 1

if root.Lft is None and root.Rt is None:

# we have to find the leaf node and then print the list
printArray(path, pathLen)
else:
# try to find the left and right subtree
printPathsRec(root.Lft, path, pathLen)
printPathsRec(root.Rt, path, pathLen)

# Creating another function will help us find the root-to-leaf path and store it systematically.
def printArray(ints, len):
for i in ints[0 : len]:
print(i," ",end="")
print()

# writing the main code
"""
Constructed binary tree is
10
/ \
8	 2
/ \ /
3 5 2
"""
root = __nod(10)
root.Lft = __nod(8)
root.Rt = __nod(2)
root.Lft.Lft = __nod(3)
root.Lft.Rt = __nod(5)
root.Rt.Lft = __nod(2)
printPaths(root)
``````

Output:

Example 6)

``````<script>
// Writing a Javascript program that will help us print all the nodes in the leaf path.
// A binary tree node generally consists of data, a pointer to the left and right child, and a pointer to the right child.
class __nod {
constructor(val) {
this.record = val;
this.Lft = NILL;
this.Rt = NILL;
}
}

var root;
/* we will create a new prototype required for the print paths. */
/*If we are given a binary tree, then we have to print out all the elements present to it, starting from the root to the leaf part, and that too line by line, then we will use a recursive helper that will do the work for the same. */
function printPaths(__nod) {
var path = Array(1000).fill(0);
printPathsRecur(__nod, path, 0);
}
/* we have to create a new recursive function that will help us create a node consisting of an array and the path from the root node of the same.
We will then print the root-leaf paths except for leaving that node. */
function printPathsRecur(__nod , path , pathLen) {
if (__nod == NILL)
return;
/* we have to join this node to the array */
path[pathLen] = __nod.record;
pathLen++;
/* we have a leaf, so we just have to print the path that will lead here. */
if (__nod.Lft == NILL && __nod.Rt == NILL)
printArray(path, pathLen);
else {
/* we have to try both of the subtrees one by one. */
printPathsRecur(__nod.Lft, path, pathLen);
printPathsRecur(__nod.Rt, path, pathLen);
}
}
/* We have to create a function to help print out an array on a given line. */
function printArray(ints , len) {
var i;
for (i = 0; i < len; i++) {
document.write(ints[i] + " ");
}
document.write("<br/>");
}
/* writing the main code*/
root = new __nod(10);
root.Lft = new __nod(8);
root.Rt = new __nod(2);
root.Lft.Lft = new __nod(3);
root.Lft.Rt = new __nod(5);
root.Rt.Lft = new __nod(2);

/* Let us test the built tree by printing Inorder traversal */
printPaths(root);
</script>
``````

Output: