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 node struct Node { int key; struct Node *left, *right; }; // Utility function to // create a new node 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 tree int 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 matrix void 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 matrix void 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 path int 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 Tree 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] != 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 Traversal 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]; 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 Code int 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 node static class Node { int key; Node left, right; }; // Utility function to // create a new node static 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 tree static 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 matrix static 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 matrix static 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 path static 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 Tree static 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 Traversal static 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 Code public 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 node class Node: def __init__( self , key): self .key = key self .left = None self .right = None row = 0 count = 0 # Utility function to # create a new node def newNode(key): temp = Node(key) return temp # Function to calculate the length # of longest path of the tree def 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 matrix def 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 matrix def 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 path def 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 Tree def 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 Traversal def 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 Code if __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 node public class Node { public int key; public Node left, right; }; // Utility function to // create a new node static 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 tree static 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 matrix static 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 matrix static 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 path static 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 Tree static 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 Traversal static 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 Code public 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> |
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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!