Binary Tree Zigzag Level Order Traversal Editorial

Practice Problem Link: Binary Tree Zigzag Level Order Traversal

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

There are different ways to traverse a binary tree. The zigzag level order traversal of a binary tree covers all the nodes of the tree such that each level is traversed left to right or right to left alternatively.

Given the root node of a binary tree, return an array depicting the zigzag level order traversal.

Note: The first level is traversed left to right.

Approach

The approach is quite similar to normal level order traversal. Here we will use a stack to store the nodes of the level which has to be traversed from right to left.

• Perform a level order traversal.
• For traversing from left to right in a level, simply add all the encountered nodes to the answer array. Also, store the nodes of the next level in a stack.
• For traversing from right to left, pop each node from the stack that was stored in the previous step and add them to the answer array.
• Return the answer array.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

vector<int> zigzagLevelOrderTraversal(Node* root) {
    vector<int> traversal;
	queue<Node*> treeNodes;
	stack<Node*> currLevelNodes;
	treeNodes.push(root);
	int leftToRight = 1;
	while (!treeNodes.empty()) {
		if (leftToRight == 1) {
			int n = treeNodes.size();
			for (int i = 0; i < n; i++) {
				Node* currentNode = treeNodes.front();
				treeNodes.pop();
				traversal.push_back(currentNode->data);
				if (currentNode->left != NULL) {
					treeNodes.push(currentNode->left);
					currLevelNodes.push(currentNode->left);
				}
				if (currentNode->right != NULL) {
					treeNodes.push(currentNode->right);
					currLevelNodes.push(currentNode->right);
				}
			}
		} else {
			int n = treeNodes.size();
			for (int i = 0; i < n; i++) {
				Node* currentNode = treeNodes.front();
				treeNodes.pop();
				traversal.push_back(currLevelNodes.top()->data);
				currLevelNodes.pop();
				if (currentNode->left != NULL) {
					treeNodes.push(currentNode->left);
				}
				if (currentNode->right != NULL) {
					treeNodes.push(currentNode->right);
				}
			}
		}
		leftToRight = 1 - leftToRight;
	}
	return traversal;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	
	int[] zigzagLevelOrderTraversal(Node root) {
	    List<Integer> traversal = new ArrayList<Integer> ();
		Queue<Node> treeNodes = new LinkedList<Node> ();
		Stack<Node> currLevelNodes = new Stack<Node> ();
		treeNodes.add(root);
		int leftToRight = 1;
		while (!treeNodes.isEmpty()) {
			if (leftToRight == 1) {
				int n = treeNodes.size();
				for (int i = 0; i < n; i++) {
					Node currentNode = treeNodes.peek();
					treeNodes.poll();
					traversal.add(currentNode.data);
					if (currentNode.left != null) {
						treeNodes.add(currentNode.left);
						currLevelNodes.push(currentNode.left);
					}
					if (currentNode.right != null) {
						treeNodes.add(currentNode.right);
						currLevelNodes.push(currentNode.right);
					}
				}
			} else {
				int n = treeNodes.size();
				for (int i = 0; i < n; i++) {
					Node currentNode = treeNodes.peek();
					treeNodes.poll();
					traversal.add(currLevelNodes.peek().data);
					currLevelNodes.pop();
					if (currentNode.left != null) {
						treeNodes.add(currentNode.left);
					}
					if (currentNode.right != null) {
						treeNodes.add(currentNode.right);
					}
				}
			}
			leftToRight = 1 - leftToRight;
		}
		int[] temp = new int[traversal.size()];
		for (int i = 0; i < traversal.size(); i++) {
			temp[i] = traversal.get(i);
		}
		return temp;
	}
}

Improved Approach

Instead of using a separate stack and queue, we can instead use a single deque.

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

vector<int> zigzagLevelOrderTraversal(Node* root) {
    // add your logic here
    deque<Node*> deque;
    vector<int> ans;

    deque.push_back(root);
    ans.push_back(root->data);
    Node* temp;
   
    int level = 1;
                
    while (!deque.empty()) {
        int n = deque.size();
 
        for (int i = 0; i < n; i++) {
            if (level%2 == 0) {
                temp = deque.back();
                deque.pop_back();
                if (temp->left) {
                    deque.push_front(temp->left);
                    ans.push_back(temp->left->data);
                }
                if (temp->right) {
                    deque.push_front(temp->right);
                    ans.push_back(temp->right->data);
                }
            }
            else {
                temp = deque.front();
                deque.pop_front();
                if (temp->right) {
                    deque.push_back(temp->right);
                    ans.push_back(temp->right->data);
                }
                if (temp->left) {
                    deque.push_back(temp->left);
                    ans.push_back(temp->left->data);
                }
            }
        }
        level++;
    }
    return ans;
}

Java

class Solution {
    /* This is the Node class definition
    
    class Node {
        public Node left;
        public Node right;
        public int data;

        public Node(int data) {
            this.data = data;
        }
    }
    */
    
    int[] zigzagLevelOrderTraversal(Node root) {
        // add your logic here
        Deque<Node> deque = new LinkedList<Node>();
        List<Integer> ans = new ArrayList<Integer>();

        deque.add(root);
        ans.add(root.data);
        Node temp;

        int level = 1;

        while (!deque.isEmpty()) {
            int n = deque.size();

            for (int i = 0; i < n; i++) {
                if (level%2 == 0) {
                    temp = deque.peekLast();
                    deque.removeLast();
                    if (temp.left != null) {
                        deque.addFirst(temp.left);
                        ans.add(temp.left.data);
                    }
                    if (temp.right != null) {
                        deque.addFirst(temp.right);
                        ans.add(temp.right.data);
                    }
                } else {
                    temp = deque.peekFirst();
                    deque.removeFirst();
                    if (temp.right != null) {
                        deque.addLast(temp.right);
                        ans.add(temp.right.data);
                    }
                    if (temp.left != null) {
                        deque.addLast(temp.left);
                        ans.add(temp.left.data);
                    }
                }
            }
            level++;
        }
        return ans.stream().mapToInt(i -> i).toArray();
    }
}