Escriba una función para imprimir el recorrido en orden ZigZag de un árbol binario. Para el siguiente árbol binario, el recorrido en zigzag será 1 3 2 7 6 5 4.
C++
// C++ implementation of a O(n) time method for
// Zigzag order traversal
#include <iostream>
#include <stack>
using namespace std;
// Binary Tree node
struct Node {
int data;
struct Node *left, *right;
};
// function to print the zigzag traversal
void zizagtraversal(struct Node* root)
{
// if null then return
if (!root)
return;
// declare two stacks
stack<struct Node*> currentlevel;
stack<struct Node*> nextlevel;
// push the root
currentlevel.push(root);
// check if stack is empty
bool lefttoright = true;
while (!currentlevel.empty()) {
// pop out of stack
struct Node* temp = currentlevel.top();
currentlevel.pop();
// if not null
if (temp) {
// print the data in it
cout << temp->data << " ";
// store data according to current
// order.
if (lefttoright) {
if (temp->left)
nextlevel.push(temp->left);
if (temp->right)
nextlevel.push(temp->right);
}
else {
if (temp->right)
nextlevel.push(temp->right);
if (temp->left)
nextlevel.push(temp->left);
}
}
if (currentlevel.empty()) {
lefttoright = !lefttoright;
swap(currentlevel, nextlevel);
}
}
}
// A utility function to create a new node
struct Node* newNode(int data)
{
struct Node* node = new struct Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// driver program to test the above function
int main()
{
// create tree
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(7);
root->left->right = newNode(6);
root->right->left = newNode(5);
root->right->right = newNode(4);
cout << "ZigZag Order traversal of binary tree is \n";
zizagtraversal(root);
return 0;
}
Java
// Java implementation of a O(n) time
// method for Zigzag order traversal
import java.util.*;
// Binary Tree node
class Node
{
int data;
Node leftChild;
Node rightChild;
Node(int data)
{
this.data = data;
}
}
class BinaryTree {
Node rootNode;
// function to print the
// zigzag traversal
void printZigZagTraversal() {
// if null then return
if (rootNode == null) {
return;
}
// declare two stacks
Stack<Node> currentLevel = new Stack<>();
Stack<Node> nextLevel = new Stack<>();
// push the root
currentLevel.push(rootNode);
boolean leftToRight = true;
// check if stack is empty
while (!currentLevel.isEmpty()) {
// pop out of stack
Node node = currentLevel.pop();
// print the data in it
System.out.print(node.data + " ");
// store data according to current
// order.
if (leftToRight) {
if (node.leftChild != null) {
nextLevel.push(node.leftChild);
}
if (node.rightChild != null) {
nextLevel.push(node.rightChild);
}
}
else {
if (node.rightChild != null) {
nextLevel.push(node.rightChild);
}
if (node.leftChild != null) {
nextLevel.push(node.leftChild);
}
}
if (currentLevel.isEmpty()) {
leftToRight = !leftToRight;
Stack<Node> temp = currentLevel;
currentLevel = nextLevel;
nextLevel = temp;
}
}
}
}
public class zigZagTreeTraversal {
// driver program to test the above function
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.rootNode = new Node(1);
tree.rootNode.leftChild = new Node(2);
tree.rootNode.rightChild = new Node(3);
tree.rootNode.leftChild.leftChild = new Node(7);
tree.rootNode.leftChild.rightChild = new Node(6);
tree.rootNode.rightChild.leftChild = new Node(5);
tree.rootNode.rightChild.rightChild = new Node(4);
System.out.println("ZigZag Order traversal of binary tree is");
tree.printZigZagTraversal();
}
}
// This Code is contributed by Harikrishnan Rajan.
Python3
# Python Program to print zigzag traversal
# of binary tree
# Binary tree node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = self.right = None
# function to print zigzag traversal of
# binary tree
def zizagtraversal(root):
# Base Case
if root is None:
return
# Create two stacks to store current
# and next level
currentLevel = []
nextLevel = []
# if ltr is true push nodes from
# left to right otherwise from
# right to left
ltr = True
# append root to currentlevel stack
currentLevel.append(root)
# Check if stack is empty
while len(currentLevel) > 0:
# pop from stack
temp = currentLevel.pop(-1)
# print the data
print(temp.data, " ", end="")
if ltr:
# if ltr is true push left
# before right
if temp.left:
nextLevel.append(temp.left)
if temp.right:
nextLevel.append(temp.right)
else:
# else push right before left
if temp.right:
nextLevel.append(temp.right)
if temp.left:
nextLevel.append(temp.left)
if len(currentLevel) == 0:
# reverse ltr to push node in
# opposite order
ltr = not ltr
# swapping of stacks
currentLevel, nextLevel = nextLevel, currentLevel
# Driver program to check above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(7)
root.left.right = Node(6)
root.right.left = Node(5)
root.right.right = Node(4)
print("Zigzag Order traversal of binary tree is")
zizagtraversal(root)
# This code is contributed by Shweta Singh
C#
// C# implementation of a O(n) time
// method for Zigzag order traversal
using System;
using System.Collections.Generic;
// Binary Tree node
public class Node
{
public int data;
public Node leftChild;
public Node rightChild;
public Node(int data)
{
this.data = data;
}
}
class GFG
{
public Node rootNode;
// function to print the
// zigzag traversal
public virtual void printZigZagTraversal()
{
// if null then return
if (rootNode == null)
{
return;
}
// declare two stacks
Stack<Node> currentLevel = new Stack<Node>();
Stack<Node> nextLevel = new Stack<Node>();
// push the root
currentLevel.Push(rootNode);
bool leftToRight = true;
// check if stack is empty
while (currentLevel.Count > 0)
{
// pop out of stack
Node node = currentLevel.Pop();
// print the data in it
Console.Write(node.data + " ");
// store data according to current
// order.
if (leftToRight)
{
if (node.leftChild != null)
{
nextLevel.Push(node.leftChild);
}
if (node.rightChild != null)
{
nextLevel.Push(node.rightChild);
}
}
else
{
if (node.rightChild != null)
{
nextLevel.Push(node.rightChild);
}
if (node.leftChild != null)
{
nextLevel.Push(node.leftChild);
}
}
if (currentLevel.Count == 0)
{
leftToRight = !leftToRight;
Stack<Node> temp = currentLevel;
currentLevel = nextLevel;
nextLevel = temp;
}
}
}
}
public class zigZagTreeTraversal
{
// Driver Code
public static void Main(string[] args)
{
GFG tree = new GFG();
tree.rootNode = new Node(1);
tree.rootNode.leftChild = new Node(2);
tree.rootNode.rightChild = new Node(3);
tree.rootNode.leftChild.leftChild = new Node(7);
tree.rootNode.leftChild.rightChild = new Node(6);
tree.rootNode.rightChild.leftChild = new Node(5);
tree.rootNode.rightChild.rightChild = new Node(4);
Console.WriteLine("ZigZag Order traversal " +
"of binary tree is");
tree.printZigZagTraversal();
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript implementation of a O(n) time
// method for Zigzag order traversal
class Node
{
constructor(data) {
this.leftChild = null;
this.rightChild = null;
this.data = data;
}
}
let rootNode;
// function to print the
// zigzag traversal
function printZigZagTraversal()
{
// if null then return
if (rootNode == null)
{
return;
}
// declare two stacks
let currentLevel = [];
let nextLevel = [];
// push the root
currentLevel.push(rootNode);
let leftToRight = true;
// check if stack is empty
while (currentLevel.length > 0)
{
// pop out of stack
let node = currentLevel.pop();
// print the data in it
document.write(node.data + " ");
// store data according to current
// order.
if (leftToRight)
{
if (node.leftChild != null)
{
nextLevel.push(node.leftChild);
}
if (node.rightChild != null)
{
nextLevel.push(node.rightChild);
}
}
else
{
if (node.rightChild != null)
{
nextLevel.push(node.rightChild);
}
if (node.leftChild != null)
{
nextLevel.push(node.leftChild);
}
}
if (currentLevel.length == 0) {
leftToRight = !leftToRight;
let temp = currentLevel;
currentLevel = nextLevel;
nextLevel = temp;
}
}
}
rootNode = new Node(1);
rootNode.leftChild = new Node(2);
rootNode.rightChild = new Node(3);
rootNode.leftChild.leftChild = new Node(7);
rootNode.leftChild.rightChild = new Node(6);
rootNode.rightChild.leftChild = new Node(5);
rootNode.rightChild.rightChild = new Node(4);
document.write("ZigZag Order traversal of binary tree is" +
"</br>");
printZigZagTraversal();
</script>
C++
//Initial Template for C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left;
Node *right;
Node(int val) {
data = val;
left = right = NULL;
}
};
// Function to Build Tree
Node* buildTree(string str)
{
// Corner Case
if(str.length() == 0 || str[0] == 'N')
return NULL;
// Creating vector of strings from input
// string after splitting by space
vector<string> ip;
istringstream iss(str);
for(string str; iss >> str; )
ip.push_back(str);
// Create the root of the tree
Node* root = new Node(stoi(ip[0]));
// Push the root to the queue
queue<Node*> queue;
queue.push(root);
// Starting from the second element
int i = 1;
while(!queue.empty() && i < ip.size()) {
// Get and remove the front of the queue
Node* currNode = queue.front();
queue.pop();
// Get the current node's value from the string
string currVal = ip[i];
// If the left child is not null
if(currVal != "N") {
// Create the left child for the current node
currNode->left = new Node(stoi(currVal));
// Push it to the queue
queue.push(currNode->left);
}
// For the right child
i++;
if(i >= ip.size())
break;
currVal = ip[i];
// If the right child is not null
if(currVal != "N") {
// Create the right child for the current node
currNode->right = new Node(stoi(currVal));
// Push it to the queue
queue.push(currNode->right);
}
i++;
}
return root;
}
// Function to calculate height of tree
int treeHeight(Node *root){
if(!root) return 0;
int lHeight = treeHeight(root->left);
int rHeight = treeHeight(root->right);
return max(lHeight, rHeight) + 1;
}
// Helper Function to store the zig zag order traversal
// of tree in a list recursively
void zigZagTraversalRecursion(Node* root, int height, bool lor, vector<int> &ans){
// Height = 1 means the tree now has only one node
if(height <= 1){
if(root) ans.push_back(root->data);
}
// When Height > 1
else{
if(lor){
if(root->left) zigZagTraversalRecursion(root->left, height - 1, lor, ans);
if(root->right) zigZagTraversalRecursion(root->right, height - 1, lor, ans);
}
else{
if(root->right) zigZagTraversalRecursion(root->right, height - 1, lor, ans);
if(root->left) zigZagTraversalRecursion(root->left, height - 1, lor, ans);
}
}
}
// Function to traverse tree in zig zag order
vector <int> zigZagTraversal(Node* root)
{
vector<int> ans;
bool leftOrRight = true;
int height = treeHeight(root);
for(int i = 1; i <= height; i++){
zigZagTraversalRecursion(root, i, leftOrRight, ans);
leftOrRight = !leftOrRight;
}
return ans;
}
int main()
{
// Tree:
// 1
// / \
// / \
// / \
// 2 3
// / \ / \
// 4 5 6 7
// / \ / \ / \ / \
//8 9 10 11 12 13 14 15
string s = "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15";
Node* root = buildTree(s);
vector <int> res = zigZagTraversal(root);
cout<<"ZigZag traversal of binary tree is:"<<endl;
for (int i = 0; i < res.size (); i++) cout << res[i] << " ";
cout<<endl;
return 0;
}
// Code By Angshuman Sengupta
Python3
# Python code for recursive approach
from collections import defaultdict
from collections import deque
class Node:
def __init__(self, val):
self.data = val
self.left = None
self.right = None
# Function to Build Tree
def buildTree(s):
# Corner Case
if(len(s) == 0 or s[0] == "N"):
return None
# Creating list of strings from input
# string after spliting by space
ip = list(map(str, s.split()))
# Create the root of the tree
root = Node(int(ip[0]))
size = 0
q = deque()
# Push the root to the queue
q.append(root)
size = size+1
# Starting from the second element
i = 1
while(size > 0 and i < len(ip)):
# Get and remove the front of the queue
currNode = q[0]
q.popleft()
size = size-1
# Get the current node's value from the string
currVal = ip[i]
# If the left child is not null
if(currVal != "N"):
# Create the left child for the current node
currNode.left = Node(int(currVal))
# Push it to the queue
q.append(currNode.left)
size = size+1
# For the right child
i = i+1
if(i >= len(ip)):
break
currVal = ip[i]
# If the right child is not null
if(currVal != "N"):
# Create the right child for the current node
currNode.right = Node(int(currVal))
# Push it to the queue
q.append(currNode.right)
size = size+1
i = i+1
return root
# Function to calculate height of tree
def treeHeight(root):
if not root:
return 0
lHeight = treeHeight(root.left)
rHeight = treeHeight(root.right)
return max(lHeight, rHeight) + 1
# Helper Function to store the zig zag order traversal
# of tree in a list recursively
def zigZagTraversalRecursion(root, height, lor, ans):
# Height = 1 means the tree now has only one node
if height <= 1:
if root:
ans.append(root.data)
# When Height > 1
else:
if lor:
if root.left:
zigZagTraversalRecursion(root.left, height - 1, lor, ans)
if root.right:
zigZagTraversalRecursion(root.right, height - 1, lor, ans)
else:
if root.right:
zigZagTraversalRecursion(root.right, height - 1, lor, ans)
if root.left:
zigZagTraversalRecursion(root.left, height - 1, lor, ans)
# Function to traverse tree in zig zag order
def zigZagTraversal(root):
ans = []
leftOrRight = True
height = treeHeight(root)
for i in range(1, height + 1):
zigZagTraversalRecursion(root, i, leftOrRight, ans)
leftOrRight = not leftOrRight
return ans
if __name__ == '__main__':
# Tree:
# 1
# / \
# / \
# / \
# 2 3
# / \ / \
# 4 5 6 7
# / \ / \ / \ / \
# 8 9 10 11 12 13 14 15
s = "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15"
root = buildTree(s)
res = zigZagTraversal(root)
print("ZigZag traversal of binary tree is:")
for i in range(len(res)):
print(res[i], end=" ")
print()
# This code is contributed by Tapesh (tapeshdua420)
C++
// C++ implementation of a O(n) time method for
// Zigzag order traversal
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Binary Tree node
class Node {
public:
int data;
Node *left, *right;
};
// Function to print the zigzag traversal
vector<int> zigZagTraversal(Node* root)
{
deque<Node*> q;
vector<int> v;
q.push_back(root);
v.push_back(root->data);
Node* temp;
// set initial level as 1, because root is
// already been taken care of.
int l = 1;
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
// popping mechanism
if (l % 2 == 0) {
temp = q.back();
q.pop_back();
}
else {
temp = q.front();
q.pop_front();
}
// pushing mechanism
if (l % 2 != 0) {
if (temp->right) {
q.push_back(temp->right);
v.push_back(temp->right->data);
}
if (temp->left) {
q.push_back(temp->left);
v.push_back(temp->left->data);
}
}
else if (l % 2 == 0) {
if (temp->left) {
q.push_front(temp->left);
v.push_back(temp->left->data);
}
if (temp->right) {
q.push_front(temp->right);
v.push_back(temp->right->data);
}
}
}
l++; // level plus one
}
return v;
}
// A utility function to create a new node
struct Node* newNode(int data)
{
struct Node* node = new struct Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Driver program to test
// the above function
int main()
{
// vector to store the traversal order.
vector<int> v;
// create tree
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(7);
root->left->right = newNode(6);
root->right->left = newNode(5);
root->right->right = newNode(4);
cout << "ZigZag Order traversal of binary tree is \n";
v = zigZagTraversal(root);
for (int i = 0; i < v.size();
i++) { // to print the order
cout << v[i] << " ";
}
return 0;
}
// This code is contributed by Ritvik Mahajan
Java
// Java implementation of a O(n) time method for
// Zigzag order traversal
import java.util.*;
public class Main
{
// Class containing left and
// right child of current
// node and key value
static class Node {
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
}
// A utility function to create a new node
static Node newNode(int data)
{
Node node = new Node(data);
return node;
}
// Function to print the zigzag traversal
static Vector<Integer> zigZagTraversal(Node root)
{
Deque<Node> q = new LinkedList<Node>();
Vector<Integer> v = new Vector<Integer>();
q.add(root);
v.add(root.data);
Node temp;
// set initial level as 1, because root is
// already been taken care of.
int l = 1;
while (q.size() > 0) {
int n = q.size();
for (int i = 0; i < n; i++) {
// popping mechanism
if (l % 2 == 0) {
temp = q.peekLast();
q.pollLast();
}
else {
temp = q.peekFirst();
q.pollFirst();
}
// pushing mechanism
if (l % 2 != 0) {
if (temp.right != null) {
q.add(temp.right);
v.add(temp.right.data);
}
if (temp.left != null) {
q.add(temp.left);
v.add(temp.left.data);
}
}
else if (l % 2 == 0) {
if (temp.left != null) {
q.offerFirst(temp.left);
v.add(temp.left.data);
}
if (temp.right != null) {
q.offerFirst(temp.right);
v.add(temp.right.data);
}
}
}
l++; // level plus one
}
return v;
}
public static void main(String[] args)
{
// vector to store the traversal order.
Vector<Integer> v;
// create tree
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(7);
root.left.right = newNode(6);
root.right.left = newNode(5);
root.right.right = newNode(4);
System.out.println("ZigZag Order traversal of binary tree is");
v = zigZagTraversal(root);
for (int i = 0; i < v.size();
i++) { // to print the order
System.out.print(v.get(i) + " ");
}
}
}
// This code is contributed by divyesh072019.
Python3
# Python3 implementation of a O(n) time method for
# Zigzag order traversal
from collections import deque
# Binary Tree node
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to print the zigzag traversal
def zigZagTraversal(root):
q = deque([])
v = []
q.append(root)
v.append(root.data)
# set initial level as 1, because root is
# already been taken care of.
l = 1
while len(q) > 0:
n = len(q)
for i in range(n):
# popping mechanism
if (l % 2 == 0):
temp = q[-1]
q.pop()
else:
temp = q[0]
q.popleft()
# pushing mechanism
if (l % 2 != 0):
if (temp.right):
q.append(temp.right)
v.append(temp.right.data)
if (temp.left):
q.append(temp.left)
v.append(temp.left.data)
elif (l % 2 == 0):
if (temp.left):
q.appendleft(temp.left)
v.append(temp.left.data)
if (temp.right):
q.appendleft(temp.right)
v.append(temp.right.data)
l+=1 # level plus one
return v
# vector to store the traversal order.
v = []
# create tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(7)
root.left.right = Node(6)
root.right.left = Node(5)
root.right.right = Node(4)
print("ZigZag Order traversal of binary tree is")
v = zigZagTraversal(root)
for i in range(len(v)):
print(v[i], end = " ")
# This code is contributed by suresh07.
C++
// C++ implementation of a O(n) time method for
// Zigzag order traversal
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Binary Tree node
class Node {
public:
int data;
Node *left, *right;
};
// Function to print the zigzag traversal
vector<int> zigZagTraversal(Node* root) {
if(root == NULL){return { } ; }
vector<int > ans ;
queue<Node*> q ;
q.push(root) ;
bool flag = false ;
while(!q.empty()){
int size = q.size() ;
vector<int> level ;
for(int i=0 ; i < size ; i++){
Node* node = q.front() ;
q.pop() ;
level.push_back(node->data) ;
if(node->left != NULL) {q.push(node->left) ;}
if(node->right != NULL) {q.push(node->right) ;}
}
flag = !flag ;
if(flag == false){
reverse(level.begin() , level.end()) ;
}
for(int i = 0 ; i < level.size() ; i++){
ans.push_back(level[i]) ;
}
}
return ans ;
}
// A utility function to create a new node
struct Node* newNode(int data)
{
struct Node* node = new struct Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Driver program to test
// the above function
int main()
{
// vector to store the traversal order.
vector<int> v;
// create tree
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(7);
root->left->right = newNode(6);
root->right->left = newNode(5);
root->right->right = newNode(4);
cout << "ZigZag Order traversal of binary tree is \n";
v = zigZagTraversal(root);
for (int i = 0; i < v.size();
i++) { // to print the order
cout << v[i] << " ";
}
return 0;
}
Java
// Java implementation of a O(n) time method for
// Zigzag order traversal
import java.util.*;
public class Main {
// Class containing left and
// right child of current
// node and key value
static class Node {
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
}
// A utility function to create a new node
static Node newNode(int data)
{
Node node = new Node(data);
return node;
}
// Function to print the zigzag traversal
static ArrayList<Integer> zigZagTraversal(Node root)
{
ArrayList<Integer> ans = new ArrayList<Integer>();
// if there is no element in the tree,return empty
// arraylist
if (root == null)
return ans;
Queue<Node> q = new LinkedList<Node>();
q.add(root);
// this variable helps to check if elements are to
// be added from left to right or right to left
boolean leftToRight = true;
while (q.size() > 0) {
int size = q.size();
// this arraylist is used to store element at
// current level
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < size; i++) {
Node curr = q.poll();
if (curr.left != null)
q.add(curr.left);
if (curr.right != null)
q.add(curr.right);
temp.add(curr.data);
}
if (leftToRight) // at current level,add element
// from left to right to our
// answer
{
// do nothing
}
// we have to add element from to right to left
// and this can be done by reversing our temp
// arraylist
else {
Collections.reverse(temp);
}
// add element form temp arraylist to our ans
// arraylist
for (int i = 0; i < temp.size(); i++) {
ans.add(temp.get(i));
}
// change the value of leftToRight from true to
// false or false to true for next iteration.
leftToRight = !(leftToRight);
}
// return our ans arraylist
return ans;
}
public static void main(String[] args)
{
// Arraylist to store the traversal order.
ArrayList<Integer> ans;
// create tree
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(7);
root.left.right = newNode(6);
root.right.left = newNode(5);
root.right.right = newNode(4);
System.out.println(
"ZigZag Order traversal of binary tree is");
ans = zigZagTraversal(root);
for (int i = 0; i < ans.size();
i++) { // to print the order
System.out.print(ans.get(i) + " ");
}
}
}
// this is contributed by akshita29320
Python3
# Python Program to print zigzag traversal
# of binary tree
# Binary tree node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = self.right = None
# function to print zigzag traversal of
# binary tree
def zigzagtraversal(root):
# Base Case
if root is None:
return
ans = [] # store the traversal in the ans array
queue = [root] # use list as queue
flag = False
while len(queue) != 0:
n = len(queue)
level = []
for i in range(n):
node = queue[0]
queue.pop(0)
level.append(node.data)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
flag = not flag
if flag == False:
level = level[::-1]
for i in range(n):
ans.append(level[i])
return ans
# Driver program to check above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(7)
root.left.right = Node(6)
root.right.left = Node(5)
root.right.right = Node(4)
print("Zigzag Order traversal of binary tree is")
v = zigzagtraversal(root)
for i in v:
print(i,end = " ")
#This Code is Contributed By Vivek Maddeshiya