import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class DFSAndBFS {

	public static void main(String[] args) {
		TreeNode root = new TreeNode(12);
		root.left = new TreeNode(8);
		root.left.left = new TreeNode(7);
		root.left.right = new TreeNode(10);
		root.left.right.left = new TreeNode(9);
		root.right = new TreeNode(20);
		root.right.left = new TreeNode(14);
		root.right.left.right = new TreeNode(15);
		root.right.right = new TreeNode(21);
		dfs(root);
		System.out.println();
		bfs(root);
	}

	public static void bfs(TreeNode root) {
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			System.out.print(node.value + " ");
			if (node.left != null) {
				queue.add(node.left);
			}
			if (node.right != null) {
				queue.add(node.right);
			}
		}
	}

	public static void dfs(TreeNode root) {
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			System.out.print(node.value + " ");
			if (node.right != null) {
				stack.add(node.right);
			}
			if (node.left != null) {
				stack.add(node.left);
			}
		}
	}
}