Given a Binary Tree, the task is to print all Root to Leaf path of this tree in Boundary Root to Leaf path traversal.
Boundary Root to Leaf Path Traversal: In this traversal, the first Root to Leaf path(Left boundary) is printed first, followed by the last Root to Leaf path (Right boundary) in Reverse order. Then the process is repeated for the second and second-last Root to Leaf path, till the all Root to Leaf path has been printed.
Examples:
Input:
1
/ \
15 13
/ / \
11 7 29
\ /
2 3
Output: 1 15 11
3 29 13 1
1 13 7 2
Explanation:
First of all print first path from Root to the Leaf
which is 1 15 11
Then, print the last path from the Leaf to Root
which is 3 29 13 1
Then, print the second path from Root to Leaf
which is 1 13 7 2
Input:
7
/ \
23 41
/ \ \
31 16 3
/ \ \ /
2 5 17 11
/
23
Output: 7 23 31 2
11 3 41 7
7 23 31 5
23 17 16 23 7
Approach: In order to print paths in Boundary Root to Leaf Path Traversal,
- We first need to make Preorder Traversal of the binary tree to get the all node values of particular path.
- Here an array is used to store the path of the tree while doing the Preorder traversal then store this path into matrix.
- Then for each path, print the matrix in first row (Left to Right) then last row (Right to Left) and so on.
Below is the implementation of the above approach:
C++
// C++ implementation to print the // path in Boundary Root to Leaf // Path Traversal.#include <bits/stdc++.h>using namespace std;// Structure of tree nodestruct Node { int key; struct Node *left, *right;};// Utility function to// create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp);}// Function to calculate the length// of longest path of the treeint lengthOfLongestPath(struct Node* node){ // Base Case if (node == NULL) return 0; // Recursive call to calculate the length // of longest path int left = lengthOfLongestPath(node->left); int right = lengthOfLongestPath(node->right); return 1 + (left > right ? left : right);}// Function to copy the complete// path in a matrixvoid copyPath(int* path, int index, int** mtrx, int row){ // Loop to copy the path for (int i = 0; i < index; i++) { mtrx[row][i] = path[i]; }}// Function to store all path// one by one in matrixvoid storePath(struct Node* node, int* path, int index, int** mtrx, int& row){ // Base condition if (node == NULL) { return; } // Inserting the current node // into the current path path[index] = node->key; // Recursive call for // the left sub tree storePath(node->left, path, index + 1, mtrx, row); // Recursive call for // the right sub tree storePath(node->right, path, index + 1, mtrx, row); // Condition to check that current // node is a leaf node or not if (node->left == NULL && node->right == NULL) { // Incrementation for changing // row row = row + 1; // Function call for copying // the path copyPath(path, index + 1, mtrx, row); }}// Function to calculate// total pathint totalPath(Node* node){ static int count = 0; if (node == NULL) { return count; } if (node->left == NULL && node->right == NULL) { return count + 1; } count = totalPath(node->left); return totalPath(node->right);}// Function for Clockwise Spiral Traversal// of Binary Treevoid traverse_matrix(int** mtrx, int height, int width){ int j = 0, k1 = 0, k2 = 0; int k3 = height - 1; int k4 = width - 1; for (int round = 0; round < height/2; round++) { for (j = k2; j < width; j++) { // Only print those values which // are not MAX_INTEGER if (mtrx[k1][j] != INT_MAX) { cout << mtrx[k1][j] << " "; } } cout << endl; k2 = 0; k1++; for (j = k4; j >= 0; j--) { // Only print those values which // are not MAX_INTEGER if (mtrx[k3][j] != INT_MAX) { cout << mtrx[k3][j] << " "; } } cout << endl; k4 = width - 1; k3--; } // Condition (one row may be left // traversing) // If number of rows in matrix are odd if (height % 2 != 0) { for (j = k2; j < width; j++) { // Only print those values which are // not MAX_INTEGER if (mtrx[k1][j] != INT_MAX) { cout << mtrx[k1][j] << " "; } } }}// Function to print all the paths// in Boundary Root to Leaf // Path Traversalvoid PrintPath(Node* node){ // Calculate the length of // longest path of the tree int max_len = lengthOfLongestPath(node); // Calculate total path int total_path = totalPath(node); // Array to store path int* path = new int[max_len]; memset(path, 0, sizeof(path)); // Use double pointer to create // 2D array which will contain // all path of the tree int** mtrx = new int*[total_path]; // Initialize width for each row // of matrix for (int i = 0; i < total_path; i++) { mtrx[i] = new int[max_len]; } // Initialize complete matrix with // MAX INTEGER(purpose garbage) for (int i = 0; i < total_path; i++) { for (int j = 0; j < max_len; j++) { mtrx[i][j] = INT_MAX; } } int row = -1; storePath(node, path, 0, mtrx, row); // Print the circular clockwise spiral // traversal of the tree traverse_matrix(mtrx, total_path, max_len); // Release extra memory // allocated for matrix free(mtrx);}// Driver Codeint main(){ /* 10 / \ 13 11 / \ 19 23 / \ / \ 21 29 43 15 / 7 */ // Create Binary Tree as shown Node* root = newNode(10); root->left = newNode(13); root->right = newNode(11); root->right->left = newNode(19); root->right->right = newNode(23); root->right->left->left = newNode(21); root->right->left->right = newNode(29); root->right->right->left = newNode(43); root->right->right->right = newNode(15); root->right->right->right->left = newNode(7); // Function Call PrintPath(root); return 0;} |
Java
// Java implementation to print the // path in Boundary Root to Leaf // Path Traversal. import java.util.*;class GFG{static int row;static int count = 0;// Structure of tree nodestatic class Node { int key; Node left, right;};// Utility function to// create a new nodestatic Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);}// Function to calculate the length// of longest path of the treestatic int lengthOfLongestPath(Node node){ // Base Case if (node == null) return 0; // Recursive call to calculate the // length of longest path int left = lengthOfLongestPath(node.left); int right = lengthOfLongestPath(node.right); return 1 + (left > right ? left : right);}// Function to copy the complete// path in a matrixstatic void copyPath(int[] path, int index, int[][] mtrx, int r) { // Loop to copy the path for(int i = 0; i < index; i++) { mtrx[r][i] = path[i]; }}// Function to store all path// one by one in matrixstatic void storePath(Node node, int[] path, int index, int[][] mtrx){ // Base condition if (node == null) { return; } // Inserting the current node // into the current path path[index] = node.key; // Recursive call for // the left sub tree storePath(node.left, path, index + 1, mtrx); // Recursive call for // the right sub tree storePath(node.right, path, index + 1, mtrx); // Condition to check that current // node is a leaf node or not if (node.left == null && node.right == null) { // Incrementation for changing // row row = row + 1; // Function call for copying // the path copyPath(path, index + 1, mtrx, row); }}// Function to calculate// total pathstatic int totalPath(Node node) { if (node == null) { return count; } if (node.left == null && node.right == null) { return count + 1; } count = totalPath(node.left); return totalPath(node.right);}// Function for Clockwise Spiral Traversal// of Binary Treestatic void traverse_matrix(int[][] mtrx, int height, int width) { int j = 0, k1 = 0, k2 = 0; int k3 = height - 1; int k4 = width - 1; for(int round = 0; round < height / 2; round++) { for(j = k2; j < width; j++) { // Only print those values which // are not MAX_INTEGER if (mtrx[k1][j] != Integer.MAX_VALUE) { System.out.print(mtrx[k1][j] + " "); } } System.out.println(); k2 = 0; k1++; for(j = k4; j >= 0; j--) { // Only print those values which // are not MAX_INTEGER if (mtrx[k3][j] != Integer.MAX_VALUE) { System.out.print(mtrx[k3][j] + " "); } } System.out.println(); k4 = width - 1; k3--; } // Condition (one row may be left // traversing) // If number of rows in matrix are odd if (height % 2 != 0) { for(j = k2; j < width; j++) { // Only print those values which are // not MAX_INTEGER if (mtrx[k1][j] != Integer.MAX_VALUE) { System.out.print(mtrx[k1][j] + " "); } } }}// Function to print all the paths// in Boundary Root to Leaf// Path Traversalstatic void PrintPath(Node node){ // Calculate the length of // longest path of the tree int max_len = lengthOfLongestPath(node); // Calculate total path int total_path = totalPath(node); // Array to store path int[] path = new int[max_len]; Arrays.fill(path, 0); // Use double pointer to create // 2D array which will contain // all path of the tree int[][] mtrx = new int[total_path][max_len]; // Initialize complete matrix with // MAX INTEGER(purpose garbage) for(int i = 0; i < total_path; i++) { for(int j = 0; j < max_len; j++) { mtrx[i][j] = Integer.MAX_VALUE; } } row = -1; storePath(node, path, 0, mtrx); // Print the circular clockwise spiral // traversal of the tree traverse_matrix(mtrx, total_path, max_len);}// Driver Codepublic static void main(String[] args){ /* 10 / \ 13 11 / \ 19 23 / \ / \ 21 29 43 15 / 7 */ // Create Binary Tree as shown Node root = newNode(10); root.left = newNode(13); root.right = newNode(11); root.right.left = newNode(19); root.right.right = newNode(23); root.right.left.left = newNode(21); root.right.left.right = newNode(29); root.right.right.left = newNode(43); root.right.right.right = newNode(15); root.right.right.right.left = newNode(7); // Function Call PrintPath(root);}}// This code is contributed by sanjeev2552 |
Python3
# Python3 implementation to print the # path in Boundary Root to Leaf # Path Traversal. # Structure of tree nodeclass Node: def __init__(self, key): self.key = key self.left = None self.right = Nonerow = 0count = 0 # Utility function to# create a new nodedef newNode(key): temp = Node(key) return temp # Function to calculate the length# of longest path of the treedef lengthOfLongestPath(node): # Base Case if (node == None): return 0; # Recursive call to calculate the length # of longest path left = lengthOfLongestPath(node.left); right = lengthOfLongestPath(node.right); return 1 + (left if left > right else right);# Function to copy the complete# path in a matrixdef copyPath(path, index, mtrx, r): # Loop to copy the path for i in range(index): mtrx[r][i] = path[i];# Function to store all path# one by one in matrixdef storePath(node, path, index, mtrx): global row # Base condition if (node == None): return; # Inserting the current node # into the current path path[index] = node.key; # Recursive call for # the left sub tree storePath(node.left, path, index + 1, mtrx); # Recursive call for # the right sub tree storePath(node.right, path, index + 1, mtrx); # Condition to check that current # node is a leaf node or not if (node.left == None and node.right == None): # Incrementation for changing # row row = row + 1; # Function call for copying # the path copyPath(path, index + 1, mtrx, row); # Function to calculate# total pathdef totalPath(node): global count if (node == None): return count; if (node.left == None and node.right == None): return count + 1; count = totalPath(node.left); return totalPath(node.right); # Function for Clockwise Spiral Traversal# of Binary Treedef traverse_matrix( mtrx, height, width): j = 0 k1 = 0 k2 = 0; k3 = height - 1; k4 = width - 1; for round in range(height//2): for j in range(k2, width): # Only print those values which # are not MAX_INTEGER if (mtrx[k1][j] != 1000000): print(mtrx[k1][j], end=' ') print() k2 = 0; k1 += 1 for j in range(k4, -1, -1): # Only print those values which # are not MAX_INTEGER if (mtrx[k3][j] != 1000000): print(mtrx[k3][j], end=' ') print() k4 = width - 1; k3 -= 1 # Condition (one row may be left # traversing) # If number of rows in matrix are odd if (height % 2 != 0): for j in range(k2, width): # Only print those values which are # not MAX_INTEGER if (mtrx[k1][j] != 1000000): print(mtrx[k1][j], end=' ') # Function to print all the paths# in Boundary Root to Leaf # Path Traversaldef PrintPath(node): global row # Calculate the length of # longest path of the tree max_len = lengthOfLongestPath(node); # Calculate total path total_path = totalPath(node); # Array to store path path = [0 for i in range(max_len)] # Use double pointer to create # 2D array which will contain # all path of the tree mtrx = [[1000000 for j in range(max_len)] for i in range(total_path)] row = -1; storePath(node, path, 0, mtrx); # Print the circular clockwise spiral # traversal of the tree traverse_matrix(mtrx, total_path, max_len); # Driver Codeif __name__=='__main__': ''' 10 / \ 13 11 / \ 19 23 / \ / \ 21 29 43 15 / 7 ''' # Create Binary Tree as shown root = newNode(10); root.left = newNode(13); root.right = newNode(11); root.right.left = newNode(19); root.right.right = newNode(23); root.right.left.left = newNode(21); root.right.left.right = newNode(29); root.right.right.left = newNode(43); root.right.right.right = newNode(15); root.right.right.right.left = newNode(7); # Function Call PrintPath(root); # This code is contributed by pratham76 |
C#
// C# implementation to print the // path in Boundary Root to Leaf // Path Traversal. using System;using System.Collections; class GFG{ static int row;static int count = 0; // Structure of tree nodepublic class Node { public int key; public Node left, right;}; // Utility function to// create a new nodestatic Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);} // Function to calculate the length// of longest path of the treestatic int lengthOfLongestPath(Node node){ // Base Case if (node == null) return 0; // Recursive call to calculate the // length of longest path int left = lengthOfLongestPath(node.left); int right = lengthOfLongestPath(node.right); return 1 + (left > right ? left : right);} // Function to copy the complete// path in a matrixstatic void copyPath(int[] path, int index, int[,] mtrx, int r) { // Loop to copy the path for(int i = 0; i < index; i++) { mtrx[r, i] = path[i]; }} // Function to store all path// one by one in matrixstatic void storePath(Node node, int[] path, int index, int[,] mtrx){ // Base condition if (node == null) { return; } // Inserting the current node // into the current path path[index] = node.key; // Recursive call for // the left sub tree storePath(node.left, path, index + 1, mtrx); // Recursive call for // the right sub tree storePath(node.right, path, index + 1, mtrx); // Condition to check that current // node is a leaf node or not if (node.left == null && node.right == null) { // Incrementation for changing // row row = row + 1; // Function call for copying // the path copyPath(path, index + 1, mtrx, row); }} // Function to calculate// total pathstatic int totalPath(Node node) { if (node == null) { return count; } if (node.left == null && node.right == null) { return count + 1; } count = totalPath(node.left); return totalPath(node.right);} // Function for Clockwise Spiral Traversal// of Binary Treestatic void traverse_matrix(int[,] mtrx, int height, int width) { int j = 0, k1 = 0, k2 = 0; int k3 = height - 1; int k4 = width - 1; for(int round = 0; round < height / 2; round++) { for(j = k2; j < width; j++) { // Only print those values which // are not MAX_INTEGER if (mtrx[k1, j] != 10000000) { Console.Write(mtrx[k1, j] + " "); } } Console.WriteLine(); k2 = 0; k1++; for(j = k4; j >= 0; j--) { // Only print those values which // are not MAX_INTEGER if (mtrx[k3, j] != 10000000) { Console.Write(mtrx[k3, j] + " "); } } Console.WriteLine(); k4 = width - 1; k3--; } // Condition (one row may be left // traversing) // If number of rows in matrix are odd if (height % 2 != 0) { for(j = k2; j < width; j++) { // Only print those values which are // not MAX_INTEGER if (mtrx[k1, j] != 10000000) { Console.Write(mtrx[k1, j] + " "); } } }} // Function to print all the paths// in Boundary Root to Leaf// Path Traversalstatic void PrintPath(Node node){ // Calculate the length of // longest path of the tree int max_len = lengthOfLongestPath(node); // Calculate total path int total_path = totalPath(node); // Array to store path int[] path = new int[max_len]; Array.Fill(path, 0); // Use double pointer to create // 2D array which will contain // all path of the tree int[,] mtrx = new int[total_path, max_len]; // Initialize complete matrix with // MAX INTEGER(purpose garbage) for(int i = 0; i < total_path; i++) { for(int j = 0; j < max_len; j++) { mtrx[i, j] = 10000000; } } row = -1; storePath(node, path, 0, mtrx); // Print the circular clockwise spiral // traversal of the tree traverse_matrix(mtrx, total_path, max_len);} // Driver Codepublic static void Main(string[] args){ /* 10 / \ 13 11 / \ 19 23 / \ / \ 21 29 43 15 / 7 */ // Create Binary Tree as shown Node root = newNode(10); root.left = newNode(13); root.right = newNode(11); root.right.left = newNode(19); root.right.right = newNode(23); root.right.left.left = newNode(21); root.right.left.right = newNode(29); root.right.right.left = newNode(43); root.right.right.right = newNode(15); root.right.right.right.left = newNode(7); // Function Call PrintPath(root);}}// This code is contributed by rutvik_56 |
Javascript
<script> // JavaScript implementation to print the // path in Boundary Root to Leaf // Path Traversal. let row; let count = 0; // Structure of tree node class Node { constructor(key) { this.left = null; this.right = null; this.key = key; } } // Utility function to // create a new node function newNode(key) { let temp = new Node(key); return (temp); } // Function to calculate the length // of longest path of the tree function lengthOfLongestPath(node) { // Base Case if (node == null) return 0; // Recursive call to calculate the // length of longest path let left = lengthOfLongestPath(node.left); let right = lengthOfLongestPath(node.right); return 1 + (left > right ? left : right); } // Function to copy the complete // path in a matrix function copyPath(path, index, mtrx, r) { // Loop to copy the path for(let i = 0; i < index; i++) { mtrx[r][i] = path[i]; } } // Function to store all path // one by one in matrix function storePath(node, path, index, mtrx) { // Base condition if (node == null) { return; } // Inserting the current node // into the current path path[index] = node.key; // Recursive call for // the left sub tree storePath(node.left, path, index + 1, mtrx); // Recursive call for // the right sub tree storePath(node.right, path, index + 1, mtrx); // Condition to check that current // node is a leaf node or not if (node.left == null && node.right == null) { // Incrementation for changing // row row = row + 1; // Function call for copying // the path copyPath(path, index + 1, mtrx, row); } } // Function to calculate // total path function totalPath(node) { if (node == null) { return count; } if (node.left == null && node.right == null) { return count + 1; } count = totalPath(node.left); return totalPath(node.right); } // Function for Clockwise Spiral Traversal // of Binary Tree function traverse_matrix(mtrx, height, width) { let j = 0, k1 = 0, k2 = 0; let k3 = height - 1; let k4 = width - 1; for(let round = 0; round < parseInt(height / 2, 10); round++) { for(j = k2; j < width; j++) { // Only print those values which // are not MAX_INTEGER if (mtrx[k1][j] != Number.MAX_VALUE) { document.write(mtrx[k1][j] + " "); } } document.write("</br>"); k2 = 0; k1++; for(j = k4; j >= 0; j--) { // Only print those values which // are not MAX_INTEGER if (mtrx[k3][j] != Number.MAX_VALUE) { document.write(mtrx[k3][j] + " "); } } document.write("</br>"); k4 = width - 1; k3--; } // Condition (one row may be left // traversing) // If number of rows in matrix are odd if (height % 2 != 0) { for(j = k2; j < width; j++) { // Only print those values which are // not MAX_INTEGER if (mtrx[k1][j] != Number.MAX_VALUE) { document.write(mtrx[k1][j] + " "); } } } } // Function to print all the paths // in Boundary Root to Leaf // Path Traversal function PrintPath(node) { // Calculate the length of // longest path of the tree let max_len = lengthOfLongestPath(node); // Calculate total path let total_path = totalPath(node); // Array to store path let path = new Array(max_len); path.fill(0); // Use double pointer to create // 2D array which will contain // all path of the tree let mtrx = new Array(total_path); // Initialize complete matrix with // MAX INTEGER(purpose garbage) for(let i = 0; i < total_path; i++) { mtrx[i] = new Array(max_len); for(let j = 0; j < max_len; j++) { mtrx[i][j] = Number.MAX_VALUE; } } row = -1; storePath(node, path, 0, mtrx); // Print the circular clockwise spiral // traversal of the tree traverse_matrix(mtrx, total_path, max_len); } /* 10 / \ 13 11 / \ 19 23 / \ / \ 21 29 43 15 / 7 */ // Create Binary Tree as shown let root = newNode(10); root.left = newNode(13); root.right = newNode(11); root.right.left = newNode(19); root.right.right = newNode(23); root.right.left.left = newNode(21); root.right.left.right = newNode(29); root.right.right.left = newNode(43); root.right.right.right = newNode(15); root.right.right.right.left = newNode(7); // Function Call PrintPath(root);</script> |
Output:
10 13 7 15 23 11 10 10 11 19 21 43 23 11 10 10 11 19 29
Time Complexity: The time complexity of the above code is O(n^2), where n is the number of nodes in the binary tree. This is because the code traverses through all the nodes in the tree in order to store the paths in the matrix and to calculate the length of the longest path
Auxiliary Space: The Auxiliary Space is O(n^2), as the matrix used to store the paths has a size of n x n, where n is the number of nodes in the tree.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
