神刀安全网

Diagonal Traversal of Binary Tree

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 Diagonal Traversal of Binary Tree  Output :  Diagonal Traversal of binary tree :   8 10 14  3 6 7 13  1 4

We strongly recommend you to minimize your browser and try this yourself first.

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.

Below is C++ implementation of above idea.

// C++ program for diagnoal traversal of Binary Tree #include <bits/stdc++.h> using namespace std;  // Tree node struct Node {     int data;     Node *left, *right; };  /* root - root of the binary tree    d -  distance of current line from rightmost         -topmost slope.    diagonalPrint - multimap to store Diagonal                    elements (Passed by Reference) */ void 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';     } }  // Utility method to create a new node Node* newNode(int data) {     Node* node = new Node;     node->data = data;     node->left = node->right = NULL;     return node; }  // Driver program int main() {     Node* root = newNode(8);     root->left = newNode(3);     root->right = newNode(10);     root->left->left = newNode(1);     root->left->right = newNode(6);     root->right->right = newNode(14);     root->right->right->left = newNode(13);     root->left->right->left = newNode(4);     root->left->right->right = newNode(7);      /*  Node* root = newNode(1);         root->left = newNode(2);         root->right = newNode(3);         root->left->left = newNode(9);         root->left->right = newNode(6);         root->right->left = newNode(4);         root->right->right = newNode(5);         root->right->left->right = newNode(7);         root->right->left->left = newNode(12);         root->left->right->left = newNode(11);         root->left->left->right = newNode(10);*/      diagonalPrint(root);      return 0; }

Output :

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

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Diagonal Traversal of Binary Tree

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址