Java Maze Solver

 

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Comparator;
	import java.util.Optional;
	public class RatMaze {
	final int N = 7;
	void printSolution(int sol[][], int[][] visited, int[][] distances) {
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++)
	System.out.print (" " + sol[i][j] + " ");
	System.out.println ();
	}
	System.out.println ();
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++)
	System.out.print (" " + visited[i][j] + " ");
	System.out.println ();
	}
	System.out.println ();
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++)
	System.out.print (" " + distances[i][j] + " ");
	System.out.println ();
	}
	}
	boolean isSafe(int maze[][], int x, int y, int visited[][], int[][] distances, int distance) {
	return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1 && (visited[x][y] == 0 || (visited[x][y] == 1 && distances[x][y] >= distance)));
	}
	boolean solveMaze(int maze[][]) {
	int sol[][] = {
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0}};
	int visited[][] = {
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0}};
	int distances[][] = {
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0}};
	Result result = solveMazeUtil (maze, 0, 0, sol, visited, distances, 1);
	if (result.distance == Integer.MAX_VALUE) {
	System.out.print ("Solution doesn't exist");
	return false;
	}
	printSolution (result.sol, visited, distances);
	return true;
	}
	class Result {
	int distance;
	int[][] sol;
	public Result(int distance, int[][] sol) {
	this.distance = distance;
	this.sol = sol;
	}
	}
	Result solveMazeUtil(int maze[][], int x, int y, int sol[][], int visited[][], int distances[][], int distance) {
	// if (x, y is goal) return true
	if (x == N - 1 && y == N - 1) {
	sol[x][y] = 1;
	return new Result (distance, sol);
	}
	if (isSafe (maze, x, y, visited, distances, distance) == true) {
	int solTmp = sol[x][y];
	sol[x][y] = 1;
	int tmpVisit = visited[x][y];
	visited[x][y] = 1;
	int tmpDist = distances[x][y];
	distances[x][y] = distance;
	ArrayList<Result> results = new ArrayList<> ();
	Result down = solveMazeUtil (maze, x + 1, y, sol, visited, distances, distance + 1);
	if(down.distance != Integer.MAX_VALUE){
	results.add (down);
	}
	Result up = solveMazeUtil (maze, x - 1, y, sol, visited, distances, distance + 1);
	if(up.distance != Integer.MAX_VALUE){
	results.add (up);
	}
	Result right = solveMazeUtil (maze, x, y + 1, sol, visited, distances, distance + 1);
	if(right.distance != Integer.MAX_VALUE){
	results.add (right);
	}
	Result left = solveMazeUtil (maze, x, y - 1, sol, visited, distances, distance + 1);
	if(left.distance != Integer.MAX_VALUE){
	results.add (left);
	}
	Optional<Result> min = Arrays.asList (new Result[]{up, down, right, left}).stream ().
	min (Comparator.comparingInt (r -> r.distance));
	if(min.get () != null){
	return min.get ();
	}
	sol[x][y] = solTmp;
	visited[x][y] = tmpVisit;
	distances[x][y] = tmpDist;
	return new Result (Integer.MAX_VALUE, sol);
	}
	return new Result (Integer.MAX_VALUE, sol);
	}
	public static void main(String args[]) {
	RatMaze rat = new RatMaze ();
	int maze[][] = {
	{1, 0, 0, 1, 1, 1, 0},
	{1, 1, 0, 1, 0, 1, 1},
	{0, 1, 0, 1, 0, 0, 1},
	{0, 1, 0, 1, 0, 0, 1},
	{0, 1, 0, 1, 1, 1, 1},
	{0, 1, 0, 1, 0, 0, 1},
	{1, 1, 1, 1, 1, 1, 1}
	};
	rat.solveMaze (maze);
	}
	}

view raw RatMaze.java hosted with ❤ by GitHub

AVL TREE LEFT RIGHT DOUBLE ROTATIONS, DEPTH FIRST SEARCHs, BREADTH FIRST SEARCH, RECURSIVE and ITERATIVE TRAVERSALS, HEIGHT, DEPTH, SIZE, LEAF, NODE FINDERS, ROOT to LEAF NODE PATHS

SINGLE ROTATION

DOUBLE ROTATION

Suppose the node to be rebalanced is X. 

There are 4 cases that we might have to fix (two are the mirror images of the other two):

• An insertion in the left subtree of the left child of X,
• An insertion in the right subtree of the left child of X,
• An insertion in the left subtree of the right child of X, or
• An insertion in the right subtree of the right child of X.

Balance is restored by tree rotations.

Case 1 and case 4 are symmetric and requires the same operation for balance. 

Cases 1,4 are handled by single rotation.

Case 2 and case 3 are symmetric and requires the same operation for balance.

Cases 2,3 are handled by double rotation

	package deneme01;
	import lombok.NoArgsConstructor;
	import java.util.*;
	class Node {
	public Node parent;
	int data, depth, weight;
	Node left, right;
	int height;
	boolean ignore;
	public Node(int data) {
	this.data = data;
	}
	public boolean isLeaf() {
	if (left == null && right == null)
	return true;
	else return false;
	}
	@Override
	public String toString() {
	return "" + data;
	}
	}
	@NoArgsConstructor
	class Tree {
	Node root;
	public Tree(Node root) {
	this.root = root;
	}
	public void preOrderRecursive(Node node) {
	if (node == null) {
	return;
	}
	System.out.print (" " + node.data);
	preOrderRecursive (node.left);
	preOrderRecursive (node.right);
	}
	public void inOrderRecursive(Node node) {
	if (node == null) {
	return;
	}
	preOrderRecursive (node.left);
	System.out.print (" " + node.data);
	preOrderRecursive (node.right);
	}
	public void postOrderRecursive(Node node) {
	if (node == null) {
	return;
	}
	preOrderRecursive (node.left);
	preOrderRecursive (node.right);
	System.out.print (" " + node.data);
	}
	public void preOrderIterative() {
	Stack<Node> stack = new Stack<> ();
	stack.push (root);
	while (!stack.isEmpty ()) {
	Node pop = stack.pop ();
	System.out.print (" " + pop.data);
	if (pop.right != null) stack.push (pop.right);
	if (pop.left != null) stack.push (pop.left);
	}
	}
	public void inOrderIterative() {
	Stack<Node> stack = new Stack<> ();
	Node current = root;
	while (!stack.isEmpty () || null != current) {
	if (current != null) {
	stack.push (current);
	current = current.left;
	} else {
	Node pop = stack.pop ();
	System.out.print (" " + pop.data);
	current = pop.right;
	}
	}
	}
	public void postOrderIterative() {
	Stack<Node> stack = new Stack<> ();
	stack.push (root);
	while (!stack.isEmpty ()) {
	Node peek = stack.peek ();
	if (peek.isLeaf ()) {
	Node pop = stack.pop ();
	System.out.print (" " + pop.data);
	} else {
	if (peek.right != null) {
	stack.push (peek.right);
	peek.right = null;
	}
	if (peek.left != null) {
	stack.push (peek.left);
	peek.left = null;
	}
	}
	}
	}
	public void bfsRecursive() {
	int height = Math.max (height (root.left), height (root.right)) + 1;
	for (int i = 1; i <= height; i++) {
	bfs (root, i);
	System.out.println ("");
	}
	}
	private void bfs(Node node, int height) {
	if (node == null) {
	return;
	}
	if (height == 1) {
	System.out.print (" " + node.data);
	} else if (height > 1) {
	bfs (node.left, height - 1);
	bfs (node.right, height - 1);
	}
	}
	public void bfsIterative() {
	Queue<Node> queue = new LinkedList<> ();
	root.depth = 0;
	queue.add (root);
	int currentDepth = root.depth;
	while (!queue.isEmpty ()) {
	Node poll = queue.poll ();
	if (currentDepth != poll.depth) {
	System.out.println ("");
	currentDepth = poll.depth;
	}
	System.out.print (" " + poll.data);
	if (poll.left != null) {
	poll.left.depth = poll.depth + 1;
	queue.add (poll.left);
	}
	if (poll.right != null) {
	poll.right.depth = poll.depth + 1;
	queue.add (poll.right);
	}
	}
	}
	public void bfsIterativeBottom2Top() {
	Queue<Node> queue = new LinkedList<> ();
	Stack<Node> stack = new Stack<> ();
	queue.add (root);
	while (!queue.isEmpty ()) {
	Node poll = queue.poll ();
	//System.out.print(" " + poll.data);
	stack.push (poll);
	if (poll.right != null) {
	queue.add (poll.right);
	}
	if (poll.left != null) {
	queue.add (poll.left);
	}
	}
	while (!stack.isEmpty ()) {
	Node pop = stack.pop ();
	System.out.print (" " + pop.data);
	}
	}
	public int size() {
	Stack<Node> stack = new Stack<> ();
	stack.push (root);
	int size = 0;
	while (!stack.isEmpty ()) {
	Node pop = stack.pop ();
	size++;
	if (pop.right != null) {
	stack.push (pop.right);
	}
	if (pop.left != null) {
	stack.push (pop.left);
	}
	}
	return size;
	}
	public int height() {
	return height (root);
	}
	private int height(Node node) {
	if (node == null) {
	return 0;
	}
	return Math.max (height (node.left), height (node.right)) + 1;
	}
	public Node insert(int x) {
	return insert (x, root);
	}
	public Node insert(int x, Node node) {
	if (node == null) {
	node = new Node (x);
	}
	if (x < node.data) {
	node = insert (x, node);
	if (x < node.left.data) {
	node = rightRotate (node);
	} else {
	node = doubleRightRotate (node);
	}
	} else if (x > node.data) {
	node = insert (x, node);
	if (x > node.right.data) {
	node = leftRotate (node);
	} else {
	node = doubleLeftRotate (node);
	}
	} else {
	//duplicate , ignore
	}
	return node;
	}
	private Node doubleRightRotate(Node node) {
	node.left = leftRotate (node.left);
	return rightRotate (node);
	}
	private Node rightRotate(Node k1) {
	Node k2 = k1.left;
	k1.left = k2.right;
	k2.right = k1;
	k1.height = Math.max (height (k1.left), height (k1.left)) + 1;
	k2.height = Math.max (height (k2.left), height (k2.left)) + 1;
	return k2;
	}
	private Node doubleLeftRotate(Node node) {
	node.right = rightRotate (node.right);
	return leftRotate (node);
	}
	private Node leftRotate(Node k1) {
	Node k2 = k1.right;
	k1.right = k2.left;
	k2.left = k1;
	k1.height = Math.max (height (k1.left), height (k1.left)) + 1;
	k2.height = Math.max (height (k2.left), height (k2.left)) + 1;
	return k2;
	}
	public void findMaxDepth() {
	Stack<Node> nodes = new Stack<> ();
	root.depth = 0;
	nodes.push (root);
	int maxDepth = 0;
	while (!nodes.isEmpty ()) {
	Node current = nodes.pop ();
	System.out.printf ("%s ", current.data);
	if (maxDepth < current.depth) {
	maxDepth = current.depth;
	}
	if (current.right != null) {
	current.right.depth = current.depth + 1;
	nodes.push (current.right);
	}
	if (current.left != null) {
	current.left.depth = current.depth + 1;
	nodes.push (current.left);
	}
	}
	System.out.println ("maxDepth = " + maxDepth);
	}
	//shortest path = breadth first search
	public void findMinDepth() {
	Queue<Node> queue = new LinkedList<> ();
	root.depth = 0;
	queue.add (root);
	int minDepth = Integer.MAX_VALUE;
	while (!queue.isEmpty ()) {
	Node poll = queue.poll ();
	if (poll.isLeaf () && minDepth > poll.depth) {
	minDepth = poll.depth;
	}
	System.out.print (" " + poll.data);
	if (poll.left != null) {
	poll.left.depth = poll.depth + 1;
	queue.add (poll.left);
	}
	if (poll.right != null) {
	poll.right.depth = poll.depth + 1;
	queue.add (poll.right);
	}
	}
	System.out.println ("minDepth = " + minDepth);
	}
	//fix this!!!
	public void traverseAndCalculateNodeTotalWeightTop2Bottom() {
	Stack<Node> stack = new Stack<> ();
	root.weight = root.data;
	stack.push (root);
	while (!stack.isEmpty ()) {
	Node peek = stack.peek ();
	if (peek.isLeaf ()) {
	Node pop = stack.pop ();
	System.out.print ("[ " + pop.data + " nw:" + pop.weight + "] ");
	} else {
	if (peek.right != null) {
	peek.right.weight = peek.weight + peek.right.data;
	stack.push (peek.right);
	peek.right = null;
	}
	if (peek.left != null) {
	peek.left.weight = peek.weight + peek.left.data;
	stack.push (peek.left);
	peek.left = null;
	}
	}
	}
	}
	public int[] averageInEachLevel() {
	int[] averages = new int[height (root)];
	Queue<Node> queue = new LinkedList<> ();
	queue.add (root);
	int currentDepth = 0;
	root.depth = 0;
	int levelSum = 0, levelMember = 0;
	while (!queue.isEmpty ()) {
	Node poll = queue.poll ();
	if (currentDepth != poll.depth) {
	System.out.print (" => sum: " + levelSum + " member: " + levelMember);
	averages[poll.depth - 1] = levelSum / levelMember;
	levelMember = 0;
	levelSum = 0;
	System.out.println (" ");
	currentDepth = poll.depth;
	}
	levelSum += poll.data;
	levelMember++;
	System.out.print (" " + poll.data);
	if (poll.left != null) {
	poll.left.depth = poll.depth + 1;
	queue.add (poll.left);
	}
	if (poll.right != null) {
	poll.right.depth = poll.depth + 1;
	queue.add (poll.right);
	}
	}
	averages[averages.length - 1] = levelSum / levelMember;
	return averages;
	}
	public Double[] averageInEachLevel2() {
	ArrayList<Double> averages = new ArrayList<> ();
	Queue<Node> queue = new LinkedList<> ();
	queue.add (root);
	List<List<Node>> levelMembers = new ArrayList<> ();
	ArrayList<Node> rootLevel = new ArrayList<> ();
	rootLevel.add (root);
	levelMembers.add (rootLevel);
	while (!queue.isEmpty ()) {
	double count = queue.size ();
	double sum = 0;
	ArrayList currentLevel = new ArrayList<> ();
	for (int i = 0; i < count; i++) {
	Node poll = queue.poll ();
	sum += poll.data;
	if (poll.right != null) {
	queue.add (poll.right);
	currentLevel.add (poll.right);
	}
	if (poll.left != null) {
	queue.add (poll.left);
	currentLevel.add (poll.left);
	}
	}
	averages.add (sum / count);
	levelMembers.add (currentLevel);
	}
	return averages.toArray (new Double[averages.size ()]);
	}
	//----
	public boolean find(int id) {
	Node current = root;
	while (current != null) {
	if (current.data == id) {
	return true;
	} else if (current.data > id) {
	current = current.left;
	} else {
	current = current.right;
	}
	}
	return false;
	}
	//while deleting you need two things ! parent and isLeftChild !
	//for the rest of the scenarios you need to go through to following considerations
	//is it root ? is it leftChild ? is it right child ?
	//Scenarios are is leaf node ? has only one right child ? has only one left child ? has two child ?
	public boolean deleteUnbalanced(int id) {
	Node parent = root;
	Node current = root;
	boolean isLeftChild = false;
	while (current.data != id) {
	parent = current;
	if (current.data > id) {
	isLeftChild = true;
	current = current.left;
	} else {
	isLeftChild = false;
	current = current.right;
	}
	if (current == null) {
	return false;
	}
	}
	//if i am here that means we have found the node
	//Case 1: if node to be deleted has no children
	if (current.left == null && current.right == null) {
	if (current == root) {
	root = null;
	}
	if (isLeftChild == true) {
	parent.left = null;
	} else {
	parent.right = null;
	}
	}
	//Case 2 : if node to be deleted has only one child
	else if (current.right == null) {
	if (current == root) {
	root = current.left;
	} else if (isLeftChild) {
	parent.left = current.left;
	} else {
	parent.right = current.left;
	}
	} else if (current.left == null) {
	if (current == root) {
	root = current.right;
	} else if (isLeftChild) {
	parent.left = current.right;
	} else {
	parent.right = current.right;
	}
	} else if (current.left != null && current.right != null) {
	//now we have found the minimum element in the right sub tree
	Node successor = getSuccessor (current);
	if (current == root) {
	root = successor;
	} else if (isLeftChild) {
	parent.left = successor;
	} else {
	parent.right = successor;
	}
	successor.left = current.left;
	}
	return true;
	}
	//from right to leftmost...
	public Node getSuccessor(Node deleleNode) {
	Node successsor = null;
	Node successsorParent = null;
	Node current = deleleNode.right;
	while (current != null) {
	successsorParent = successsor;
	successsor = current;
	current = current.left;
	}
	//check if successor has the right child, it cannot have left child for sure
	//if it does have the right child, add it to the left of successorParent.
	//successsorParent
	if (successsor != deleleNode.right) {
	successsorParent.left = successsor.right;
	successsor.right = deleleNode.right;
	}
	return successsor;
	}
	public boolean delete(int x) {
	Node parent = root;
	Node current = root;
	boolean isLeftChild = false;
	while (current.data != x) {
	parent = current;
	if (current.data < x) {
	isLeftChild = false;
	current = current.right;
	} else {
	isLeftChild = true;
	current = current.left;
	}
	if (current == null) {
	return false;// not found the X in the tree
	}
	}
	if (current.left == null && current.right == null) {
	if (current == root) {
	root = null;
	}
	if (isLeftChild) {
	parent.left = null;
	} else {
	parent.right = null;
	}
	} else if (current.right != null) {
	if (current == root) {
	root = current.right;
	}
	if (isLeftChild) {
	parent.left = current.right;
	} else {
	parent.right = current.right;
	}
	} else if (current.left != null) {
	if (current == root) {
	root = current.left;
	}
	if (isLeftChild) {
	parent.left = current.left;
	} else {
	parent.right = current.left;
	}
	} else if (current.left != null && current.right != null) {
	Node successor = getSuccessor (current);
	if (current == root) {
	root = successor;
	} else if (isLeftChild) {
	current.left = successor;
	} else {
	current.right = successor;
	}
	successor.left = current.left;
	}
	return isLeftChild;
	}
	public void insertUnBalanced(int id) {
	Node newNode = new Node (id);
	if (root == null) {
	root = newNode;
	return;
	}
	Node current = root;
	Node parent = null;
	while (true) {
	parent = current;
	if (id < current.data) {
	current = current.left;
	if (current == null) {
	parent.left = newNode;
	return;
	}
	} else {
	current = current.right;
	if (current == null) {
	parent.right = newNode;
	return;
	}
	}
	}
	}
	//---------
	public void allPathsToLeafNodesWithPreOrderDFS() {
	Stack<Node> stack = new Stack<> ();
	stack.push (root);
	List<Deque<Integer>> paths = new ArrayList<> ();
	while (!stack.isEmpty ()) {
	Node pop = stack.pop ();
	System.out.print (" " + pop.data);
	if (pop.isLeaf ()) {
	Deque<Integer> path = new ArrayDeque<> ();
	Node current = pop;
	while (current != null) {
	path.add (current.data);
	current = current.parent;
	}
	paths.add (path);
	}
	if (pop.right != null) {
	pop.right.parent = pop;
	stack.push (pop.right);
	}
	if (pop.left != null) {
	pop.left.parent = pop;
	stack.push (pop.left);
	}
	}
	System.out.println ("paths = " + paths);
	}
	public void allPathsToLeafNodesWithInOrderDFS() {
	Stack<Node> stack = new Stack<> ();
	List<Deque<Integer>> paths = new ArrayList<> ();
	Node current = root;
	while (!stack.isEmpty () || current != null) {
	if (current != null) {
	stack.push (current);
	if (current.left != null) current.left.parent = current;
	current = current.left;
	} else {
	Node pop = stack.pop ();
	System.out.println (" " + pop.data);
	if (pop.isLeaf ()) {
	Deque<Integer> path = new ArrayDeque<> ();
	Node now = pop;
	while (now != null) {
	path.add (now.data);
	now = now.parent;
	}
	paths.add (path);
	}
	current = pop.right;
	if (pop.right != null) pop.right.parent = pop;
	}
	}
	System.out.println ("paths = " + paths);
	}
	public void allPathsToLeafNodesWithBFS() {
	List<Deque<Integer>> paths = new ArrayList<> ();
	Queue<Node> queue = new LinkedList<> ();
	queue.add (root);
	while (!queue.isEmpty ()) {
	Node poll = queue.poll ();
	System.out.println ("poll = " + poll);
	if (poll.isLeaf ()) {
	Deque<Integer> path = new ArrayDeque<> ();
	Node current = poll;
	while (current != null) {
	path.add (current.data);
	current = current.parent;
	}
	paths.add (path);
	}
	if (poll.left != null) {
	poll.left.parent = poll;
	queue.add (poll.left);
	}
	if (poll.right != null) {
	poll.right.parent = poll;
	queue.add (poll.right);
	}
	}
	System.out.println ("paths = " + paths);
	}
	}
	public class Main {
	// 40
	// 20 50
	// 10 30 45 60
	// 5 15 25 35 44 46 55 61
	//4 6 14 16 24 26 34 36 43 47 54 56 62
	// 63
	// 64
	// 40 20 10 5 15 30 25 35 50 45 44 46 60 55 61
	// 5 10 15 20 25 30 35 40 44 45 46 50 55 60 61
	// 5 15 10 25 35 30 20 44 46 45 55 61 60 50 40
	public static String traversePreOrder(Node root) {
	if (root == null) {
	return "";
	}
	StringBuilder sb = new StringBuilder ();
	sb.append (root.data);
	String pointerRight = "└──";
	String pointerLeft = (root.right != null) ? "├──" : "└──";
	traverseNodes (sb, "", pointerLeft, root.left, root.right != null);
	traverseNodes (sb, "", pointerRight, root.right, false);
	return sb.toString ();
	}
	public static void traverseNodes(StringBuilder sb, String padding, String pointer, Node node, boolean hasRightSibling) {
	if (node != null) {
	sb.append ("\n");
	sb.append (padding);
	sb.append (pointer);
	sb.append (node.data);
	StringBuilder paddingBuilder = new StringBuilder (padding);
	if (hasRightSibling) {
	paddingBuilder.append ("│ ");
	} else {
	paddingBuilder.append (" ");
	}
	String paddingForBoth = paddingBuilder.toString ();
	String pointerRight = "└──";
	String pointerLeft = (node.right != null) ? "├──" : "└──";
	traverseNodes (sb, paddingForBoth, pointerLeft, node.left, node.right != null);
	traverseNodes (sb, paddingForBoth, pointerRight, node.right, false);
	}
	}
	public static void main(String[] args) {
	Tree tree = buildTree ();
	System.out.println ("Before deletion --");
	String s = traversePreOrder (tree.root);
	System.out.println (s);
	tree.deleteUnbalanced (40);
	System.out.println ("After insertion --");
	s = traversePreOrder (tree.root);
	System.out.println (s);
	System.out.println ("");
	tree = buildTree ();
	System.out.println ("Before insertion --");
	s = traversePreOrder (tree.root);
	System.out.println (s);
	tree.insertUnBalanced (12);
	System.out.println ("After insertion --");
	s = traversePreOrder (tree.root);
	System.out.println (s);
	System.out.println ("");
	tree = buildTree ();
	System.out.println ("PreOrder --");
	tree.preOrderIterative ();
	System.out.println ("");
	tree = buildTree ();
	System.out.println ("InOrder --");
	tree.inOrderIterative ();
	System.out.println ("");
	tree = buildTree ();
	System.out.println ("PostOrder --");
	tree.postOrderIterative ();
	System.out.println ("");
	System.out.println ("");
	tree = buildTree ();
	System.out.println (" Size : " + tree.size ());
	System.out.println ("");
	System.out.println ("-- tree height--");
	tree = buildTree ();
	System.out.println (" Height : " + tree.height ());
	System.out.println ("");
	System.out.println ("-- bfs recursive--");
	tree = buildTree ();
	tree.bfsRecursive ();
	System.out.println ("");
	System.out.println ("-- bfs iterative --");
	tree = buildTree ();
	tree.bfsIterative ();
	System.out.println ("");
	System.out.println ("-- each level average iterative --");
	tree = buildTree ();
	tree.averageInEachLevel ();
	System.out.println ("");
	System.out.println ("-- each level average iterative 2 --");
	tree = buildTree ();
	tree.averageInEachLevel2 ();
	System.out.println ("");
	System.out.println ("-- maxDepth --");
	tree = buildTree ();
	System.out.println ("");
	tree.findMaxDepth ();
	System.out.println ("");
	System.out.println ("-- totalNodeWeights --");
	tree = buildTree ();
	System.out.println ("");
	tree.traverseAndCalculateNodeTotalWeightTop2Bottom ();
	System.out.println ("");
	System.out.println ("-- findMinDepthToLeafNode --");
	tree = buildTree ();
	System.out.println ("");
	tree.findMinDepth ();
	System.out.println ("");
	System.out.println ("-- findMinDepthToLeafNode --");
	tree = buildTree ();
	System.out.println ("");
	tree.bfsIterativeBottom2Top ();
	System.out.println ("");
	System.out.println ("-- allPaths2LeafNodesWithPreOrderDFS --");
	tree = buildTree ();
	System.out.println ("");
	tree.allPathsToLeafNodesWithPreOrderDFS ();
	System.out.println ("");
	System.out.println ("-- allPaths2LeafNodesWithInOrderDFS --");
	tree = buildTree ();
	System.out.println ("");
	tree.allPathsToLeafNodesWithInOrderDFS ();
	System.out.println ("");
	}
	// 40
	// 20 50
	// 10 30 45 60
	// 15 25 35 55 61
	// 14 16 24 26 34 36 54 56 62
	// 63
	// 64
	private static Tree buildTree() {
	Tree tree = new Tree ();
	Node root = new Node (400);
	tree.root = root;
	tree.root.left = new Node (200);
	tree.root.right = new Node (500);
	tree.root.left.left = new Node (100);
	tree.root.left.right = new Node (300);
	tree.root.right.left = new Node (450);
	tree.root.right.right = new Node (600);
	tree.root.left.left.left = new Node (50);
	tree.root.left.left.right = new Node (150);
	tree.root.left.right.left = new Node (250);
	tree.root.left.right.right = new Node (350);
	tree.root.right.left.left = new Node (440);
	tree.root.right.left.right = new Node (460);
	tree.root.right.right.left = new Node (550);
	tree.root.right.right.right = new Node (610);
	tree.root.right.right.left.left = new Node (540);
	tree.root.right.right.left.right = new Node (560);
	tree.root.left.left.left.left = new Node (40);
	tree.root.left.left.left.right = new Node (60);
	tree.root.left.left.left.left.left = new Node (35);
	tree.root.left.left.left.left.right = new Node (45);
	tree.root.left.left.left.left.right.left = new Node (44);
	tree.root.left.left.left.left.right.right = new Node (48);
	tree.root.left.left.left.left.right.right.left = new Node (47);
	tree.root.left.left.left.left.right.right.right = new Node (49);
	tree.root.left.left.left.left.right.left.left = new Node (43);
	tree.root.left.left.right.left = new Node (140);
	tree.root.left.left.right.right = new Node (160);
	tree.root.left.right.left.left = new Node (240);
	tree.root.left.right.left.right = new Node (260);
	tree.root.left.right.right.left = new Node (340);
	tree.root.left.right.right.right = new Node (360);
	tree.root.right.left.left.left = new Node (430);
	tree.root.right.left.right.right = new Node (470);
	tree.root.right.right.right.right = new Node (620);
	tree.root.right.right.right.right.right = new Node (630);
	tree.root.right.right.right.right.right.right = new Node (640);
	return tree;
	}
	}

view raw Main.java hosted with ❤ by GitHub