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. If the diagonal element are present in two different subtress then left subtree diagonal element should be taken first and then right subtree.?

?? View Full Code ??

Approach :

• Breadth-First Traversal with Queue: Use a queue to perform level-wise processing. The right child will always belong to the same diagonal, and the left child will belong to the next diagonal.
• Push Nodes: Push the root node into the queue to start.
• Traversal: For each node at the front of the queue, add it to the result list. Move to the right child (staying in the same diagonal) and add left children to the queue (next diagonal).
• Repeat: Continue until the queue is empty, processing nodes level by level and capturing diagonal elements in order.

vector<int> diagonal(Node *root)
{
   
   vector<int>ans;
   
   if(root == NULL){
       return ans ;
   }
   
   queue<Node*>q;
   q.push(root);
   
   while(!q.empty()){
       Node* frontNode = q.front();
       q.pop();
       
       while(frontNode != NULL){
           ans.push_back(frontNode->data);
           if(frontNode->left){
               q.push(frontNode->left);
           }
           frontNode = frontNode->right;
       }
       
   }
   return ans;
   
}        

1. Queue Initialization: We initialize a queue that will store nodes based on diagonal lines. We start by adding the root node to the queue.
2. For each node in the queue:

• Add its data to the result (ans).
• Check if it has a left child and, if so, push it to the queue (since it belongs to the next diagonal).
• Move to the right child, as it belongs to the same diagonal line.

The result is stored in the vector ans, which contains the diagonal elements in the desired order.

Time Complexity: O(N)

Space Complexity: O(N)

?? GitHub Repo ??