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.
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:
The zigzag traversal of this tree would be $4, 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.
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.
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 stacksstack<struct Node*> curr;stack<struct Node*> next;// push the rootcurr.push(root);// direction variablebool isLtoR = true;while (!curr.empty()) {// pop from stackstruct Node* temp = curr.top();curr.pop();if (temp != 0) {// if temp exists, print tempcout << temp->data << " ";// pushing the nodes in nextif (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 nodestruct 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
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.