BST: Breadth First Search
This problem will use a ArrayDeque which implements a Queue.
Complete the toString method for a Binary Search Tree to generate a String that visits the node of a BST at each level before moving to the next level.
The BFS algorithm for trees works by utilizing a queue of nodes to preserve the traversal order. Initially, the queue includes only the root node. The algorithm continues to execute the following steps while the queue contains one or more nodes:
- Remove the first node from the queue.
- If the current node is the target of the search, the search terminates.
- Otherwise, append the children of the current node to the end of the queue and repeat the steps.
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
To traverse the tree using BFS, we start by adding the root node (8) to a queue. In the first iteration, we visit the root node (8) and enqueue its children, which are 3 and 10. In the second iteration, we dequeue 3, visit it, and enqueue its children, which are 1 and 6. Then we dequeue 10, visit it, and enqueue its child 14. In the third iteration, we dequeue 1 and visit it. The next dequeued nodes are 6 and 14, which we visit and enqueue their children (4 and 7 for 6, and 13 for 14). Finally, we dequeue 4, 7, and 13, and visit them in that order.
The setup:
You are writing the toString in a subclass of the BST class. The head node of the BST class is protected hence the subclass has direct access to it.
public class BST{
proctected Node head;
}
public class Node{
private Node left;
private Node right;
private int data;
/* return left node, null if no left node */
public Node getLeft(){ /* implementation not shown */ }
/* return right node, null if no right node */
public Node getRight(){ /* implementation not shown */ }
/* return data of node */
public int getData(){ /* implementation not shown */ }
}