(103). 28.7. ZIG‐ZAG TRAVERSAL BINARY SEARCH TREE. - anishsingh90/Data_Structure_And_Algorithm_In_Cpp_github.io GitHub Wiki

//ZIG-ZAG TRAVERSAL IN BINARY SEARCH TREE

#include <bits/stdc++.h> using namespace std;

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

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

};

//ZIG-ZAG TRAVERSAL PRINT void zigzagTraversal(Node* root){ if(root == NULL){ return; }

stack<Node*> currLevel;
stack<Node*> nextLevel;

bool leftToRight = true;

currLevel.push(root);

while(!currLevel.empty()){
	Node* temp = currLevel.top();
	currLevel.pop();
	
	
	if(temp){
		cout << temp->data <<" ";
	
	//Left To Right
	if(leftToRight){
		if(temp->left){
			 nextLevel.push(temp->left);
		}
		if(temp->right){
			nextLevel.push(temp->right);
		}
	}
	
	//Right To Left 
	else{
		if(temp->right){
			nextLevel.push(temp->right);
		}
		if(temp->left){
			nextLevel.push(temp->left);
		}
	}
}
if(currLevel.empty()){
	leftToRight = !leftToRight;
	swap(currLevel, nextLevel);
}
}

}

int main(){ /* 12 /
9 15 /
5 10 */

Node* root = new Node(12); root->left = new Node(9); root->right = new Node(15); root->left->left = new Node(5); root->left->right = new Node(10);

//zig-zag traversal cout << "zig-zag traversal is: "; zigzagTraversal(root); cout << endl;

return 0; }

/* OUTPUT: zig-zag traversal is: 12 15 9 5 10 */

⚠️ **GitHub.com Fallback** ⚠️