Binary Tree ZigZag Traversal

Print binary tree in zigzag order | 103. Binary Tree Zigzag Level Order Traversal Leetcode

Advertisement

Write a program to print ZigZag order traversal of a binary tree. For the below binary tree the zigzag order traversal will be 1 3 2 4 5 6 7.

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

tree1
Input: root  = [3,9,20,null,null,15,7]
Output: 
Advertisement
[[3],[20,9],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100

Solution:

  • Let us take 2 Stack. One for the parent, second one for child
  • boolean flag leftToRight for maintaining order in alternative fashion while adding right and left nodes.
  • If the parent stack is empty
    • Toggle the flag => leftToRight = !leftToRight;
    • Assign child to parent stack => parent = child;
    • Reset child stack => child = new Stack<>();
    • Add current level to output => output.add(level);
    • Reset Level => level = new ArrayList<>();
/*
Definition for a binary tree node.
*/
import java.util.*;
 
   class TreeNode {
 
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution {
 
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
      List<List<Integer>> output = new ArrayList<>();
 
      if(root == null)
        return output;
 
      Stack<TreeNode> parent = new Stack<>();
      Stack<TreeNode> child = new Stack<>();
      boolean leftToRight = true;
 
      parent.add(root);
 
      List<Integer> level = new ArrayList<>();
      while(!parent.isEmpty()){
        TreeNode node = parent.pop();
        level.add(node.val);
        if(leftToRight){
                if(node.left!=null) child.add(node.left);
                if(node.right!=null) child.add(node.right);
        }
        else{
                if(node.right!=null) child.add(node.right);
                if(node.left!=null) child.add(node.left);
        }
        if(parent.isEmpty()){
          leftToRight = !leftToRight;
          parent = child;
          child = new Stack<>();
          output.add(level);
          level = new ArrayList<>();
        }
      }
      return output;
    }
 
    public static void main(String args[]){
    	TreeNode root = new TreeNode(1);
    	root.left = new TreeNode(2);
    	root.right = new TreeNode(3);
    	root.left.left = new TreeNode(4);
    	root.left.right = new TreeNode(5);
    	root.right.left = new TreeNode(6);
    	root.right.right = new TreeNode(7);
 
    	System.out.print(new Solution().zigzagLevelOrder(root));
 
    }
}

What is the time and space complexity of zigzag order traversal in binary tree?

Time Complexity: O(n) 
Space Complexity: O(n)+(n)=O(n)

Advertisement

Leave a Reply

Your email address will not be published. Required fields are marked *

three × three =

Share on Social Media