Scenario

Implement an algorithm that searches the binary tree one level at a time, left to right. The traversal starts from the root node and finishes at the leaf node.

Apply BFS traversal in Java.

Steps for Completion

1. Implement the psuedocode algorithm from Snippet 3.14 (shown below) in a public method called printBfs()in SimpleBinaryTree. The return value should be void and it should print each node on a newline.

breadthFirstSearch(root) if (root != null) queue = createQueue() enqueue(queue, root) while (not isEmpty(queue)) node = dequeue(queue) process(node) if(node.left != null) enqueue(queue, node.left) if(node.right != null) enqueue(queue, node.right)

^{Snippet 3.14}

Tasks

Implement the BFS algorithm in the printBfs() method.

Output values were not hard coded into the program.

Code given:

import java.util.LinkedList; import java.util.Optional; import java.util.Queue;

public class SimpleBinaryTree implements BinaryTree { protected BinaryTreeNode root;

public void put(K key, V value) { if (root == null) root = new BinaryTreeNode<>(key, value); else put(key, value, root); }

private void put(K key, V value, BinaryTreeNode node) { if (((Comparable) key).compareTo(node.getKey()) == 0) { node.setKey(key); node.setValue(value); } else if (((Comparable) key).compareTo(node.getKey()) < 0) { if (node.getLeft().isPresent()) put(key, value, node.getLeft().get()); else node.setLeft(new BinaryTreeNode<>(key, value)); } else { if (node.getRight().isPresent()) put(key, value, node.getRight().get()); else node.setRight(new BinaryTreeNode<>(key, value)); } }

public Optional get(K key) { return Optional.ofNullable(root).flatMap(n -> get(key, n)); }

private Optional get(K key, BinaryTreeNode node) { if (((Comparable) key).compareTo(node.getKey()) == 0) return Optional.of(node.getValue()); else if (((Comparable) key).compareTo(node.getKey()) < 0) return node.getLeft().flatMap(n -> get(key, n)); else return node.getRight().flatMap(n -> get(key, n)); }

public Optional minKey() { return Optional.ofNullable(root).map(this::minKey); }

protected K minKey(BinaryTreeNode node) { return node.getLeft().map(this::minKey).orElse(node.getKey()); }

public void printBfs() { // write your code here }

public void printDfs() { Optional.ofNullable(root).ifPresent(this::printDfs); }

private void printDfs(BinaryTreeNode node) { //System.out.println("PREORDER " + node.getKey()); node.getLeft().ifPresent(this::printDfs); System.out.println("INORDER " + node.getKey()); node.getRight().ifPresent(this::printDfs); //System.out.println("POSTORDER " + node.getKey()); }

public static void main(String[] args) { SimpleBinaryTree binaryTree = new SimpleBinaryTree(); System.out.println(binaryTree.minKey()); binaryTree.put(457998224, "Isabel"); binaryTree.put(366112467, "John"); binaryTree.put(671031776, "Ruth"); binaryTree.put(225198452, "Sarah"); binaryTree.put(419274013, "Peter"); binaryTree.put(751965387, "Tom");

System.out.println(binaryTree.get(457998224)); System.out.println(binaryTree.get(366112467)); System.out.println(binaryTree.get(671031776)); System.out.println(binaryTree.get(225198452)); System.out.println(binaryTree.get(419274013)); System.out.println(binaryTree.get(751965387));

binaryTree.put(751965387, "Sam");

System.out.println(binaryTree.get(751965387)); System.out.println(binaryTree.get(999999999)); System.out.println(binaryTree.minKey());

binaryTree.printDfs(); binaryTree.printBfs(); } }