Level order traversal in spiral form

Last Updated : 15 May, 2025

Given a binary tree and the task is to find the spiral order traversal of the tree and return the list containing the elements.
Spiral order Traversal: Starting from level 0 for root node, for all the even levels we print the node's value from right to left and for all the odd levels we print the node's value from left to right.

Example:

Input: root = [1, 2, 3, 7, 6, 5, 4]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Explanation: Start with root (1), print level 0 (right to left), level 1 (left to right), and continue alternating.
Input: root = [1, 3, 2]

Output: [1, 3, 2]
Explanation: Start with root (1), print level 0 (right to left), then level 1 (left to right)

Input: root = [10, 20, 30, 40, 60]

Output: [10, 20, 30, 60, 40]
Explanation: Start with root (10), print level 0 (right to left), level 1 (left to right), and continue alternating.

Try it on GfG Practice

Using Recursion - O(n) Time and O(h) Space

The idea is to first calculate the height of the tree, then recursively traverse each level and print the level order traversal according to the current level being odd or even.

Follow the below steps to Implement the idea:

1. Initialize Variables:

h: Calculate the height of the binary tree (i.e., the number of levels).
ltr: A boolean flag to control the left-to-right or right-to-left traversal. Initialize it to false.
i: Loop variable to traverse each level from 1 to h.

2. Level-wise Traversal:

Loop from 1 to h (height of the tree).
For each level:
- Call a recursive function to print nodes at the current level (printGivenLevel(tree, level, ltr)).
- After printing each level, toggle the ltr flag (ltr = !ltr), to alternate the direction for the next level.

3. Recursive Function (printGivenLevel(tree, level, ltr)):

Base Case: If the node is NULL, return.
If the current level == 1, print the node's data.
If the level > 1:
- If ltr is true, recursively print the left subtree first, then the right subtree.
- If ltr is false, recursively print the right subtree first, then the left subtree.

4. Toggle the Direction:

After each level, flip the value of ltr to change the direction of traversal for the next level.

C++

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

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int data) {
        this->data = data;
        left = right = nullptr;
    }
};

int height(Node* node) {
    if (node == nullptr)
        return 0;
    int leftHeight = height(node->left);
    int rightHeight = height(node->right);
    return max(leftHeight, rightHeight) + 1;
}

// Main recursive function that stores the
// spiral traversal in vector res.
void getLevel(Node* root, int level, bool ltr, vector<int>& res) {
    if (root == nullptr) return;
    if (level == 1)
        res.push_back(root->data);
    else if (level > 1) {
        if (ltr) {
            getLevel(root->left, level - 1, ltr, res);
            getLevel(root->right, level - 1, ltr, res);
        } else {
            getLevel(root->right, level - 1, ltr, res);
            getLevel(root->left, level - 1, ltr, res);
        }
    }
}

vector<int> findSpiral(Node* root) {
    vector<int> res;
    int h = height(root);
    bool ltr = false;
    for (int i = 1; i <= h; i++) {
        getLevel(root, i, ltr, res);
        ltr = !ltr;
    }
    return res;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(7);
    root->left->right = new Node(6);
    root->right->left = new Node(5);
    root->right->right = new Node(4);

    vector<int> res = findSpiral(root);
    for (int x : res)
        cout << x << " ";
    return 0;
}

Java

import java.util.ArrayList;

// Class representing a node of the binary tree
class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
        left = right = null;
    }
}

class GfG {

    // Function to calculate the height of the binary tree
    static int height(Node node) {
        if (node == null)
            return 0;

        int leftHeight = height(node.left);
        int rightHeight = height(node.right);

        // Height is max of left/right subtree + 1 (for current node)
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // Function to perform spiral (zig-zag) level order traversal
    static ArrayList<Integer> findSpiral(Node root) {
        ArrayList<Integer> result = new ArrayList<>();
        int h = height(root); // Get height of tree

        boolean leftToRight = false; // Direction flag

        // Traverse each level
        for (int level = 1; level <= h; level++) {
            getLevel(root, level, leftToRight, result);
            leftToRight = !leftToRight; 
        }

        return result;
    }

    // Helper function to get nodes at a given level in desired order
    static void getLevel(Node root, int level, boolean leftToRight,
                         ArrayList<Integer> result) {
        if (root == null)
            return;

        if (level == 1) {
            // If it's the current level, add node to result
            result.add(root.data);
        } else {
            // Recur for left and right children in
            // order based on direction
            if (leftToRight) {
                getLevel(root.left, level - 1, leftToRight, result);
                getLevel(root.right, level - 1, leftToRight, result);
            } else {
                getLevel(root.right, level - 1, leftToRight, result);
                getLevel(root.left, level - 1, leftToRight, result);
            }
        }
    }

    // Main function to test the spiral traversal
    public static void main(String[] args) {
        // Creating a binary tree
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(7);
        root.left.right = new Node(6);
        root.right.left = new Node(5);
        root.right.right = new Node(4);

        // Performing spiral traversal
        ArrayList<Integer> res = findSpiral(root);

        // Printing the result
        for (int val : res)
            System.out.print(val + " ");
    }
}

Python

#include <iostream>
#include <vector>

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def height(node):
    if node is None:
        return 0
    leftHeight = height(node.left)
    rightHeight = height(node.right)
    return max(leftHeight, rightHeight) + 1


def findSpiral(root):
    res = []
    h = height(root)
    ltr = False
    for i in range(1, h + 1):
        getLevel(root, i, ltr, res)
        ltr = not ltr
    return res

# Main recursive function that stores the
# spiral traversal in list res.
def getLevel(root, level, ltr, res):
    if root is None:
        return
    if level == 1:
        res.append(root.data)
    elif level > 1:
        if ltr:
            getLevel(root.left, level - 1, ltr, res)
            getLevel(root.right, level - 1, ltr, res)
        else:
            getLevel(root.right, level - 1, ltr, res)
            getLevel(root.left, level - 1, ltr, res)

if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(7)
    root.left.right = Node(6)
    root.right.left = Node(5)
    root.right.right = Node(4)

    res = findSpiral(root)
    for x in res:
        print(x, end=' ')

C#

using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;

    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

class GfG {
    static int Height(Node node) {
        if (node == null)
            return 0;
        int leftHeight = Height(node.left);
        int rightHeight = Height(node.right);
        return Math.Max(leftHeight, rightHeight) + 1;
    }

    static List<int> findSpiral(Node root) {
        List<int> res = new List<int>();
        int h = Height(root);
        bool ltr = false;
        for (int i = 1; i <= h; i++) {
            getLevel(root, i, ltr, res);
            ltr = !ltr;
        }
        return res;
    }

    static void getLevel(Node root, int level, bool ltr, List<int> res) {
        if (root == null) return;
        if (level == 1)
            res.Add(root.data);
        else if (level > 1) {
            if (ltr) {
                getLevel(root.left, level - 1, ltr, res);
                getLevel(root.right, level - 1, ltr, res);
            } else {
                getLevel(root.right, level - 1, ltr, res);
                getLevel(root.left, level - 1, ltr, res);
            }
        }
    }

    public static void Main() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(7);
        root.left.right = new Node(6);
        root.right.left = new Node(5);
        root.right.right = new Node(4);

        List<int> res = findSpiral(root);
        foreach (int x in res)
            Console.Write(x + " ");
    }
}

JavaScript

class Node {
    constructor(data) {
        this.data = data;
        this.left = this.right = null;
    }
}

function height(node) {
    if (node === null) return 0;
    let leftHeight = height(node.left);
    let rightHeight = height(node.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

function findSpiral(root) {
    let res = [];
    let h = height(root);
    let ltr = false;
    for (let i = 1; i <= h; i++) {
        getLevel(root, i, ltr, res);
        ltr = !ltr;
    }
    return res;
}

function getLevel(root, level, ltr, res) {
    if (root === null) return;
    if (level === 1)
        res.push(root.data);
    else if (level > 1) {
        if (ltr) {
            getLevel(root.left, level - 1, ltr, res);
            getLevel(root.right, level - 1, ltr, res);
        } else {
            getLevel(root.right, level - 1, ltr, res);
            getLevel(root.left, level - 1, ltr, res);
        }
    }
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(7);
root.left.right = new Node(6);
root.right.left = new Node(5);
root.right.right = new Node(4);

const res = findSpiral(root);
console.log(res.join(' '));

Output

1 2 3 4 5 6 7

Time Complexity: O(n)
Auxiliary Space: O(h), for recursive stack space.

Using Two Stacks - O(n) Time and O(n) Space

The idea is to use two stacks. One stack s1 is used to traverse the current level and the other stack s2 is used to store the nodes of next level.

1. Initialize two stackss1 and s2, and push the root of the tree into s1.

2. While loop: Continue as long as either s1 or s2 contains nodes.

Traverse s1:
- Pop the top node from s1, and add to the result.
- If the node has a right child, push it to s2.
- If the node has a left child, push it to s2.
Traverse s2:
- Pop the top node from s2, and add to the result
- If the node has a left child, push it to s1.
- If the node has a right child, push it to s1.

3. Alternating Directions: This traversal alternates as we first push right in s2 and first push left in s1.

C++

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

struct Node {
    int data;
    Node *left, *right;

    Node(int val) {
        data = val;
        left = right = nullptr;
    }
};

vector<int> findSpiral(Node* root) {
    vector<int> res;
    if (root == nullptr)
        return res;

    stack<Node*> s1; // Current level
    stack<Node*> s2; // Next level

    s1.push(root);

    while (!s1.empty() || !s2.empty()) {

        // Print nodes of current level from s1
        // and push nodes of next level to s2
        while (!s1.empty()) {
            Node* temp = s1.top();
            s1.pop();
            res.push_back(temp->data);

            if (temp->right)
                s2.push(temp->right);
            if (temp->left)
                s2.push(temp->left);
        }

        // Print nodes of current level from s2
        // and push nodes of next level to s1
        while (!s2.empty()) {
            Node* temp = s2.top();
            s2.pop();
            res.push_back(temp->data);

            if (temp->left)
                s1.push(temp->left);
            if (temp->right)
                s1.push(temp->right);
        }
    }
    return res;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(7);
    root->left->right = new Node(6);
    root->right->left = new Node(5);
    root->right->right = new Node(4);

    vector<int> res = findSpiral(root);

    for (int x : res)
        cout << x << " ";

    return 0;
}

Java

import java.util.*;

// Class representing a node in the binary tree
class Node {
    int data;
    Node left, right;

    Node(int val) {
        data = val;
        left = right = null;
    }
}

class GfG {

    // Function to perform spiral (zigzag) traversal of a binary tree
    static ArrayList<Integer> findSpiral(Node root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null)
            return res;

        Stack<Node> s1 = new Stack<>(); 
        Stack<Node> s2 = new Stack<>(); 
        
        // Push first level to first stack 's1'
        s1.push(root);

        // Keep printing while any of the stacks has some nodes
        while (!s1.isEmpty() || !s2.isEmpty()) {

            // Print nodes of current level from s1 and 
            // push nodes of next level to s2
            while (!s1.isEmpty()) {
                Node temp = s1.pop();
                res.add(temp.data);

                // Note that right child is pushed before left
                if (temp.right != null)
                    s2.push(temp.right);
                if (temp.left != null)
                    s2.push(temp.left);
            }

            // Print nodes of current level from s2 and 
            // push nodes of next level to s1
            while (!s2.isEmpty()) {
                Node temp = s2.pop();
                res.add(temp.data);

                // Note that left child is pushed before right
                if (temp.left != null)
                    s1.push(temp.left);
                if (temp.right != null)
                    s1.push(temp.right);
            }
        }

        return res;
    }

    // Driver method to test the above logic
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(7);
        root.left.right = new Node(6);
        root.right.left = new Node(5);
        root.right.right = new Node(4);

        ArrayList<Integer> res = findSpiral(root);
        for (int x : res)
            System.out.print(x + " ");
    }
}

Python

class Node:
    def __init__(self, val):
        self.data = val
        self.left = self.right = None


def findSpiral(root):
    res = []
    if root is None:
        return res

    s1 = []  # Current level
    s2 = []  # Next Level

    # Push first level to first stack 's1'
    s1.append(root)

    # Keep printing while any of the stacks has some nodes
    while s1 or s2:
        
        # Print nodes of current level from s1
        # and push nodes of next level to s2
        while s1:
            temp = s1.pop()
            res.append(temp.data)

            # Note that right child is pushed before left
            if temp.right:
                s2.append(temp.right)
            if temp.left:
                s2.append(temp.left)

        # Print nodes of current level from s2 
        # and push nodes of next level to s1
        while s2:
            temp = s2.pop()
            res.append(temp.data)

            # Note that left child is pushed before right
            if temp.left:
                s1.append(temp.left)
            if temp.right:
                s1.append(temp.right)

    return res

if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(7)
    root.left.right = Node(6)
    root.right.left = Node(5)
    root.right.right = Node(4)
    res = findSpiral(root)
    print(' '.join(map(str, res)))

C#

using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;
    public Node(int val) {
        data = val;
        left = right = null;
    }
}

class GfG{
    
    public static List<int> findSpiral(Node root) {
        List<int> res = new List<int>();
        if (root == null)
            return res;

        Stack<Node> s1 = new Stack<Node>(); // Current level
        Stack<Node> s2 = new Stack<Node>(); // Next Level

        // Push first level to first stack 's1'
        s1.Push(root);

        // Keep printing while any of the stacks has some nodes
        while (s1.Count > 0 || s2.Count > 0) {
            
            // Print nodes of current level from s1 
            // and push nodes of next level to s2
            while (s1.Count > 0) {
                Node temp = s1.Pop();
                res.Add(temp.data);

                // Note that right child is pushed before left
                if (temp.right != null)
                    s2.Push(temp.right);
                if (temp.left != null)
                    s2.Push(temp.left);
            }

            // Print nodes of current level from s2 
            // and push nodes of next level to s1
            while (s2.Count > 0) {
                Node temp = s2.Pop();
                res.Add(temp.data);

                // Note that left child is pushed before right
                if (temp.left != null)
                    s1.Push(temp.left);
                if (temp.right != null)
                    s1.Push(temp.right);
            }
        }
        return res;
    }

    static void Main() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(7);
        root.left.right = new Node(6);
        root.right.left = new Node(5);
        root.right.right = new Node(4);
        List<int> res = findSpiral(root);
        Console.WriteLine(string.Join(" ", res));
    }
}

JavaScript

class Node {
    constructor(val) {
        this.data = val;
        this.left = this.right = null;
    }
}

function findSpiral(root) {
    const res = [];
    if (root === null)
        return res;

    const s1 = [];
    const s2 = [];

    // Push first level to first stack 's1'
    s1.push(root);

    // Keep printing while any of the stacks has some nodes
    while (s1.length > 0 || s2.length > 0) {
        
        // Print nodes of current level from s1 and 
        // push nodes of next level to s2
        while (s1.length > 0) {
            const temp = s1.pop();
            res.push(temp.data);

            // Note that right child is pushed before left
            if (temp.right)
                s2.push(temp.right);
            if (temp.left)
                s2.push(temp.left);
        }

        // Print nodes of current level from 
        // s2 and push nodes of next level to s1
        while (s2.length > 0) {
            const temp = s2.pop();
            res.push(temp.data);

            // Note that left child is pushed before right
            if (temp.left)
                s1.push(temp.left);
            if (temp.right)
                s1.push(temp.right);
        }
    }
    return res;
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(7);
root.left.right = new Node(6);
root.right.left = new Node(5);
root.right.right = new Node(4);
const res = findSpiral(root);
console.log(res.join(' '));

Output

1 2 3 4 5 6 7

Time Complexity: O(n), where n is the number of nodes in the binary tree.
Auxiliary Space: O(n), for storing the nodes in the stack.

Using Deque - O(n) Time and O(n) Space

The idea is to use Doubly Ended Queues, then push and pop the nodes from each end in alternate order.

To implement the idea:

1. Initialize a deque dq and push the root of the binary tree into it.

2. Set reverse = true.

3.While the deque is not empty, repeat the following:

Set n = dq.size().
If reverse is false, do the following:
- For each node in the deque, pop from the front and print the node's value.
- If the left child exists, push it to the back of the deque.
- If the right child exists, push it to the back of the deque.
- After processing the level, set reverse = !reverse.
If reverse is true, do the following:
- For each node in the deque, pop from the back and print the node's value.
- If the right child exists, push it to the front of the deque.
- If the left child exists, push it to the front of the deque.
- After processing the level, set reverse = !reverse.

C++

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int x) {
        data = x;
        left = nullptr;
        right = nullptr;
    }
};

vector<int> findSpiral(Node* root)
{
    vector<int> res;
    if (!root) return res;

    deque<Node*> dq;
    dq.push_back(root);

    bool reverse = true;

    while (!dq.empty()) {
        int n = dq.size();

        while (n--) {
            
            // Push right first if reverse is true
            if (reverse) {
                Node* curr = dq.back();
                dq.pop_back();
                res.push_back(curr->data);

                if (curr->right) dq.push_front(curr->right);
                if (curr->left)  dq.push_front(curr->left);
            }
            
            // Else push left first
            else {
                Node* curr = dq.front();
                dq.pop_front();
                res.push_back(curr->data);

                if (curr->left)  dq.push_back(curr->left);
                if (curr->right) dq.push_back(curr->right);
            }
        }

        reverse = !reverse;
    }

    return res;
}

int main()
{
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(7);
    root->left->right = new Node(6);
    root->right->left = new Node(5);
    root->right->right = new Node(4);

    vector<int> res = findSpiral(root);

    for (int x : res)
        cout << x << "  ";

    return 0;
}

Java

import java.util.*;

// Node class representing a node of the binary tree
class Node {
    int data;
    Node left, right;

    Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GfG{

    // Function to return the spiral (zigzag) traversal of the binary tree
    static ArrayList<Integer> findSpiral(Node root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Deque<Node> dq = new ArrayDeque<>();
        dq.add(root);

        // 'reverse' indicates direction of traversal at current level
        boolean reverse = true;

        // Loop until all levels are processed
        while (!dq.isEmpty()) {
            int n = dq.size();

            // Process all nodes at current level
            while (n-- > 0) {
                // If reverse is true, process from right to left
                if (reverse) {
                    Node curr = dq.removeLast();
                    res.add(curr.data);

                    // Add right child first, then left child 
                    // to the front of deque
                    if (curr.right != null) dq.addFirst(curr.right);
                    if (curr.left != null) dq.addFirst(curr.left);
                } 
                // Else process from left to right
                else {
                    Node curr = dq.removeFirst();
                    res.add(curr.data);

                    // Add left child first, then right child to
                    // the end of deque
                    if (curr.left != null) dq.addLast(curr.left);
                    if (curr.right != null) dq.addLast(curr.right);
                }
            }

            // Toggle direction for next level
            reverse = !reverse;
        }

        return res;
    }

    // Driver code to test the spiral traversal function
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(7);
        root.left.right = new Node(6);
        root.right.left = new Node(5);
        root.right.right = new Node(4);

        ArrayList<Integer> res = findSpiral(root);

        // Print the result of spiral traversal
        for (int x : res)
            System.out.print(x + "  ");
    }
}

Python

from collections import deque

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

def findSpiral(root):
    res = []
    if not root:
        return res

    dq = deque([root])
    reverse = True

    while dq:
        n = len(dq)

        for _ in range(n):
            
            # Push right first if reverse is true
            if reverse:
                curr = dq.pop()
                res.append(curr.data)

                if curr.right:
                    dq.appendleft(curr.right)
                if curr.left:
                    dq.appendleft(curr.left)
            else:
                curr = dq.popleft()
                res.append(curr.data)

                if curr.left:
                    dq.append(curr.left)
                if curr.right:
                    dq.append(curr.right)

        reverse = not reverse

    return res

if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(7)
    root.left.right = Node(6)
    root.right.left = Node(5)
    root.right.right = Node(4)

    res = findSpiral(root)
    print('  '.join(map(str, res)))

C#

using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GfG {

    static List<int> findSpiral(Node root) {
        List<int> res = new List<int>();
        if (root == null) return res;
        
        // We are Using LinkList on place of the Deque
        LinkedList<Node> dq = new LinkedList<Node>();  
        dq.AddLast(root);

        bool reverse = true;

        while (dq.Count > 0) {
            int n = dq.Count;

            for (int i = 0; i < n; i++) {

                if (reverse) {
                    Node curr = dq.Last.Value;
                    dq.RemoveLast();
                    res.Add(curr.data);

                    if (curr.right != null) dq.AddFirst(curr.right);
                    if (curr.left != null) dq.AddFirst(curr.left);
                } else {
                    Node curr = dq.First.Value;
                    dq.RemoveFirst();
                    res.Add(curr.data);

                    if (curr.left != null) dq.AddLast(curr.left);
                    if (curr.right != null) dq.AddLast(curr.right);
                }
            }

            reverse = !reverse;
        }

        return res;
    }

    static void Main() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(7);
        root.left.right = new Node(6);
        root.right.left = new Node(5);
        root.right.right = new Node(4);

        List<int> res = findSpiral(root);

        foreach (int x in res)
            Console.Write(x + "  ");
    }
}

JavaScript

// Node class for the binary tree
class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

// Node class for deque
class DequeNode {
    constructor(value) {
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

// Custom Deque class (Doubly Linked List)
class Deque {
    constructor() {
        this.front = null;
        this.rear = null;
        this.length = 0;
    }

    isEmpty() {
        return this.length === 0;
    }

    pushFront(value) {
        const node = new DequeNode(value);
        if (this.isEmpty()) {
            this.front = this.rear = node;
        } else {
            node.next = this.front;
            this.front.prev = node;
            this.front = node;
        }
        this.length++;
    }

    pushBack(value) {
        const node = new DequeNode(value);
        if (this.isEmpty()) {
            this.front = this.rear = node;
        } else {
            node.prev = this.rear;
            this.rear.next = node;
            this.rear = node;
        }
        this.length++;
    }

    popFront() {
        if (this.isEmpty()) return null;
        const node = this.front;
        if (this.front === this.rear) {
            this.front = this.rear = null;
        } else {
            this.front = this.front.next;
            this.front.prev = null;
        }
        this.length--;
        return node.value;
    }

    popBack() {
        if (this.isEmpty()) return null;
        const node = this.rear;
        if (this.front === this.rear) {
            this.front = this.rear = null;
        } else {
            this.rear = this.rear.prev;
            this.rear.next = null;
        }
        this.length--;
        return node.value;
    }

    size() {
        return this.length;
    }
}

// Function to perform spiral (zigzag) traversal using custom deque
function findSpiral(root) {
    const res = [];
    if (!root) return res;

    const dq = new Deque();
    dq.pushBack(root);
    let reverse = true;

    while (!dq.isEmpty()) {
        let n = dq.size();

        while (n-- > 0) {
            if (reverse) {
                const curr = dq.popBack();
                res.push(curr.data);

                // Right child is pushed first, then left
                if (curr.right) dq.pushFront(curr.right);
                if (curr.left) dq.pushFront(curr.left);
            } else {
                const curr = dq.popFront();
                res.push(curr.data);

                // Left child is pushed first, then right
                if (curr.left) dq.pushBack(curr.left);
                if (curr.right) dq.pushBack(curr.right);
            }
        }

        reverse = !reverse;
    }

    return res;
}

// Example usage
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(7);
root.left.right = new Node(6);
root.right.left = new Node(5);
root.right.right = new Node(4);

const res = findSpiral(root);
console.log(res.join('  '));

Output

1  2  3  4  5  6  7

Time Complexity: O(n), where n is the number of nodes in the binary tree.
Auxiliary Space: O(n), for storing the nodes in the Deque.

Comment

Article Tags:

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem