CareerCup

i would ask - what specific type of DFS you are looking for - in-order, pre-order, post-order?

All Related to tree Traversal

package datastructure;

public class BinaryTreeTraversal {

	public static Node<Integer> node;

	public static Node<Integer> sortedArrayToBST(int arr[], int start, int end) {
		if (start > end)
			return null;

		int mid = start + (end - start) / 2;
		Node<Integer> node = new Node<Integer>();
		node.setValue(arr[mid]);

		node.left = sortedArrayToBST(arr, start, mid - 1);
		node.right = sortedArrayToBST(arr, mid + 1, end);
		return node;
	}

	public static void main(String[] args) {

		int[] test = new int[] { 1, 2, 3, 4, 5, 6, 7 };
		Node<Integer> node = sortedArrayToBST(test, 0, test.length - 1);

		System.out.println("preOrderTraversal >> ");

		preOrderTraversal(node);

		System.out.println("");

		System.out.println("inOrderTraversal >> ");

		inOrderTraversal(node);

		System.out.println("");

		System.out.println("postOrderTraversal >> ");

		postOrderTraversal(node);

		System.out.println("");

		searchInTree(node, 7);

		System.out.println("");

		System.out.println("Alter tree");

		reverseTree(node);

		

		System.out.println("preOrderTraversal >> ");

		preOrderTraversal(node);

		System.out.println("");

		System.out.println("inOrderTraversal >> ");

		inOrderTraversal(node);

		System.out.println("");

		System.out.println("postOrderTraversal >> ");

		postOrderTraversal(node);
		
		

	}

	public static void preOrderTraversal(Node<Integer> node) {

		if (node != null) {

			System.out.print(" " + node.toString());
			preOrderTraversal(node.left);
			preOrderTraversal(node.right);
		}

	}

	public static void inOrderTraversal(Node<Integer> node) {

		if (node != null) {

			inOrderTraversal(node.left);
			System.out.print(" " + node.toString());
			inOrderTraversal(node.right);
		}

	}

	public static void postOrderTraversal(Node<Integer> node) {

		if (node != null) {

			postOrderTraversal(node.left);

			postOrderTraversal(node.right);

			System.out.print(" " + node.toString());
		}

	}

	public static void reverseTree(Node<Integer> node) {

		if (node != null) {

			Node<Integer> temp = node.left;

			node.left = node.right;
			node.right = temp;

			reverseTree(node.left);

			reverseTree(node.left);

		}

	}

	public static void searchInTree(Node<Integer> node, int key) {

		if (node != null) {

			if (node.value.equals(key)) {

				System.out.println("Found -- >>" + node.value);
				
				return ;

			} else {

				if (key < node.value.intValue()) {

					searchInTree(node.left, key);
				} else {

					searchInTree(node.right, key);
				}
			}
		}
	}

}

// Depth first search in preorder.
void DepthFirstSearch(Tree * t, Visitor &v) {
    if (t == NULL) return;
    Stack <Tree> dfs;
    dfs.push(t);
    v.BeginGroup();
    while (dfs.isNotEmpty()) {
        Tree *current = dfs.pop();
         v.Visit(current);
         if (current->Right) {
             dfs.push(current->Right);
         }
         if (current->Left) {
             dfs.push(current->Left);
         }
    }
    v.EndGroup();
}

was this asked in fone interview ? or on site