How do implement a breadth first traversal

Question

This is what I have  I thought pre-order was the same and mixed it up with depth first   import java util LinkedList  import java util Queue   public class Exercise25 1     public static void main String   args         BinaryTree tree   new BinaryTree new Integer    10  5  15  12  4  8          System out print   nInorder          tree inorder        System out print   nPreorder          tree preorder        System out print   nPostorder          tree postorder           call the breadth method to test it      System out print   nBreadthFirst         tree breadth            class BinaryTree     private TreeNode root          Create a default binary tree      public BinaryTree                Create a binary tree from an array of objects      public BinaryTree Object   objects        for  int i   0  i  lt  objects length  i            insert objects i                     Search element o in this binary tree      public boolean search Object o        return search o  root          public boolean search Object o  TreeNode root        if  root    null          return false            if  root element equals o           return true            else         return search o  root left     search o  root right                    Return the number of nodes in this binary tree      public int size         return size root          public int size TreeNode root        if  root    null          return 0            else         return 1   size root left    size root right                    Return the depth of this binary tree  Depth is the     number of the nodes in the longest path of the tree      public int depth         return depth root          public int depth TreeNode root        if  root    null          return 0            else         return 1   Math max depth root left   depth root right                     Insert element o into the binary tree     Return true if the element is inserted successfully      public boolean insert Object o        if  root    null          root   new TreeNode o      Create a new root           else            Locate the parent node       TreeNode parent   null        TreeNode current   root        while  current    null            if    Comparable o  compareTo current element   lt  0              parent   current            current   current left                    else if    Comparable o  compareTo current element   gt  0              parent   current            current   current right                    else             return false     Duplicate node not inserted                             Create the new node and attach it to the parent node       if    Comparable o  compareTo parent element   lt  0            parent left   new TreeNode o                 else           parent right   new TreeNode o                      return true     Element inserted        public void breadth       breadth root            Implement this method to produce a breadth first      search traversal   public void breadth TreeNode root         if  root    null            return         System out print root element               breadth root left         breadth root right              Inorder traversal      public void inorder         inorder root              Inorder traversal from a subtree      private void inorder TreeNode root        if  root    null          return            inorder root left       System out print root element             inorder root right              Postorder traversal      public void postorder         postorder root              Postorder traversal from a subtree      private void postorder TreeNode root        if  root    null          return            postorder root left       postorder root right       System out print root element                    Preorder traversal      public void preorder         preorder root              Preorder traversal from a subtree      private void preorder TreeNode root        if  root    null          return            System out print root element             preorder root left       preorder root right               Inner class tree node      private class TreeNode       Object element      TreeNode left      TreeNode right       public TreeNode Object o          element   o

User · Answer

Use the following algorithm to traverse in breadth first search-

First add the root node into the queue with the put method.
Iterate while the queue is not empty.
Get the first node in the queue, and then print its value.
Add both left and right children into the queue (if the current nodehas children).
Done. We will print the value of each node, level by level,by poping/removing the element

Code is written below-

    Queue<TreeNode> queue= new LinkedList<>();
    private void breadthWiseTraversal(TreeNode root) {
        if(root==null){
            return;
        }
        TreeNode temp = root;
        queue.clear();
        ((LinkedList<TreeNode>) queue).add(temp);
        while(!queue.isEmpty()){
            TreeNode ref= queue.remove();
            System.out.print(ref.data+" ");
            if(ref.left!=null) {
                ((LinkedList<TreeNode>) queue).add(ref.left);
            }
            if(ref.right!=null) {
                ((LinkedList<TreeNode>) queue).add(ref.right);
            }
        }
    }

User · Answer

This code which you have written  is not producing correct BFS traversal   This is the code you claimed is BFS  but in fact this is DFS        search traversal   public void breadth TreeNode root         if  root    null            return         System out print root element               breadth root left         breadth root right

User · Answer

Breadth first search  Queue lt TreeNode gt  queue   new LinkedList lt BinaryTree TreeNode gt      public void breadth TreeNode root        if  root    null          return      queue clear        queue add root       while  queue isEmpty             TreeNode node   queue remove            System out print node element                 if node left    null  queue add node left           if node right    null  queue add node right

User · Answer

traverse public void traverse         if node    null          System out println  Empty tree        else               Queue lt Node gt  q  new LinkedList lt Node gt             q add node           while q peek      null                        Node temp   q remove                System out println temp getData                 if temp left    null                  q add temp left               if temp right    null                  q add temp right

User · Answer

It doesn t seem like you re asking for an implementation  so I ll try to explain the process   Use a Queue   Add the root node to the Queue   Have a loop run until the queue is empty   Inside the loop dequeue the first element and print it out   Then add all its children to the back of the queue  usually going from left to right    When the queue is empty every element should have been printed out   Also  there is a good explanation of breadth first search on wikipedia  http   en wikipedia org wiki Breadth-first search

User · Answer

Breadth first is a queue  depth first is a stack   For breadth first  add all children to the queue  then pull the head and do a breadth first search on it  using the same queue   For depth first  add all children to the stack  then pop and do a depth first on that node  using the same stack

User · Answer

public void breadthFirstSearch Node root  Consumer lt String gt  c        List lt Node gt  queue   new LinkedList lt  gt          queue add root        while   queue isEmpty              Node n   queue remove 0           c accept n value            if  n left    null              queue add n left           if  n right    null              queue add n right             And the Node   public static class Node       String value      Node left      Node right       public Node final String value  final Node left  final Node right            this value   value          this left   left          this right   right

User · Answer

public static boolean BFS ListNode n  int x           if n  null              return false           Queue lt ListNode lt Integer gt  gt  q   new Queue lt ListNode lt Integer gt  gt     ListNode lt Integer gt  tmp   new ListNode lt Integer gt      q enqueue n   tmp   q dequeue    if tmp val    x       return true    while tmp    null       for ListNode lt Integer gt  child  n getChildren             if child val    x               return true                    q enqueue child              tmp   q dequeue      return false

User · Answer

For implementing the breadth first search  you should use a queue  You should push the children of a node to the queue  left then right  and then visit the node  print data   Then  yo should remove the node from the queue  You should continue this process till the queue becomes empty  You can see my implementation of the BFS here  https   github com m-vahidalizadeh foundations blob master src algorithms TreeTraverse java

[java] How do implement a breadth first traversal?

Examples related to java

Examples related to breadth-first-search