Convert a Binary Tree into Doubly Linked List in spiral fashion | c ++ program to convert Binary Tree into Doubly Linked List where the nodes are represented spirally . ; A Binary Tree Node ; Given a reference to the head of a list and a node , inserts the node on the front of the list . ; Make right of given node as head and left as NULL ; change left of head node to given node ; move the head to point to the given node ; Function to prints contents of DLL ; Function to print corner node at each level ; Base Case ; Create an empty deque for doing spiral level order traversal and enqueue root ; create a stack to store Binary Tree nodes to insert into DLL later ; nodeCount indicates number of Nodes at current level . ; Dequeue all Nodes of current level and Enqueue all Nodes of next level odd level ; dequeue node from front & push it to stack ; insert its left and right children in the back of the deque ; even level ; dequeue node from the back & push it to stack ; inserts its right and left children in the front of the deque ; head pointer for DLL ; pop all nodes from stack and push them in the beginning of the list ; Utility function to create a new tree Node ; Driver program to test above functions ; Let us create binary tree shown in above diagram ; root -> right -> left -> left = newNode ( 12 ) ; ; root -> right -> right -> right = newNode ( 15 ) ;
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; void push ( Node * * head_ref , Node * node ) { node -> right = ( * head_ref ) ; node -> left = NULL ; if ( ( * head_ref ) != NULL ) ( * head_ref ) -> left = node ; ( * head_ref ) = node ; } void printList ( Node * node ) { while ( node != NULL ) { cout << node -> data << " ▁ " ; node = node -> right ; } } void spiralLevelOrder ( Node * root ) { if ( root == NULL ) return ; deque < Node * > q ; q . push_front ( root ) ; stack < Node * > stk ; int level = 0 ; while ( ! q . empty ( ) ) { int nodeCount = q . size ( ) ; if ( level & 1 ) { while ( nodeCount > 0 ) { Node * node = q . front ( ) ; q . pop_front ( ) ; stk . push ( node ) ; if ( node -> left != NULL ) q . push_back ( node -> left ) ; if ( node -> right != NULL ) q . push_back ( node -> right ) ; nodeCount -- ; } } else { while ( nodeCount > 0 ) { Node * node = q . back ( ) ; q . pop_back ( ) ; stk . push ( node ) ; if ( node -> right != NULL ) q . push_front ( node -> right ) ; if ( node -> left != NULL ) q . push_front ( node -> left ) ; nodeCount -- ; } } level ++ ; } Node * head = NULL ; while ( ! stk . empty ( ) ) { push ( & head , stk . top ( ) ) ; stk . pop ( ) ; } cout << " Created ▁ DLL ▁ is : STRNEWLINE " ; printList ( head ) ; } Node * newNode ( int data ) { Node * temp = new Node ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } int main ( ) { Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 5 ) ; root -> right -> left = newNode ( 6 ) ; root -> right -> right = newNode ( 7 ) ; root -> left -> left -> left = newNode ( 8 ) ; root -> left -> left -> right = newNode ( 9 ) ; root -> left -> right -> left = newNode ( 10 ) ; root -> left -> right -> right = newNode ( 11 ) ; root -> right -> left -> right = newNode ( 13 ) ; root -> right -> right -> left = newNode ( 14 ) ; spiralLevelOrder ( root ) ; return 0 ; }