@Test public void testDepthFirstSearch() { for (int i = 1; i < 6; i++) { Assert.assertNotNull(Searcher.depthFirstSearch(binTree, i)); } Assert.assertNull(Searcher.depthFirstSearch(binTree, 10)); BinaryTreeNode<Integer> four = Searcher.depthFirstSearch(binTree, 4); Assert.assertNotNull(four); Assert.assertFalse(four.isLeaf()); Assert.assertNull(four.leftChild()); Assert.assertNotNull(four.rightChild()); Assert.assertEquals(Integer.valueOf(5), four.rightChild().data()); BinaryTreeNode<Integer> five = Searcher.depthFirstSearch(binTree, 5); Assert.assertTrue(five.isLeaf()); }
public static <E extends Comparable<E>> BinaryTreeNode<E> depthFirstSearch(BinarySearchTree<E> binTree, BinaryTreeNode<E> startNode, E value) { LOGGER.debug("Searching for: {}.", value); Stack<BinaryTreeNode<E>> stack = new Stack<BinaryTreeNode<E>>(); Set<BinaryTreeNode<E>> visited = new HashSet<BinaryTreeNode<E>>(); stack.push(startNode); BinaryTreeNode<E> leftChild = null; BinaryTreeNode<E> rightChild = null; BinaryTreeNode<E> currentNode = null; while (!stack.isEmpty()) { currentNode = stack.pop(); visited.add(currentNode); LOGGER.debug("Visited: {}.", visited); if (currentNode.data().equals(value)) { return currentNode; } rightChild = currentNode.rightChild(); if (rightChild != null && !visited.contains(rightChild)) { stack.push(rightChild); } leftChild = currentNode.leftChild(); if (leftChild != null && !visited.contains(leftChild)) { stack.push(leftChild); } } return null; }
Searcher { public static <E extends Comparable<E>> BinaryTreeNode<E> depthFirstSearch(BinarySearchTree<E> binTree, BinaryTreeNode<E> startNode, E value) { LOGGER.debug("Searching for: {}.", value); Stack<BinaryTreeNode<E>> stack = new Stack<BinaryTreeNode<E>>(); Set<BinaryTreeNode<E>> visited = new HashSet<BinaryTreeNode<E>>(); stack.push(startNode); BinaryTreeNode<E> leftChild = null; BinaryTreeNode<E> rightChild = null; BinaryTreeNode<E> currentNode = null; while (!stack.isEmpty()) { currentNode = stack.pop(); visited.add(currentNode); LOGGER.debug("Visited: {}.", visited); if (currentNode.data().equals(value)) { return currentNode; } rightChild = currentNode.rightChild(); if (rightChild != null && !visited.contains(rightChild)) { stack.push(rightChild); } leftChild = currentNode.leftChild(); if (leftChild != null && !visited.contains(leftChild)) { stack.push(leftChild); } } return null; } }
Searcher { public static <E extends Comparable<E>> BinaryTreeNode<E> depthFirstSearch(BinarySearchTree<E> binTree, BinaryTreeNode<E> startNode, E value) { LOGGER.debug("Searching for: {}.", value); Stack<BinaryTreeNode<E>> stack = new Stack<BinaryTreeNode<E>>(); Set<BinaryTreeNode<E>> visited = new HashSet<BinaryTreeNode<E>>(); stack.push(startNode); BinaryTreeNode<E> leftChild = null; BinaryTreeNode<E> rightChild = null; BinaryTreeNode<E> currentNode = null; while (!stack.isEmpty()) { currentNode = stack.pop(); visited.add(currentNode); LOGGER.debug("Visited: {}.", visited); if (currentNode.data().equals(value)) { return currentNode; } rightChild = currentNode.rightChild(); if (rightChild != null && !visited.contains(rightChild)) { stack.push(rightChild); } leftChild = currentNode.leftChild(); if (leftChild != null && !visited.contains(leftChild)) { stack.push(leftChild); } } return null; }  }
Searcher { public static <E extends Comparable<E>> BinaryTreeNode<E> depthFirstSearch(BinarySearchTree<E> binTree, BinaryTreeNode<E> startNode, E value) { LOGGER.debug("Searching for: {}.", value); Stack<BinaryTreeNode<E>> stack = new Stack<BinaryTreeNode<E>>(); Set<BinaryTreeNode<E>> visited = new HashSet<BinaryTreeNode<E>>(); stack.push(startNode); BinaryTreeNode<E> leftChild = null; BinaryTreeNode<E> rightChild = null; BinaryTreeNode<E> currentNode = null; while (!stack.isEmpty()) { currentNode = stack.pop(); visited.add(currentNode); LOGGER.debug("Visited: {}.", visited); if (currentNode.data().equals(value)) { return currentNode; } rightChild = currentNode.rightChild(); if (rightChild != null && !visited.contains(rightChild)) { stack.push(rightChild); } leftChild = currentNode.leftChild(); if (leftChild != null && !visited.contains(leftChild)) { stack.push(leftChild); } } return null; }  static BinaryTreeNode<E> binarySearch(BinarySearchTree<E> binTree,
			BinaryTreeNode<E> startNode, E value); static BinaryTreeNode<E> binarySearch(BinarySearchTree<E> binTree, E value); static BinaryTreeNode<E> breadthFirstSearch(BinarySearchTree<E> binTree,
			BinaryTreeNode<E> startNode, E value); static BinaryTreeNode<E> breadthFirstSearch(BinarySearchTree<E> binTree, E value); static BinaryTreeNode<E> depthFirstSearch(BinarySearchTree<E> binTree,
			BinaryTreeNode<E> startNode, E value); static BinaryTreeNode<E> depthFirstSearch(BinarySearchTree<E> binTree, E value); }
Searcher { public static <E extends Comparable<E>> BinaryTreeNode<E> depthFirstSearch(BinarySearchTree<E> binTree, BinaryTreeNode<E> startNode, E value) { LOGGER.debug("Searching for: {}.", value); Stack<BinaryTreeNode<E>> stack = new Stack<BinaryTreeNode<E>>(); Set<BinaryTreeNode<E>> visited = new HashSet<BinaryTreeNode<E>>(); stack.push(startNode); BinaryTreeNode<E> leftChild = null; BinaryTreeNode<E> rightChild = null; BinaryTreeNode<E> currentNode = null; while (!stack.isEmpty()) { currentNode = stack.pop(); visited.add(currentNode); LOGGER.debug("Visited: {}.", visited); if (currentNode.data().equals(value)) { return currentNode; } rightChild = currentNode.rightChild(); if (rightChild != null && !visited.contains(rightChild)) { stack.push(rightChild); } leftChild = currentNode.leftChild(); if (leftChild != null && !visited.contains(leftChild)) { stack.push(leftChild); } } return null; }  static BinaryTreeNode<E> binarySearch(BinarySearchTree<E> binTree,
			BinaryTreeNode<E> startNode, E value); static BinaryTreeNode<E> binarySearch(BinarySearchTree<E> binTree, E value); static BinaryTreeNode<E> breadthFirstSearch(BinarySearchTree<E> binTree,
			BinaryTreeNode<E> startNode, E value); static BinaryTreeNode<E> breadthFirstSearch(BinarySearchTree<E> binTree, E value); static BinaryTreeNode<E> depthFirstSearch(BinarySearchTree<E> binTree,
			BinaryTreeNode<E> startNode, E value); static BinaryTreeNode<E> depthFirstSearch(BinarySearchTree<E> binTree, E value); static final Logger LOGGER; }