Traverse the matrix in Diagonally Bottom-Up fashion using Recursion

0 0 7 minutes read

Given a matrix mat[][] of size N x N, the task is to traverse the matrix Diagonally in Bottom-up fashion using recursion.
Diagonally Bottom-up Traversal:

Traverse the major-diagonal of the matrix.
Traverse the bottom diagonal to the major-diagonal of the matrix.
Traverse the up diagonal to the major-diagonal of the matrix.
Similarly, Traverse the matrix for every diagonal.

The below image shows the Bottom-up Traversal of the matrix.

Examples:

Input: 
M[][] = {{11, 42, 25, 51}, 
         {14, 17, 61, 23},
         {22, 38, 19, 12},
         {27, 81, 29, 71}} 
Output: 
11 17 19 71 
14 38 29 
42 61 12 
22 81 
25 23 
27 
51 

Input: 
M[][] = {{3, 2, 5}, 
         {4, 7, 6},
         {2, 8, 9}}
Output: 
3 7 9 
4 8 
2 6 
2 
5

Approach: The idea is to traverse the major-diagonal elements of the matrix and then recursively call the for the bottom diagonal of the matrix and the diagonal above to the major-diagonal of the matrix. Recursive Definition of the approach is described as follows:

Function Definition: For this problem, there will be the following arguments as follows:
- mat[][] // Matrix to be Traversed
- Current Row (say i) // Current Row to be Traversed
- Current Column (say j) // Current Column to be Traversed
- Number of rows (say row)
- Number of columns (say col)
Base Case: The base case for this problem can be when the current row or the current column is out of bounds. In this case, traverse the other bottom diagonal, or if the bottom diagonal is chosen last time then traverse the major-diagonal just above it.

if (i >= row or j >= col)
    if (flag)
        // Change the Current index
        // to the bottom diagonal
    else
        // Change the current index
        // to the up diagonal of matrix

Recursive Case: There will be two cases of the recursive traversal of the matrix which is defined as follows:
- Traversal of the Current Diagonal: To traverse the current diagonal increment the current row and column by 1 at the same time and recursively call the function.
- Traversal of Bottom / Up Diagonal: To traverse the bottom / up diagonal call the recursive function with the static variables storing the next traversal start point of the matrix.

Below is the implementation of the above approach:

C++

// C++ implementation to traverse the
// matrix in the bottom-up fashion
// using Recursion
 
#include <iostream>
 
using namespace std;
 
// Recursive function to traverse the
// matrix Diagonally Bottom-up
bool traverseMatrixDiagonally(int m[][5], 
          int i, int j, int row, int col)
{
     
    // Static variable for changing
    // Row and column
    static int k1 = 0, k2 = 0;
     
    // Flag variable for handling
    // Bottom up diagonal traversing
    static bool flag = true;
     
    // Base Condition
    if (i >= row || j >= col) {
         
        // Condition when to traverse
        // Bottom Diagonal of the matrix
        if (flag) {
            int a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
            k1++;
        }
        else {
 
            int a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
        }
        cout << endl;
        return false;
    }
     
    // Print matrix cell value
    cout << m[i][j] << " ";
     
    // Recursive function to traverse
    // The matrix diagonally
    if (traverseMatrixDiagonally(
           m, i + 1, j + 1, row, col)) {
        return true;
    }
    // Recursive function 
    // to change diagonal
    if (traverseMatrixDiagonally(
            m, k1, k2, row, col)) {
        return true;
    }
     
    return true;
}
 
// Driver Code
int main()
{
    // Initialize the 5 x 5 matrix
    int mtrx[5][5] = {
        { 10, 11, 12, 13, 14 },
        { 15, 16, 17, 18, 19 },
        { 20, 21, 22, 23, 24 },
        { 25, 26, 27, 28, 29 },
        { 30, 31, 32, 33, 34 }
    };
 
    // Function call 
    // for traversing matrix
    traverseMatrixDiagonally(
            mtrx, 0, 0, 5, 5);
}

Java

// Java implementation to traverse 
// the matrix in the bottom-up 
// fashion using recursion
class GFG{
     
// Static variable for changing
// row and column
static int k1 = 0, k2 = 0;
 
// Flag variable for handling
// bottom up diagonal traversing
static boolean flag = true; 
 
// Recursive function to traverse the
// matrix diagonally bottom-up
static boolean traverseMatrixDiagonally(int m[][], int i,
                                        int j, int row,
                                        int col)
{
     
    // Base Condition
    if (i >= row || j >= col)
    {
         
        // Condition when to traverse
        // Bottom Diagonal of the matrix
        if (flag)
        {
            int a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
            k1++;
        }
        else
        {
            int a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
        }
         
        System.out.println();
        return false;
    }
     
    // Print matrix cell value
    System.out.print(m[i][j] + " ");
     
    // Recursive function to traverse
    // The matrix diagonally
    if (traverseMatrixDiagonally(m, i + 1,
                                    j + 1, row, col))
    {
        return true;
    }
     
    // Recursive function 
    // to change diagonal
    if (traverseMatrixDiagonally(m, k1, k2, row, col))
    {
        return true;
    }
     
    return true;
}
 
// Driver Code
public static void main(String[] args)
{
    // Initialize the 5 x 5 matrix
    int mtrx[][] = { { 10, 11, 12, 13, 14 },
                     { 15, 16, 17, 18, 19 },
                     { 20, 21, 22, 23, 24 },
                     { 25, 26, 27, 28, 29 },
                     { 30, 31, 32, 33, 34 } };
 
    // Function call 
    // for traversing matrix
    traverseMatrixDiagonally(mtrx, 0, 0, 5, 5);
}
}
 
// This code is contributed by sapnasingh4991

Python3

# Python3 implementation to traverse the 
# matrix in the bottom-up fashion 
# using Recursion
 
# Static variable for changing 
# Row and column
k1 = 0
k2 = 0
 
# Flag variable for handling 
# Bottom up diagonal traversing
flag = True
 
# Recursive function to traverse the 
# matrix Diagonally Bottom-up
def traverseMatrixDiagonally(m, i, 
                             j, row, col):
    global k1
    global k2
    global flag
 
    # Base Condition
    if(i >= row or j >= col):
 
        # Condition when to traverse 
        # Bottom Diagonal of the matrix
        if(flag):
            a = k1 
            k1 = k2
            k2 = a
            if(flag):
                flag = False
            else:
                flag = True
            k1 += 1
        else:
            a = k1
            k1 = k2
            k2 = a
            if(flag):
                flag = False
            else:
                flag = True
        print()
        return False
       
    # Print matrix cell value
    print(m[i][j], end = " ")
 
    # Recursive function to traverse 
    # The matrix diagonally
    if (traverseMatrixDiagonally(m, i + 1, 
                                 j + 1, 
                                 row, col)):
        return True
 
    # Recursive function  
    # to change diagonal
    if(traverseMatrixDiagonally(m, k1, 
                                k2, row, col)):
        return True
    return True
 
# Driver Code
 
# Initialize the 5 x 5 matrix
mtrx=[[10, 11, 12, 13, 14],
      [15, 16, 17, 18, 19],
      [20, 21, 22, 23, 24],
      [25, 26, 27, 28, 29],
      [30, 31, 32, 33, 34]]
 
# Function call  
# for traversing matrix
traverseMatrixDiagonally(mtrx, 0, 
                         0, 5, 5)
 
#This code is contributed by avanitrachhadiya2155

C#

// C# implementation to traverse 
// the matrix in the bottom-up 
// fashion using recursion
using System;
 
class GFG{
     
// Static variable for changing
// row and column
static int k1 = 0, k2 = 0;
 
// Flag variable for handling
// bottom up diagonal traversing
static bool flag = true; 
 
// Recursive function to traverse the
// matrix diagonally bottom-up
static bool traverseMatrixDiagonally(int [,]m, int i,
                                     int j, int row,
                                     int col)
{
     
    // Base Condition
    if (i >= row || j >= col)
    {
         
        // Condition when to traverse
        // Bottom Diagonal of the matrix
        if (flag)
        {
            int a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
            k1++;
        }
        else
        {
            int a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
        }
         
        Console.WriteLine();
        return false;
    }
     
    // Print matrix cell value
    Console.Write(m[i, j] + " ");
     
    // Recursive function to traverse
    // The matrix diagonally
    if (traverseMatrixDiagonally(m, i + 1,
                                    j + 1, row, col))
    {
        return true;
    }
     
    // Recursive function 
    // to change diagonal
    if (traverseMatrixDiagonally(m, k1, k2, row, col))
    {
        return true;
    }
    return true;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Initialize the 5 x 5 matrix
    int [,]mtrx = { { 10, 11, 12, 13, 14 },
                    { 15, 16, 17, 18, 19 },
                    { 20, 21, 22, 23, 24 },
                    { 25, 26, 27, 28, 29 },
                    { 30, 31, 32, 33, 34 } };
 
    // Function call for  
    // traversing matrix
    traverseMatrixDiagonally(mtrx, 0, 0, 5, 5);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
// Java script implementation to traverse
// the matrix in the bottom-up
// fashion using recursion
 
     
// Static variable for changing
// row and column
let k1 = 0, k2 = 0;
 
// Flag variable for handling
// bottom up diagonal traversing
let flag = true;
 
// Recursive function to traverse the
// matrix diagonally bottom-up
function traverseMatrixDiagonally(m,i,j,row,col)
{
     
    // Base Condition
    if (i >= row || j >= col)
    {
         
        // Condition when to traverse
        // Bottom Diagonal of the matrix
        if (flag)
        {
            let a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
            k1++;
        }
        else
        {
            let a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
        }
         
        document.write("<br>");
        return false;
    }
     
    // Print matrix cell value
    document.write(m[i][j] + " ");
     
    // Recursive function to traverse
    // The matrix diagonally
    if (traverseMatrixDiagonally(m, i + 1,
                                    j + 1, row, col))
    {
        return true;
    }
     
    // Recursive function
    // to change diagonal
    if (traverseMatrixDiagonally(m, k1, k2, row, col))
    {
        return true;
    }
     
    return true;
}
 
// Driver Code
 
    // Initialize the 5 x 5 matrix
    let mtrx = [[ 10, 11, 12, 13, 14 ],
                    [ 15, 16, 17, 18, 19 ],
                    [ 20, 21, 22, 23, 24 ],
                    [ 25, 26, 27, 28, 29 ],
                    [ 30, 31, 32, 33, 34 ]];
 
    // Function call
    // for traversing matrix
    traverseMatrixDiagonally(mtrx, 0, 0, 5, 5);
 
 
//This code is contributed by sravan kumar
</script>

Output

10 16 22 28 34 
15 21 27 33 
11 17 23 29 
20 26 32 
12 18 24 
25 31 
13 19 
30 
14

Time Complexity: O(N²)

The time complexity of the above algorithm is O(N^2) where N is the number of the elements in the matrix. This is because the algorithm recursively calls itself for each element of the matrix.

Space Complexity: O(N)

The space complexity of the above algorithm is O(N) where N is the number of elements in the matrix. This is because the algorithm uses recursive calls to traverse the matrix.

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 zambiatek!