Convert a Binary Tree into Doubly Linked List in spiral fashion | Java program to convert Binary Tree into Doubly Linked List where the nodes are represented spirally ; A binary tree node ; Given a reference to 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 ; pop all nodes from stack and push them in the beginning of the list ; Driver program to test above functions ; Let us create binary tree as shown in above diagram ; tree . root . right . left . left = new Node ( 12 ) ; ; tree . root . right . right . right = new Node ( 15 ) ;
import java . util . * ; class Node { int data ; Node left , right ; public Node ( int data ) { this . data = data ; left = right = null ; } } class BinaryTree { Node root ; Node head ; void push ( Node node ) { node . right = head ; node . left = null ; if ( head != null ) head . left = node ; head = node ; } void printList ( Node node ) { while ( node != null ) { System . out . print ( node . data + " ▁ " ) ; node = node . right ; } } void spiralLevelOrder ( Node root ) { if ( root == null ) return ; Deque < Node > q = new LinkedList < Node > ( ) ; q . addFirst ( root ) ; Stack < Node > stk = new Stack < Node > ( ) ; int level = 0 ; while ( ! q . isEmpty ( ) ) { int nodeCount = q . size ( ) ; if ( ( level & 1 ) % 2 != 0 ) { while ( nodeCount > 0 ) { Node node = q . peekFirst ( ) ; q . pollFirst ( ) ; stk . push ( node ) ; if ( node . left != null ) q . addLast ( node . left ) ; if ( node . right != null ) q . addLast ( node . right ) ; nodeCount -- ; } } else { while ( nodeCount > 0 ) { Node node = q . peekLast ( ) ; q . pollLast ( ) ; stk . push ( node ) ; if ( node . right != null ) q . addFirst ( node . right ) ; if ( node . left != null ) q . addFirst ( node . left ) ; nodeCount -- ; } } level ++ ; } while ( ! stk . empty ( ) ) { push ( stk . peek ( ) ) ; stk . pop ( ) ; } System . out . println ( " Created ▁ DLL ▁ is ▁ : ▁ " ) ; printList ( head ) ; } public static void main ( String [ ] args ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = new Node ( 1 ) ; tree . root . left = new Node ( 2 ) ; tree . root . right = new Node ( 3 ) ; tree . root . left . left = new Node ( 4 ) ; tree . root . left . right = new Node ( 5 ) ; tree . root . right . left = new Node ( 6 ) ; tree . root . right . right = new Node ( 7 ) ; tree . root . left . left . left = new Node ( 8 ) ; tree . root . left . left . right = new Node ( 9 ) ; tree . root . left . right . left = new Node ( 10 ) ; tree . root . left . right . right = new Node ( 11 ) ; tree . root . right . left . right = new Node ( 13 ) ; tree . root . right . right . left = new Node ( 14 ) ; tree . spiralLevelOrder ( tree . root ) ; } }