You have already seen how to perform level order traversal i…
You have already seen how to perform level order traversal in a tree using a queue data structure. Write an algorithm to perform a new type of traversal called GatorLevel Traversal. In this traversal, we print nodes in alternating left-to-right and right-to-left patterns across different levels. You can see the below image showcasing an example. You are required to write a function in C++ or pseudocode that takes in as input the root node of a binary tree and uses two stacks or one queue and one stack for performing the GatorLevel traversal. Here is the definition of a node object for a tree node and you can assume that the tree is already constructed (no need to write insert function): struct Node{ int val; Node* left; Node* right;}