21. ZigZag Tree Traversal
Last updated
Was this helpful?
Last updated
Was this helpful?
The problem can be found at the following link:
Initialize an empty vector ans to store the zigzag traversal result.
Check if the root is null. If so, return the empty ans vector.
Use a queue q to perform level order traversal.
Start by pushing the root node into the queue.
Initialize a boolean variable left to true to control the direction of traversal.
While the queue is not empty :
Get the size of the queue to process nodes at the current level.
Create a temporary vector vec to store node values at the current level.
Iterate through the nodes at the current level.
Dequeue a node from the front of the queue.
the index to insert the node value based on the traversal direction.
Store the node value at the determined index in vec.
If the dequeued node has left or right child, enqueue them.
Toggle the value of left to switch the direction for the next level.
Append the values stored in vec to the result vector ans.
Return the result vector ans containing the zigzag traversal of the tree.
Time Complexity: The time complexity of this approach is O(N)
, where N is the number of nodes in the binary tree.
Auxiliary Space Complexity: The auxiliary space complexity is O(N)
, where N is the maximum number of nodes at any level of the tree.
For discussions, questions, or doubts related to this solution, please visit our . We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the repository.