Binary Tree Zigzag Level Order Traversal

class Solution {
public:
    vector<vector<int>> levelOrderZigzag(TreeNode* root) {
        if (!root) return {};
        vector<deque<int>> intermediate;
        function<void(TreeNode*, int)> traverse = [&](TreeNode* current, int depth) {
            if (depth >= intermediate.size()) {
                intermediate.emplace_back(deque<int>(1, current->val));
            } else {
                if (depth % 2 == 0)
                    intermediate[depth].push_back(current->val);
                else
                    intermediate[depth].push_front(current->val);
            }
            if (current->left) traverse(current->left, depth + 1);
            if (current->right) traverse(current->right, depth + 1);
        };
        traverse(root, 0);
        vector<vector<int>> ordered_results;
        for (auto layer : intermediate) {
            ordered_results.push_back(vector<int>{layer.begin(), layer.end()});
        }
        return ordered_results;
    }
};

The provided C++ solution implements a zigzag level order traversal of a binary tree. This traversal type is a variation of the traditional breadth-first search (BFS), where the nodes at each level of the tree are visited in alternating order. Here’s a breakdown of how the solution approaches the problem:

1. Check if the root node is null and return an empty vector if true, as there are no nodes to traverse.

2. Initialize a deque (double-ended queue) to facilitate the zigzag ordering. Here, elements can be added or removed from both ends efficiently, which is crucial for this traversal's alternating behavior.

3. Define a recursive lambda function named traverse to traverse the tree nodes. This function:

   • Checks if the current depth matches the size of the intermediate deque. If true, it initializes a new deque with the current node's value.
   • Determines the order to insert the current node's value based on the depth's parity. If the depth is even, it inserts at the end, otherwise at the front.
   • Recursively calls itself for the left and right children of the current node if they exist.

4. Initiate the recursive traversal with the root node starting at depth 0.

5. After completing the depth-based traversal and building the intermediate deque, convert each deque into a vector and store them in ordered_results to maintain the required structure.

6. Finally, return ordered_results, which contains the zigzag level order traversal of the binary tree.

Overall, this solution leverages the properties of deque combined with recursive depth-first search (DFS) to achieve the desired zigzag traversal, ensuring that each tree level is processed according to its corresponding order requirement.

class Solution {
    private void zigzagTraversal(TreeNode current, int depth, List<List<Integer>> output) {
        if (depth >= output.size()) {
            LinkedList<Integer> newLayer = new LinkedList<>();
            newLayer.add(current.val);
            output.add(newLayer);
        } else {
            if (depth % 2 == 0) output.get(depth).add(current.val);
            else output.get(depth).add(0, current.val);
        }

        if (current.left != null) zigzagTraversal(current.left, depth + 1, output);
        if (current.right != null) zigzagTraversal(current.right, depth + 1, output);
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> output = new ArrayList<List<Integer>>();
        if (root != null) {
            zigzagTraversal(root, 0, output);
        }
        return output;
    }
}

This solution implements the Zigzag Level Order Traversal of a binary tree using Java. The traversal is achieved by using a recursive method to explore the tree depth-first.

• The zigzagLevelOrder method initializes an empty list output to hold lists of integers, representing the levels of the tree.
• If the tree's root is not null, the zigzagTraversal method is called with the root node, a starting depth of 0, and the output list.
• In zigzagTraversal, the method first checks if the current depth exceeds or matches the size of the output. If it does, it creates a new LinkedList, adds the current node's value, and appends this list to output.
• For existing levels in output, nodes' values are added to either the beginning or end of the list depending on the current depth, exploiting the LinkedList properties for efficient inserts at both ends.
• This insertion order creates the zigzag pattern, where values at even depths are added to the end, and values at odd depths are added to the beginning of the lists.
• The recursion continues to the node's left and right children, increasing the depth counter by one each time.

This process continues until all nodes have been visited, resulting in the output list containing the zigzag level order traversal of the binary tree. Make sure the TreeNode class is defined with attributes val, left, and right before implementing this method. This implementation needs additional handling for different input sizes and types to ensure robustness.

typedef struct DoublyLinkedNode {
    int data;
    struct DoublyLinkedNode *nextPtr;
    struct DoublyLinkedNode *prevPtr;
} DoublyLinkedNode;

typedef struct DoubleEndedQueue {
    DoublyLinkedNode *front;
    DoublyLinkedNode *back;
    int count;
} DoubleEndedQueue;

DoubleEndedQueue *initializeDeque() {
    DoubleEndedQueue *queue = (DoubleEndedQueue *)malloc(sizeof(DoubleEndedQueue));
    if (!queue) return NULL;
    queue->front = queue->back = NULL;
    queue->count = 0;
    return queue;
}

void insertFront(DoubleEndedQueue *queue, int data) {
    DoublyLinkedNode *node = (DoublyLinkedNode *)malloc(sizeof(DoublyLinkedNode));
    if (!node) return;
    node->data = data;
    node->nextPtr = queue->front;
    node->prevPtr = NULL;
    if (queue->front)
        queue->front->prevPtr = node;
    else
        queue->back = node;
    queue->front = node;
    queue->count++;
}

void insertBack(DoubleEndedQueue *queue, int data) {
    DoublyLinkedNode *node = (DoublyLinkedNode *)malloc(sizeof(DoublyLinkedNode));
    if (!node) return;
    node->data = data;
    node->nextPtr = NULL;
    node->prevPtr = queue->back;
    if (queue->back)
        queue->back->nextPtr = node;
    else
        queue->front = node;
    queue->back = node;
    queue->count++;
}

void destroyDeque(DoubleEndedQueue *queue) {
    DoublyLinkedNode *current = queue->front, *temp;
    while (current) {
        temp = current;
        current = current->nextPtr;
        free(temp);
    }
    free(queue);
}

void depthFirstSearch(struct TreeNode *node, int depth, DoubleEndedQueue **levelQueues, int *highestLevel) {
    if (!node) return;
    if (depth > *highestLevel) {
        *highestLevel = depth;
        levelQueues[depth] = initializeDeque();
    }
    if (depth % 2 == 0)
        insertBack(levelQueues[depth], node->val);
    else
        insertFront(levelQueues[depth], node->val);

    depthFirstSearch(node->left, depth + 1, levelQueues, highestLevel);
    depthFirstSearch(node->right, depth + 1, levelQueues, highestLevel);
}

int **zigzagTraversal(struct TreeNode *root, int *returnSize, int **columnSizes) {
    DoubleEndedQueue *levelQueues[1000];
    int highestLevel = -1;
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    depthFirstSearch(root, 0, levelQueues, &highestLevel);
    *returnSize = highestLevel + 1;
    int **result = malloc(*returnSize * sizeof(int *));
    *columnSizes = malloc(*returnSize * sizeof(int));

    for (int i = 0; i <= highestLevel; i++) {
        (*columnSizes)[i] = levelQueues[i]->count;
        result[i] = malloc(levelQueues[i]->count * sizeof(int));
        DoublyLinkedNode *current = levelQueues[i]->front;
        for (int j = 0; j < levelQueues[i]->count; j++) {
            result[i][j] = current->data;
            current = current->nextPtr;
        }
        destroyDeque(levelQueues[i]);
    }
    return result;
}

To tackle the problem of Zigzag Level Order Traversal of a binary tree using C, the solution employs a combination of custom data structures and a depth-first traversal approach to capture the zigzag sequence.

Custom Data Structures Used:

• DoublyLinkedNode: A node structure for the doubly linked list that holds integer data and pointers to the next and previous nodes.
• DoubleEndedQueue: This structure manages a double-ended queue (deque) with pointers to the front and back nodes, along with a count of the nodes.

Key Functions Implemented:

• initializeDeque: Sets up an empty deque.
• insertFront and insertBack: Functions for inserting data at the front or back of the deque, essential for the zigzag pattern.
• destroyDeque: Frees up the memory used by the deque.

Traversal and Construction Logic:

• depthFirstSearch: A recursive function that performs a depth-first traversal of the binary tree. Depending on the depth, nodes' values are inserted from left to right or right to left, facilitated by insertBack and insertFront.
• zigzagTraversal: This function sets up infrastructure for the traversal, like an array of levelQueues to hold nodes' values at each depth, and then uses depthFirstSearch to populate these queues according to the zigzag order.

Result Compilation:

• After the depth-first traversal, zigzagTraversal iterates through each levelQueues to compile the final zigzag order into a 2D array. Each level's results are accessed in order and copied into this array, after which the deques for each level are destroyed to free memory.

This approach efficiently manages memory and ensures that elements are added in a zigzag fashion by alternating the direction of insertion into the deques based on the current level's parity.

/* Definition for a binary tree node.
 * function TreeNode(value, left, right) {
 *     this.value = (value===undefined ? 0 : value)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var zigzagTraversal = function (root) {
    if (!root) {
        return [];
    }
    let output = [];
    let traverse = function (node, level) {
        if (level >= output.length) {
            output.push([node.value]);
        } else {
            if (level % 2 == 0) output[level].push(node.value);
            else output[level].unshift(node.value);
        }
        if (node.left) traverse(node.left, level + 1);
        if (node.right) traverse(node.right, level + 1);
    };
    traverse(root, 0);
    return output;
};

This solution addresses the problem of performing a zigzag level order traversal on a binary tree using JavaScript. The code defines a function zigzagTraversal that takes the root of a binary tree as input and returns the values of the nodes in a zigzag order across levels.

• Initiate the traversal by checking if the root is null. If it is, return an empty array indicating there are no nodes to traverse.
• Declare an array output to store the values of nodes for each level.
• Define a helper function traverse that takes a current node and its corresponding level in the tree as arguments.
• Within the traverse function:
  • Ensure the current tree level exists in the output array. If not, initialize it with an array containing the current node's value.
  • Depending on whether the current level is even or odd, append or prepend the node's value to the corresponding sub-array in output. This ensures zigzag ordering.
  • Recursively call traverse for the left and right child nodes if they exist, increasing the level count by one each time to move deeper into the tree levels.
• Start the traversal process by calling traverse(root, 0).
• Finally, return the output array which will contain the zigzag level order traversal of the tree's nodes.

This approach efficiently handles the traversal and ordering of a binary tree's nodes in a zigzag manner, leveraging recursion and conditional logic based on the tree's level to manipulate the insertion order of node values.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque

class Solution:
    def zigzagTraversal(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        output = []

        def traverse(node: TreeNode, depth: int) -> None:
            if depth >= len(output):
                output.append(deque([node.val]))
            else:
                if depth % 2 == 0:
                    output[depth].append(node.val)
                else:
                    output[depth].appendleft(node.val)

            for child in [node.left, node.right]:
                if child:
                    traverse(child, depth + 1)

        # Start the DFS zigzag traversal from the root
        traverse(root, 0)

        return output

This article explains the implementation of a Binary Tree Zigzag Level Order Traversal in Python. The zigzag level order traversal of a binary tree is a unique method where the nodes at each level are collected alternately from left to right and then right to left. To achieve this, you will use a BFS (Breadth-First Search) approach leveraging Python's deque for efficient append operations at both ends of the deque.

The given code provides a clear example of how to implement the zigzag traversal for a binary tree:

• Begin by defining a helper function, traverse, which accepts a node and the depth of that node from the root.
• Ensure the base condition where if the tree root is None, return an empty list.
• The output list stores each level's values. For each node, check whether the current depth is even or odd:
  • If the depth is even, add the node's value to the end of the corresponding deque.
  • If the depth is odd, add the node's value to the front.
• Use a recursive approach to traverse every child of the current node, incrementing the depth by 1 each time.
• At the beginning of the function, invoke the traverse function starting from the root at depth 0.
• Convert each deque in the output to a list before returning it to match the required output format.

Ensure you have the TreeNode class defined elsewhere in your code, as this class outlines the structure of the nodes in your binary tree, with each node containing its value and pointers to its left and right children. This implementation is an efficient solution to perform a zigzag traversal on a binary tree, offering a time complexity proportional to the number of nodes in the tree, as each node and each level is processed once.