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

Cycle sort

Cycle sort is an examination arranging calculation which powers exhibit to be figured into the quantity of cycles where every one of them can be pivoted to create an arranged...

5 minutes read.

Balanced Binary Tree

A balanced binary tree is just a random nod-based tree with a rule of keeping its height minimum in size to maintain various operations such as insertions, deletions and several...

3 minutes read.

Application of 2D array - Sparse Matrix

2D Arrays Application - Sparse Matrix A matrix is a two-dimensional data item consisting of m rows and n columns, with a total of m x n values. A sparse matrix...

7 minutes read.

Box Stacking Problem

Stacking of boxes depending on their base You have been given n different boxes. These boxes will have different heights, widths, and depths. You have to stack all these boxes in...

4 minutes read.

Perfect Binary Tree

Complete binary trees are an important and general topic in the concept – of tree data structures. Before discussing a complete binary tree, we need to know the concept of...

4 minutes read.

Counting Sort

Counting Sort: Counting sort is a sorting algorithm that is used to sort the elements of the array within a specific range. It counts the same element number of the...

3 minutes read.

Burning binary tree

Burn the Binary tree starting from the target node You have given a binary tree and a target node value. Now you have to burn the tree from target node. You...

4 minutes read.

Sorting Algorithms

Sorting: In the data structure, sorting is the process by which you arrange the data in a logical order. This logical order can also be an ascending order or a...

7 minutes read.

Polish Notation in Data Structures

Arithmetic Expression: An arithmetic expression is defined as several operands or data items combined using several operators. For example; a+b*(c-d) is an expression. Operands: Operands represent the data in an expression...

2 minutes read.

Array vs Linked List: Data Structure

Data structure: Difference Between Array and Linked List What is Array? An array is a linear data structure that can store similar data items for further processing. The similar data items...

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.

Length of longest palindrome in a linked list using O(1) extra space

Length of longest palindrome in a linked list using O(1) extra space In this problem, we need to find the length of the longest palindrome list that is present in given...

2 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.

Common Operations on various Data Structures

Data structures are ways to organise data in computer memory for quick and effective use. The storage of data uses a variety of data-structures. It is also possible to define...

7 minutes read.

Find the fractional (n/kth) node in the linked list

Find the fractional (n/kth) node in the linked list In this problem, we have given a singly linked list and a number k. Here we need to find the (n/k)th element...

2 minutes read.

Given a Binary Tree, Check if it's balanced

Implementation /*Creating a C++ program that will help us identify whether the given tree is height-balanced or not.  */ #include <bits/stdc++.h> using namespace std; /* A particular binary tree node consists of data with some...

4 minutes read.

Applications of Different Linked Lists in Data Structure

What is a Linked list? A linked list is a data structure that consists of a sequence of elements, where each containing a reference or ("link") to the next element in...

5 minutes read.

What Is Graph Data Structure

A graph is generally a set of vertices and edges or border that is mainly used to join these vertices. A graph is basically pictured as a cyclic tree in...

7 minutes read.

Flatten Binary Tree to a linked list

Implementation In this section, we will see the implementation of the binary Tree and its conversion into linked lists. let us proceed: - // Writing a C++ program that will convert a...

4 minutes read.

Comb Sort

Brush sort is a fairly direct orchestrating computation at first arranged by Wlodzimierz Dobosiewicz and Artur Borowy in 1980, later rediscovered (and given the name "Combsort") by Stephen Lacey and...

5 minutes read.