CC-20 : Implement ZigZag Traversal of Binary Tree.

Description:

In ZigZag traversal, at each alternate level, we traverse the current levels nodes in left-right or right-left order alternatively. Given a Binary Tree, traverse it in ZigZag manner.

Test cases and expected outputs:

Input Parameters	Expected outputs
Traverse above tree in ZigZag manner.	ZigZag traversal : 4, 7,5, 6,78,14, 16,8,33, 18, 9,

Pseudocode:

We will use member variable ArrayList or ArrayLists named zigZag to store the Binary Tree’s node data traversed levelwise in ZigZag manner.

Method bfsZigZagTraversal (TreeNode root, int level):

If root node is null, return.

Else:

If zigZag.size() < level, add a new current Arraylist to end of ArrayList to store the current level’s traversed nodes.

If current level is even, add node data of root to end of current ArrayList(node are being traversed from left to right).

If current level is odd, add node data of root to start of current ArrayList(node are being traversed from right to left).

Recursively call bfsZigZagTraversal () method with node’s left child and (level+1) as input parameters.

Recursively call convertToLinkedList() method with node’s right child and (level+1) as input parameters.

Code:

public class BinTreeZigZag{

private ArrayList< ArrayList< Integer > > zigZag=new ArrayList< ArrayList < Integer > >();

public ArrayList< ArrayList < Integer > > getZigZag() {
	return zigZag;
}
public void setZigZag(ArrayList< ArrayList < Integer > > zigZag) {
	this.zigZag = zigZag;
}

public void bfsZigZagTraversal(BinTreeNode root, int lvl) {
	if (root==null) {return;}
	if (zigZag.size() <=lvl) {zigZag.add(new ArrayList<Integer>());}
	if(lvl%2==0) {
		zigZag.get(lvl).add(root.getNodeData());
	}else {
		zigZag.get(lvl).add(0,root.getNodeData());
	}
	bfsZigZagTraversal(root.getLeftChild(), lvl+1);
	bfsZigZagTraversal(root.getRightChild(), lvl+1);
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

Note: for easy reference BinTreeNode is included as internal class in program below. Ideally it should be in a separate file.

import java.util.ArrayList;

public class BinTreeZigZag{

private ArrayList< ArrayList < Integer > > zigZag=new ArrayList< ArrayList < Integer > >();

public ArrayList < ArrayList < Integer > > getZigZag() {
	return zigZag;
}
public void setZigZag(ArrayList< ArrayList < Integer > > zigZag) {
	this.zigZag = zigZag;
}

public void bfsZigZagTraversal(BinTreeNode root, int lvl) {
	if (root==null) {return;}
	if (zigZag.size() <=lvl) {zigZag.add(new ArrayList<Integer>());}
	if(lvl%2==0) {
		zigZag.get(lvl).add(root.getNodeData());
	}else {
		zigZag.get(lvl).add(0,root.getNodeData());
	}
	bfsZigZagTraversal(root.getLeftChild(), lvl+1);
	bfsZigZagTraversal(root.getRightChild(), lvl+1);
}
 	
public static void main(String[] args) {
	/***********************
 	Test cases given below:
	 **********************/
	ArrayList<Integer> retVal=null;
	try {
	BinTreeZigZag zz=new BinTreeZigZag();
	BinTreeNode root=zz.new BinTreeNode(4);
	//Left L1 Children
	root.setLeftChild(zz.new BinTreeNode(5));
	root.setRightChild(zz.new BinTreeNode(7));
	
	//Left L2 Children
	root.getLeftChild().setLeftChild(zz.new BinTreeNode(6));
	root.getLeftChild().setRightChild(zz.new BinTreeNode(78));
	
	//Left L3 Children
	root.getLeftChild().getLeftChild().setLeftChild(zz.new BinTreeNode(33));
	
	//Right L2 Children
	root.getRightChild().setLeftChild(zz.new BinTreeNode(14));
	
	
	//Right L3 Children
	root.getRightChild().getLeftChild().setLeftChild(zz.new BinTreeNode(8));
	root.getRightChild().getLeftChild().setRightChild(zz.new BinTreeNode(16));
	
	//Right L3 Children
	root.getRightChild().getLeftChild().getRightChild().setLeftChild(zz.new BinTreeNode(18));
	
	//Right L4 Children
	root.getRightChild().getLeftChild().getRightChild().getLeftChild().setLeftChild(zz.new BinTreeNode(9));
	
	
	zz.bfsZigZagTraversal(root,0);
	for (int idx=0; idx < zz.getZigZag().size();idx++) {
		System.out.println();
		for (int idx1=0; idx1 < zz.getZigZag().get(idx).size(); idx1++) {
			System.out.print(zz.getZigZag().get(idx).get(idx1)+",");
		}
	}
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
	
}

public class BinTreeNode {
	private BinTreeNode leftNode=null;
	private BinTreeNode rightNode=null;
	private int nodeData=0;
	
	public BinTreeNode(int data) {
		nodeData=data;
	}	
	public BinTreeNode getLeftChild() {
		return leftNode;
	}
	public void setLeftChild(BinTreeNode leftNode) {
		this.leftNode = leftNode;
	}
	public BinTreeNode getRightChild() {
		return rightNode;
	}
	public void setRightChild(BinTreeNode rightNode) {
		this.rightNode = rightNode;
	}
	public int getNodeData() {
		return nodeData;
	}
	public void setNodeData(int nodeData) {
		this.nodeData = nodeData;
	}

}


}