Breadth first traversal of a binary tree in Java?

Question

I'm trying to implement a breadth first traversal method for Binary Trees in Java. I've referenced multiple examples here and none have seemed to help.

public String breadthFirstTraverse(){
    MyQueue<BinaryNode<T>> travQ = new MyQueue<BinaryNode<T>>();
    MyQueue<T> mq = new MyQueue<T>();
    if(root == null){
        return "";
    }
    mq.enqueue(root.getData());
    travQ.enqueue(root);
    BinaryNode<T> node = root;
    while(travQ.size() != 0){
        node = travQ.dequeue();
        if (node.getLeftNode().getData() != nullSymbol){
            mq.enqueue(node.getLeftNode().getData());
            travQ.enqueue(node.getLeftNode());
        }
        if (node.getRightNode().getData() != nullSymbol){
            mq.enqueue(node.getRightNode().getData());
            travQ.enqueue(node.getRightNode());
        }
    }
    return mq.toString();
}

score 0 · Answer 1 · edited Mar 20 '15 at 09:55

0

Try this

public static void printBFS(TreeNode root){
    Deque<TreeNode> a=new ArrayDeque<TreeNode>();
    a.addLast(root);
    while(!a.isEmpty()){
        TreeNode t=a.removeFirst();
        System.out.println(t.payload);
        if(t.left!=null){
            a.addLast(t.left);
        }
        if(t.right!=null){
            a.addLast(t.right);

        }   
    }
}

edited Mar 20 '15 at 09:55

Vincent Chen

17
4

answered Mar 20 '15 at 09:04

Solsta

11
3

You might want to edit your code properly so that it all fits in one grey block – EdmDroid Mar 20 '15 at 09:09

score -1 · Answer 2 · answered Oct 02 '21 at 11:53

-1

With java 8 syntax

void bfsTraverse(Node node, Queue<Node> tq) {
    if (node == null) {
        return;
    }
    System.out.print(" " + node.value);
    Optional.ofNullable(node.left).ifPresent(tq::add);
    Optional.ofNullable(node.right).ifPresent(tq::add);
    bfsTraverse(tq.poll(), tq);
}

Then invoke this method with root Node and a new object of Queue interface implementation

bfsTraverse(root, new LinkedList<>());

answered Oct 02 '21 at 11:53

Asanka Siriwardena

871
13
18

[Don't use Optionals for conditional logic.](https://stackoverflow.com/a/56235329/5515060) – Lino Oct 02 '21 at 12:03
@Lino What is the drawback? It does the same with more elegant way – Asanka Siriwardena Oct 02 '21 at 12:08
@Lino For me I don't like null checks with if. Voting down answers for your personal preference, is not nice. – Asanka Siriwardena Oct 02 '21 at 12:22
Using `Optional` creates unnecessary objects. The method references are fairly advanced programming stuff that can be done shorter in traditional, basic code. Even though `if (node.left != null) tq.add(node.left);` repeats `node.left`, it is still shorter. – Roland Illig Nov 01 '21 at 13:44

Breadth first traversal of a binary tree in Java?

2 Answers2