Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

tree
traversal
zigzag

What is zigzag tree traversal?

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Answers Code

ZigZag is a tree traversal algorithm that traverses the nodes in each level from left to right and then from right to left.

Take a look at the tree below:

svg viewer

The zigzag traversal of this tree would be 4,5,2,1,34, 5, 2, 1, 3. The first level, which is just the root node, needs to be traversed from left to right. The next level is then traversed from right to left, i.e., 5, then 2, and so on.

Algorithm

Zigzag traversal can be implemented using two stacks, one stack for the current level (curr) and another for the next level (next).

  • Keep track of the direction to traverse using the variable isLtoR. If isLtoR is true, then the current level needs to be traversed from left to right and vice versa.

  • Push the root node into curr and set isLtoR to false for the next level.

  • Pop a node from curr and store it in the variable temp. Deduce the direction from isLtoR and decide, depending on the direction, whether the left child or the right child is to be pushed into next first.

  • Repeat the above step until curr is empty. When it is empty, swap the two stacks so that next becomes the emptied curr and curr becomes next.

  • Repeat the steps above until curr is eventually empty.

Code

The code tabs below implement the algorithm above:

#include <iostream>
#include <stack>
using namespace std;
struct Node {
int data;
struct Node* left_node;
struct Node* right_node;
};
void ZigZag(struct Node* root)
{
if (root == 0)
return;
// 2 stacks
stack<struct Node*> curr;
stack<struct Node*> next;
// push the root
curr.push(root);
// direction variable
bool isLtoR = true;
while (!curr.empty()) {
// pop from stack
struct Node* temp = curr.top();
curr.pop();
if (temp != 0) {
// if temp exists, print temp
cout << temp->data << " ";
// pushing the nodes in next
if (isLtoR == true) {
if (temp->left_node != 0)
next.push(temp->left_node);
if (temp->right_node != 0)
next.push(temp->right_node);
}
else {
if (temp->right_node != 0)
next.push(temp->right_node);
if (temp->left_node != 0)
next.push(temp->left_node);
}
}
if (curr.empty()) {
isLtoR = !isLtoR;
stack<struct Node*> temp_stack = next;
next = curr;
curr = temp_stack;
}
}
}
// function to add a node
struct Node* add_node(int data)
{
struct Node* node = new struct Node;
node->data = data;
node->left_node = node->right_node = 0;
return node;
}
int main()
{
struct Node* root = add_node(4);
root->left_node = add_node(2);
root->right_node = add_node(5);
root->left_node->left_node = add_node(1);
root->left_node->right_node = add_node(3);
cout << "ZigZag traversal: ";
ZigZag(root);
return 0;
}

RELATED TAGS

tree
traversal
zigzag
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Answers Code
Keep Exploring