Diagonal Traversal of Binary Tree - GeeksforGeeks

Diagonal Traversal of Binary Tree - GeeksforGeeks
Consider lines of slope -1 passing between nodes. Given a Binary Tree, print all diagonal elements in a binary tree belonging to same line.

Input : Root of below tree


Output : 
Diagonal Traversal of binary tree : 
 8 10 14
 3 6 7 13
 1 4

The idea is to use map. We use different slope distances and use them as key in map. Value in map is vector (or dynamic array) of nodes. We traverse the tree to store values in map. Once map is built, we print contents of it.

oid diagonalPrintUtil(Node* root, int d,

                      map<int, vector<int>> &diagonalPrint)

{

    // Base case

    if (!root)

        return;

 

    // Store all nodes of same line together as a vector

    diagonalPrint[d].push_back(root->data);

 

    // Increase the vertical distance if left child

    diagonalPrintUtil(root->left, d + 1, diagonalPrint);

 

    // Vertical distance remains same for right child

    diagonalPrintUtil(root->right, d, diagonalPrint);

}

 

// Print diagonal traversal of given binary tree

void diagonalPrint(Node* root)

{

    // create a map of vectors to store Diagonal elements

    map<int, vector<int> > diagonalPrint;

    diagonalPrintUtil(root, 0, diagonalPrint);

 

    cout << "Diagonal Traversal of binary tree : \n";

    for (auto it = diagonalPrint.begin();

         it != diagonalPrint.end(); ++it)

    {

        for (auto itr = it->second.begin();

             itr != it->second.end(); ++itr)

            cout << *itr  << ' ';

 

        cout << '\n';

    }

Read full article from Diagonal Traversal of Binary Tree - GeeksforGeeks