package trees;

import java.util.*;

public class Tree {
	private static class Node {
		String data;
		LinkedList<Node> children;
		Node (String data) {
			this.data = data;
			children = new LinkedList<Node>();
		}
	}
	
	private Node root=null;

	
	// print the subtree rooted at cur, recursively (pre-order traversal)
	private void printPreOrderHelper (Node cur, int depth) {
		for (int i=0; i<depth; i++)
			System.out.print("  ");
		System.out.println(cur.data);

		for(Node child : cur.children)
			printPreOrderHelper(child, depth+1);
		
/*		Iterator<Node> it;
		it = cur.children.iterator();
		while (it.hasNext()) {
			Node child = it.next();
			printTreeHelper (child);
		}
		*/
	}
	
	public void printPreOrder() {
		if(root!=null) 
			printPreOrderHelper(root, 0);
	}

	// print the subtree rooted at cur, recursively (post-order traversal)
	private void printPostOrderHelper (Node cur, int depth) {
		for(Node child : cur.children)
			printPostOrderHelper(child, depth+1);

		for (int i=0; i<depth; i++)
			System.out.print("  ");
		System.out.println(cur.data);
	}
	public void printPostOrder() {
		if(root!=null) 
			printPostOrderHelper(root, 0);
	}

	// print the tree in a preorder traversal with a stack (depth-first search)
	public void printPreOrderWithAStack () {
		Stack<Node> s = new Stack<Node>();
		
		if (root!=null)
			s.push(root);
		
		while (!s.isEmpty()) {
			Node cur = s.pop();
			System.out.println(cur.data);
			for(Node child : cur.children)
				s.push(child);
		}
		
	}

	// print the tree in a level-order traversal (breadth-first search)
	public void printWithAQueue () {
		Queue<Node> q = new LinkedList<Node>();
		
		if (root!=null)
			q.add(root);
		
		while (!q.isEmpty()) {
			Node cur = q.remove();
			System.out.println(cur.data);
			for(Node child : cur.children)
				q.add(child);
		}
		
	}

	public static void main(String []args) {
		Tree t = new Tree();
		t.root = new Node("Root");
		
		Node subdir1 = new Node ("a");
		t.root.children.add(subdir1);

		Node subdir2 = new Node ("b");
		t.root.children.add(subdir2);

		Node subdir3 = new Node ("c");
		t.root.children.add(subdir3);


		Node subdir11 = new Node ("a1");
		subdir1.children.add(subdir11);

		Node subdir12 = new Node ("a2");
		subdir1.children.add(subdir12);

		Node subdir13 = new Node ("a3");
		subdir1.children.add(subdir13);

		Node subdir21 = new Node ("b1");
		subdir2.children.add(subdir21);


		Node subdir22 = new Node ("b2");
		subdir2.children.add(subdir22);

		t.printPreOrder();
		System.out.println();
		t.printPostOrder();	
		System.out.println();
		t.printPreOrderWithAStack();
		System.out.println();
		t.printWithAQueue();
	}
	
	
}