AI coding assistant for busy programmers

All

JavaScript

Print the elements of a binary tree in spiral order in C++

C++

#include <iostream>
#include <stack>
using namespace std;

struct node {
    int data;
    struct node *left, *right;
};

struct node* newNode(int data) {
    struct node* node = (struct node*)malloc(sizeof(struct node));

node->data = data;

node->left = NULL;

node->right = NULL;

return(node);

}

void printSpiral(struct node *root) {

if (root == NULL) return; // NULL check

// Create two stacks to store alternate levels. For levels to be printed from right to left, first stack is filled and second stack is empty. For levels to be printed from left to right, second stack is filled and first stack is empty.

stack<struct node*> s1; // For levels to be printed from right to left.

stack<struct node*> s2; // For levels to be printed from left to right.

// Push first level to first stack 's1' and print it. Then push children of all nodes at this level to second stack 's2' and print them in reverse order. Continue this process until both stacks are empty. If one of the stacks becomes empty then we have finished printing for that direction also, so we can terminate the loop. We can use a flag variable 'flag' which becomes true when one of the stacks becomes empty and use it break out of the loop when second stack also becomes empty after printing a level in reverse order. This flag variable is not really needed here as we know that the loop will terminate when both stacks become empty, but I have used it here just for completeness sake (to show that we can use a flag variable if required). We can also use two variables 'rev' (for reverse) instead of using a flag variable as shown below: rev = 1 indicates that next level should be printed in reverse order and rev = 0 indicates that next level should be printed in normal order. The code below uses two stacks but it can easily modified to work with only one stack by using a different logic within the loop body - see comments below for details: */

s1.push(root); // Push root into first stack 's1'. We don't need any other logic here as root will always be at first level which will always be printed in normal order (from left-to-right). So we simply push root into first stack 's1'. If you want you can also push root into second stack 's2' here instead of pushing it into 's1', but then you would need an extra boolean variable which indicates whether this is the first element being pushed into either of these two stacks or not - see comments below for details: */

int rev = 0; // Flag variable used for reversing direction or not: */

while (!s1.empty() || !s2.empty()) { // While both stacks are not empty keep printing...*/
          if (!rev) { // If direction is normal...*/
              while (!s1.empty()) { /* Pop all nodes from top of first stack 's1' and push their children into second stack 's2'. Print only those nodes which are popped out - do not print any child nodes at this point.*/
                  struct node *temp = s1.top(); s1.pop(); cout << temp->data << " "; /* Pop out top element.*/ /* Push its children.*/ if (temp->right) s2.push(temp->right); if (temp->left) s2 .push(temp->left); } rev = 1 - rev;} else { /* If direction is reversed...*/ while (!s2 .empty()) { /* Pop all nodes from top of second stac k's2' and push their children into first stac k's1'. Print only those nodes which are popped out - do not print any child nodes at this point.*/ struct n ode *temp = s2 .top(); s2 .pop(); cout << temp ->data << " " ; /* Pop out top element.*/ /* Push its children.*/ if (temp ->left ) s 1 .push(temp ->left ); if (temp ->right ) s 1 .push( temp ->right ); } rev= 1-rev ; } } } int main() { struct n ode *root= newNode( 1 ); root ->left= newNode( 2 ); root ->right= newNode( 3 ); root ->left ->left= newNode( 7 ); root ->left ->right= newNode( 6 ); root ->right ->left= newNode( 5 ); root ->right ->right= newNode( 4 ); cout<<"Spiral Order traversal of binary tree is \n"; printSpiral (root); return 0 ; }

🤖 Code Explanation

This code creates a new node struct with data, left, and right pointers. It also defines a printSpiral function that takes in a node struct (the root node) and prints the data in the node in a spiral pattern. Finally, the code defines a main function that creates a new root node and prints the spiral pattern of the node data.

AI coding assistant for busy programmers

Print the elements of a binary tree in spiral order in C++

C++

🤖 Code Explanation

More problems solved in C++