Logo
×

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:

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

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:

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

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:

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

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:

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

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:

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

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:

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

Related Topics

Lowest common ancestor in a binary search tree

Suppose you have given two values of nodes in a binary search tree. You have to find out the lowest common ancestor between the nodes. Let’s take an example tree- For the...

4 minutes read.

Operations on Queue in Data Structures

A queue is a linear structure where operations are done in a specific sequence. Queues are abstract data structures that are comparable to Stacks. A queue, unlike a stack, is...

8 minutes read.

Bucket Sort

Bucket Sort: In the sorting algorithm, we create buckets and put elements into them. We can apply some sorting algorithm (insertion sort) to sort the elements in each bucket. Finally,...

4 minutes read.

Deletion in Binary Search Tree

Implementation #include <iostream> using namespace std; struct _nod {   int ky;   struct _nod *Lft, *Rt; }; // Creating a node in the binary tree. struct _nod *nw_nod(int Itm) {   struct _nod *temp = (struct _nod *)malloc(sizeof(struct...

4 minutes read.

Given Two Binary Trees, Check if it is Symmetric

Implementation // creating a C++ program that will help us check whether the two given trees are mirror images of each other.  #include<bits/stdc++.h> using namespace std; /* A given binary tree has a data...

5 minutes read.

FIFO approach

FIFO is first in first out approach. It is done for the list of elements in data structures where first element will be deleted after another element ia added to it Here,...

6 minutes read.

Tree in Data Structure

Tree A tree is a non-linear data structure by which hierarchical data is displayed. As we know that there are many trees in the forest, similarly the data structure also contains...

3 minutes read.

Data Structure Infix to Postfix Conversion

Infix to Postfix Conversion The infix expression is easy to read and write by humans. In present time, we use the infix expression in our daily life but the computers are...

4 minutes read.

What is the difference between Tree and Graph

We usually use a diverse range of data structure to store our data and information. To store them in a more sequential manner and to access them easily, we use...

4 minutes read.

Write Main Difference Between Tree and Graph in Data Structures

Graph: The graph has two sets, which are considered V and E. These vertices are also called nodes, and edges are referred to as arcs connecting any two nodes in a...

4 minutes read.

Threaded Binary Tree

The linked form of binary trees wastes storage capacity because more than half of the connection variables have a Missing value. A binary tree has several nodes. Hence n+1 link fields...

8 minutes read.

Partitioning a linked list around a given value

Partitioning a linked list around a given value In this problem, we are given a linked list and a value k. We need to partition the given linked list so that...

3 minutes read.

Linear vs Non-Linear: Data Structure

What is Linear Data Structure? The data structure is said to be linear if the data elements are arranged linearly or we can say sequentially. In the linear data structure, the...

3 minutes read.

Deletion in B+ Tree

Make a search for the leaf node that containing the key value by taking the value in a key value. If the required key value is found, then it will remove...

6 minutes read.

Does Overloading Work with Inheritance

This is a question that occasionally comes to many programmers. Who are curious to know more now has a complete explanation and a solution through this tutorial! Inheritance: The functions of...

3 minutes read.

Stack vs Heap Memory Allocation Data Structure

Difference Between Stack and Heap Memory Allocation Stack Memory Stack memory allocation is a way to use the system memory as a temporary storage of the data which is act like last-in-first-out...

3 minutes read.

Array Data Structure

Data Structure Array: The array is a non-primitive and linear data structure that is a group of similar data items. That is, it can store only one type of data....

6 minutes read.

Optimal binary search tree in DSA

Implementation // A simple way of the recursive implementation of the optimal search that we will perform on the binary tree.   #include <bits/stdc++.h> using namespace std; // we have to create a basic utility...

8 minutes read.

Binary Tree Uses

A binary tree is a tree data structure containing hubs with at most two children for instance a right and left child. The node at the top is insinuated as the...

3 minutes read.

CSS Text-indent

Text-indent The Text-indent property of CSS is used to set any first line’s indentation inside a text’s block. It describes the horizontal space amount that puts establish before the text line. It...

3 minutes read.