Convert a Binary Tree into Doubly Linked List in spiral fashion

Last Updated : 30 Jun, 2022

Given a Binary Tree, convert it into a Doubly Linked List where the nodes are represented Spirally. The left pointer of the binary tree node should act as a previous node for created DLL and the right pointer should act as the next node.

The solution should not allocate extra memory for DLL nodes. It should use binary tree nodes for creating DLL i.e. only change of pointers is allowed.

For example, for the tree on the left side, Doubly Linked List can be,
1 2 3 7 6 5 4 8 9 10 11 13 14 or
1 3 2 4 5 6 7 14 13 11 10 9 8.

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

We can do this by doing a spiral order traversal in O(n) time and O(n) extra space. The idea is to use deque (Double-ended queue) that can be expanded or contracted on both ends (either its front or it’s back). We do something similar to level order traversal but to maintain spiral order, for every odd level, we dequeue node from the front and insert its left and right children in the back of the deque data structure. And for each even level, we dequeue node from the back and insert its right and left children in the front of the deque. We also maintain a stack to store Binary Tree nodes. Whenever we pop nodes from deque, we push that node into the stack.

Later, we pop all nodes from the stack and push the nodes at the beginning of the list. We can avoid the use of stack if we maintain a tail pointer that always points to the last node of DLL and inserts nodes in O(1) time in the end.

Below is the implementation of the above idea

C++

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

Java

/* Java program to convert Binary Tree into Doubly Linked List  
   where the nodes are represented spirally */
  
import java.util.*; 
  
// A binary tree node 
class Node  
{ 
    int data; 
    Node left, right; 
  
    public Node(int data)  
    { 
        this.data = data; 
        left = right = null; 
    } 
} 
  
class BinaryTree  
{ 
    Node root; 
    Node head; 
  
    /* Given a reference to a node, 
       inserts the node on the front of the list. */
    void push(Node node)  
    { 
        // Make right of given node as head and left as 
        // NULL 
        node.right = head; 
        node.left = null; 
  
        // change left of head node to given node 
        if (head != null)  
            head.left = node; 
              
        // move the head to point to the given node 
        head = node; 
    } 
  
    // Function to prints contents of DLL 
    void printList(Node node)  
    { 
        while (node != null)  
        { 
            System.out.print(node.data + " "); 
            node = node.right; 
        } 
    } 
  
    /* Function to print corner node at each level */
    void spiralLevelOrder(Node root)  
    { 
        // Base Case 
        if (root == null) 
            return; 
  
        // Create an empty deque for doing spiral 
        // level order traversal and enqueue root 
        Deque<Node> q = new LinkedList<Node>(); 
        q.addFirst(root); 
  
        // create a stack to store Binary Tree nodes 
        // to insert into DLL later 
        Stack<Node> stk = new Stack<Node>(); 
  
        int level = 0; 
        while (!q.isEmpty())  
        { 
            // nodeCount indicates number of Nodes 
            // at current level. 
            int nodeCount = q.size(); 
  
            // Dequeue all Nodes of current level and 
            // Enqueue all Nodes of next level 
            if ((level & 1) %2 != 0) //odd level 
            { 
                while (nodeCount > 0)  
                { 
                    // dequeue node from front & push it to 
                    // stack 
                    Node node = q.peekFirst(); 
                    q.pollFirst(); 
                    stk.push(node); 
  
                    // insert its left and right children 
                    // in the back of the deque 
                    if (node.left != null) 
                        q.addLast(node.left); 
                    if (node.right != null) 
                        q.addLast(node.right); 
  
                    nodeCount--; 
                } 
            }  
            else //even level 
            { 
                while (nodeCount > 0)  
                { 
                    // dequeue node from the back & push it 
                    // to stack 
                    Node node = q.peekLast(); 
                    q.pollLast(); 
                    stk.push(node); 
  
                    // inserts its right and left children 
                    // in the front of the deque 
                    if (node.right != null) 
                        q.addFirst(node.right); 
                    if (node.left != null) 
                        q.addFirst(node.left); 
                    nodeCount--; 
                } 
            } 
            level++; 
        } 
  
        // pop all nodes from stack and 
        // push them in the beginning of the list 
        while (!stk.empty())  
        { 
            push(stk.peek()); 
            stk.pop(); 
        } 
  
        System.out.println("Created DLL is : "); 
        printList(head); 
    } 
  
    // Driver program to test above functions 
    public static void main(String[] args)  
    { 
        // Let us create binary tree as shown in above diagram 
        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.left = new Node(12); 
        tree.root.right.left.right = new Node(13); 
        tree.root.right.right.left = new Node(14); 
        // tree.root.right.right.right = new Node(15); 
  
        tree.spiralLevelOrder(tree.root); 
    } 
} 
  
// This code has been contributed by Mayank Jaiswal(mayank_24) 

Python3

# Python3 program to convert Binary Tree  
# into Doubly Linked List where the nodes  
# are represented spirally. 
      
# Binary tree node  
class newNode:  
  
    # Constructor to create a newNode  
    def __init__(self, data):  
        self.data = data  
        self.left = None
        self.right = None
          
""" Given a reference to the head of a list 
    and a node, inserts the node on the front 
    of the list. """
def push(head_ref, node): 
  
    # Make right of given node as  
    # head and left as None 
    node.right = (head_ref) 
    node.left = None
  
    # change left of head node to 
    # given node 
    if ((head_ref) != None): 
        (head_ref).left = node  
  
    # move the head to point to  
    # the given node 
    (head_ref) = node 
  
# Function to prints contents of DLL 
def printList(node): 
    i = 0
    while (i < len(node)): 
      
        print(node[i].data, end = " ") 
        i += 1
      
""" Function to print corner node at each level """
def spiralLevelOrder(root): 
  
    # Base Case 
    if (root == None): 
        return
  
    # Create an empty deque for doing spiral 
    # level order traversal and enqueue root 
    q = [] 
    q.append(root) 
  
    # create a stack to store Binary  
    # Tree nodes to insert into DLL later 
    stk = [] 
  
    level = 0
    while (len(q)): 
      
        # nodeCount indicates number of 
        # Nodes at current level. 
        nodeCount = len(q)  
          
        # Dequeue all Nodes of current level  
        # and Enqueue all Nodes of next level 
        if (level&1): # odd level 
            while (nodeCount > 0): 
              
                # dequeue node from front &  
                # push it to stack 
                node = q[0] 
                q.pop(0) 
                stk.append(node) 
  
                # insert its left and right children 
                # in the back of the deque 
                if (node.left != None): 
                    q.append(node.left) 
                if (node.right != None): 
                    q.append(node.right) 
  
                nodeCount -= 1
              
        else:     # even level 
          
            while (nodeCount > 0): 
              
                # dequeue node from the back &  
                # push it to stack 
                node = q[-1] 
                q.pop(-1) 
                stk.append(node) 
  
                # inserts its right and left  
                # children in the front of  
                # the deque 
                if (node.right != None): 
                    q.insert(0, node.right) 
                if (node.left != None): 
                    q.insert(0, node.left) 
                nodeCount -= 1
        level += 1
          
    # head pointer for DLL 
    head = [] 
      
    # pop all nodes from stack and push 
    # them in the beginning of the list 
    while (len(stk)): 
      
        head.append(stk[0]) 
        stk.pop(0) 
  
    print("Created DLL is:") 
    printList(head) 
  
# Driver Code 
if __name__ == '__main__': 
      
    """Let us create Binary Tree as  
    shown in above example """
  
    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.left = newNode(12) 
    root.right.left.right = newNode(13) 
    root.right.right.left = newNode(14) 
    #root.right.right.right = newNode(15) 
  
    spiralLevelOrder(root) 
  
# This code is contributed 
# by SHUBHAMSINGH10 

C#

/* C# program to convert Binary Tree into Doubly Linked List  
where the nodes are represented spirally */
using System; 
using System.Collections.Generic; 
  
// A binary tree node 
public class Node  
{ 
    public int data; 
    public Node left, right; 
  
    public Node(int data)  
    { 
        this.data = data; 
        left = right = null; 
    } 
} 
  
public class BinaryTree  
{ 
    Node root; 
    Node head; 
  
    /* Given a reference to a node, 
    inserts the node on the front of the list. */
    void push(Node node)  
    { 
        // Make right of given node as head and left as 
        // NULL 
        node.right = head; 
        node.left = null; 
  
        // change left of head node to given node 
        if (head != null)  
            head.left = node; 
              
        // move the head to point to the given node 
        head = node; 
    } 
  
    // Function to prints contents of DLL 
    void printList(Node node)  
    { 
        while (node != null)  
        { 
            Console.Write(node.data + " "); 
            node = node.right; 
        } 
    } 
  
    /* Function to print corner node at each level */
    void spiralLevelOrder(Node root)  
    { 
        // Base Case 
        if (root == null) 
            return; 
  
        // Create an empty deque for doing spiral 
        // level order traversal and enqueue root 
        LinkedList<Node> q = new LinkedList<Node>(); 
        q.AddFirst(root); 
  
        // create a stack to store Binary Tree nodes 
        // to insert into DLL later 
        Stack<Node> stk = new Stack<Node>(); 
  
        int level = 0; 
        while (q.Count != 0)  
        { 
            // nodeCount indicates number of Nodes 
            // at current level. 
            int nodeCount = q.Count; 
  
            // Dequeue all Nodes of current level and 
            // Enqueue all Nodes of next level 
            if ((level & 1) % 2 != 0) //odd level 
            { 
                while (nodeCount > 0)  
                { 
                    // dequeue node from front & push it to 
                    // stack 
                    Node node = q.First.Value; 
                    q.RemoveFirst(); 
                    stk.Push(node); 
  
                    // insert its left and right children 
                    // in the back of the deque 
                    if (node.left != null) 
                        q.AddLast(node.left); 
                    if (node.right != null) 
                        q.AddLast(node.right); 
  
                    nodeCount--; 
                } 
            }  
            else //even level 
            { 
                while (nodeCount > 0)  
                { 
                    // dequeue node from the back & push it 
                    // to stack 
                    Node node = q.Last.Value; 
                    q.RemoveLast(); 
                    stk.Push(node); 
  
                    // inserts its right and left children 
                    // in the front of the deque 
                    if (node.right != null) 
                        q.AddFirst(node.right); 
                    if (node.left != null) 
                        q.AddFirst(node.left); 
                    nodeCount--; 
                } 
            } 
            level++; 
        } 
  
        // pop all nodes from stack and 
        // push them in the beginning of the list 
        while (stk.Count != 0)  
        { 
            push(stk.Peek()); 
            stk.Pop(); 
        } 
  
        Console.WriteLine("Created DLL is : "); 
        printList(head); 
    } 
  
    // Driver program to test above functions 
    public static void Main(String[] args)  
    { 
        // Let us create binary tree as shown in above diagram 
        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.left = new Node(12); 
        tree.root.right.left.right = new Node(13); 
        tree.root.right.right.left = new Node(14); 
        // tree.root.right.right.right = new Node(15); 
  
        tree.spiralLevelOrder(tree.root); 
    } 
} 
  
/* This code contributed by PrinciRaj1992 */

Javascript

<script> 
   
/* Javascript program to convert Binary Tree into Doubly Linked List  
where the nodes are represented spirally */
  
// A binary tree node 
class Node  
{ 
  constructor(data) 
  { 
      this.data = data; 
      this.left = null; 
      this.right = null; 
  } 
} 
  
var root = null; 
var head = null; 
/* Given a reference to a node, 
inserts the node on the front of the list. */
function push(node)  
{ 
    // Make right of given node as head and left as 
    // NULL 
    node.right = head; 
    node.left = null; 
    // change left of head node to given node 
    if (head != null)  
        head.left = node; 
          
    // move the head to point to the given node 
    head = node; 
} 
// Function to prints contents of DLL 
function printList(node)  
{ 
    while (node != null)  
    { 
        document.write(node.data + " "); 
        node = node.right; 
    } 
} 
/* Function to print corner node at each level */
function spiralLevelOrder(root)  
{ 
    // Base Case 
    if (root == null) 
        return; 
    // Create an empty deque for doing spiral 
    // level order traversal and enqueue root 
    var q = []; 
    q.unshift(root); 
    // create a stack to store Binary Tree nodes 
    // to insert into DLL later 
    var stk = []; 
    var level = 0; 
    while (q.length != 0)  
    { 
        // nodeCount indicates number of Nodes 
        // at current level. 
        var nodeCount = q.length; 
        // Dequeue all Nodes of current level and 
        // Enqueue all Nodes of next level 
        if ((level & 1) % 2 != 0) //odd level 
        { 
            while (nodeCount > 0)  
            { 
                // dequeue node from front & push it to 
                // stack 
                var node = q[0]; 
                q.shift(); 
                stk.push(node); 
                // insert its left and right children 
                // in the back of the deque 
                if (node.left != null) 
                    q.push(node.left); 
                if (node.right != null) 
                    q.push(node.right); 
                nodeCount--; 
            } 
        }  
        else //even level 
        { 
            while (nodeCount > 0)  
            { 
                // dequeue node from the back & push it 
                // to stack 
                var node = q[q.length-1]; 
                q.pop(); 
                stk.push(node); 
                // inserts its right and left children 
                // in the front of the deque 
                if (node.right != null) 
                    q.unshift(node.right); 
                if (node.left != null) 
                    q.unshift(node.left); 
                nodeCount--; 
            } 
        } 
        level++; 
    } 
    // pop all nodes from stack and 
    // push them in the beginning of the list 
    while (stk.length != 0)  
    { 
        push(stk[stk.length-1]); 
        stk.pop(); 
    } 
    document.write("Created DLL is :<br>"); 
    printList(head); 
} 
  
// Driver program to test above functions 
// Let us create binary tree as shown in above diagram 
root = new Node(1); 
root.left = new Node(2); 
root.right = new Node(3); 
root.left.left = new Node(4); 
root.left.right = new Node(5); 
root.right.left = new Node(6); 
root.right.right = new Node(7); 
root.left.left.left = new Node(8); 
root.left.left.right = new Node(9); 
root.left.right.left = new Node(10); 
root.left.right.right = new Node(11); 
// tree.root.right.left.left = new Node(12); 
root.right.left.right = new Node(13); 
root.right.right.left = new Node(14); 
// tree.root.right.right.right = new Node(15); 
spiralLevelOrder(root); 
  
// This code is contributed by itsok. 
  
</script>

Output

Created DLL is:
1 2 3 7 6 5 4 8 9 10 11 13 14

Time Complexity: O(n), as we are using a loop to traverse n times. Where n is the number of nodes in the tree.
Auxiliary Space: O(n), as we are using extra space for dequeue and stack.

A

Aditya Goel

Improve

Previous Article

Construct Binary Tree from String with bracket representation

Convert a Binary Tree to a Circular Doubly Link List

Similar Reads

Convert Binary Tree to Circular Doubly Linked List using Linear extra space

Given a Binary Tree, convert it to a Circular Doubly Linked List. The left and right pointers in nodes are to be used as previous and next pointers, respectively, in the converted Circular Linked List.The order of nodes in the List must be the same as in the order of the given Binary Tree.The first node of Inorder traversal must be the head node of

Convert Binary Tree to Doubly Linked List using Morris Traversal

Given a Binary Tree (BT), convert it to a Doubly Linked List (DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be the same as in Inorder for the given Binary Tree. The first node of Inorder traversal must be the head node of the DLL. Examples: Input

Convert Binary Tree to Doubly Linked List by fixing left and right pointers

Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be the same as in Inorder for the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the

Convert given Binary Tree to Doubly Linked List in Linear time

Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In-Place. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the D

Convert Binary Tree to Doubly Linked List using inorder traversal

Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be the same as in Inorder for the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the

Convert Binary Tree to Doubly Linked List by keeping track of visited node

Given a Binary Tree, The task is to convert it to a Doubly Linked List keeping the same order. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be the same as in Inorder for the given Binary Tree. The first node of Inorder traversal (leftmost node in BT)

Convert a Binary Tree into its Mirror Tree (Invert Binary Tree)

Given a binary tree, the task is to convert the binary tree into its Mirror tree. Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged. Recommended PracticeMirror TreeTry It!The idea is to traverse recursively and swap the right and left subtrees after traversing the subtrees. Follow

Convert Array into Zig-Zag fashion (arr[i-1] < arr[i] > arr[i+1])

Given an array of distinct elements of size N, the task is to rearrange the elements of the array in a zig-zag fashion, i.e., the elements are arranged as smaller, then larger, then smaller, and so on. There can be more than one arrangement that follows the form: arr[0] < arr[1] > arr[2] < arr[3] > arr[4] < ... Examples: Input: N = 7

Extract Leaves of a Binary Tree in a Doubly Linked List

Given a Binary Tree, extract all leaves of it in a Doubly Linked List (DLL). Note that the DLL need to be created in-place. Assume that the node structure of DLL and Binary Tree is same, only the meaning of left and right pointers are different. In DLL, left means previous pointer, and right means next pointer. Let the following be input binary tre

Convert a Binary Tree to a Circular Doubly Link List

Given a Binary Tree, convert it to a Circular Doubly Linked List (In-Place). The left and right pointers in nodes are to be used as previous and next pointers respectively in the converted Circular Linked List.The order of nodes in the List must be the same as in Inorder for the given Binary Tree.The first node of Inorder traversal must be the head

Article Tags :

Practice Tags :

Tree