Binary tree breadth first search algorithm

Question

In a binary tree BFS algorithm, can someone please help me understand why we do a height - 1 in the code below. I wrote this code but it never worked until I figured out online you need to do a height - 1.

public class BreadthFirstSearch {

public static int calculateHeightOfTree(Node root) {
    if (root == null) {
        return 0;
    } else {
        return 1 + Math.max(calculateHeightOfTree(root.leftNode), calculateHeightOfTree(root.rightNode));
    }
}

public static void printDataAtAllLevels(Node root, int height) {
    for (int i = 1; i <= height; i++) {
        printDataAtGivenLevel(root, i);
    }
}

public static void printDataAtGivenLevel(Node root, int height) {
    if (root == null) {
        return;
    }
    if (height == 1) {
        System.out.println(root.data);
    } else {
        printDataAtGivenLevel(root.leftNode, height - 1);
        printDataAtGivenLevel(root.rightNode, height - 1);
    }
}

public static void main(String[] args) {
    Node node = new Node(1);
    node.leftNode = new Node(2);
    node.rightNode = new Node(3);
    node.leftNode.leftNode = new Node(4);
    node.leftNode.rightNode = new Node(5);

    System.out.println("Level order traversal of binary tree is ");
    int height = calculateHeightOfTree(node);
    System.out.println("HEIGHT: " + height);
    printDataAtAllLevels(node, height);
}

Eran · Accepted Answer · 2019-11-25 07:32:24Z

1

Well, if you want to print the data of level n of the tree, that's equivalent to printing the data of level n-1 of the left and right sub-trees. Therefore, when you pass the left and right sub-trees to the recursive calls, you should request to print the data of level reduced by 1.

For example, since the root of the tree has level 1, the left and right children of the root have level 2. So if you wish to print all the data of level 2 for the original tree, that's equivalent to printing the data of level 1 for the left and right sub-trees.

answered Nov 25, 2019 at 7:32

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Tobias · Accepted Answer · 2019-11-25 07:32:40Z

0

If you would not decrease height it would always be the same value in every (recursive) method call.

Therefore the recursion would not stop because height == 1 would always be false. It would only stop because root == null would be true, because you reached the end of a sub-tree. But in this case there would be no output, but only a return.

answered Nov 25, 2019 at 7:32

Tobias

2,5753 gold badges17 silver badges34 bronze badges

Comments

Maurice Perry · Accepted Answer · 2019-11-25 07:38:16Z

0

Because the height int printDataAtGivenLevel(Node root, int height) is the height relative to the root. So if you want to print level 2 from the root, you need to print level 1 from root.left and root.right.

answered Nov 25, 2019 at 7:38

Maurice Perry

9,6782 gold badges15 silver badges28 bronze badges

Comments

Karan Matalia · Accepted Answer · 2019-11-25 08:03:03Z

0

So that you can print the height starting from the node with the lowest height to the node with the maximum height.

answered Nov 25, 2019 at 8:03

Karan Matalia

752 silver badges12 bronze badges

Comments

tevemadar · Accepted Answer · 2019-11-25 10:08:21Z

Honestly, when I read Binary tree breadth first search algorithm, I do not think about a series of depth-limited DFS traversals, but visiting nodes of a given level, and collecting the ones for the next level, rinse and repeat:

static void doStuff(Node root){
  List<Node> current=new ArrayList<>();
  current.add(root);
  int level=0;
  int total=0;
  while(current.size()>0){
    level++;
    System.out.println("Level "+level+":");
    List<Node> next=new ArrayList<>();
    for(int i=0;i<current.size();i++){
      Node node=current.get(i);
      System.out.print(node.data+" ");
      if(node.leftNode!=null)
        next.add(node.leftNode);
      if(node.rightNode!=null)
        next.add(node.rightNode);
      total++;
    }
    System.out.println();
    current=next;
  }
  System.out.println(total+" nodes visited, from "+level+" levels");
}

Then it can be tricked into one list:

static void doStuff(Node root){
  List<Node> nodes=new LinkedList<>();
  nodes.add(root);
  int level=0;
  int total=0;
  int current;
  while((current=nodes.size())>0){
    level++;
    System.out.println("Level "+level+":");
    while(current-->0){
      Node node=nodes.removeFirst();
      System.out.print(node.data+" ");
      if(node.leftNode!=null)
        nodes.add(node.leftNode);
      if(node.rightNode!=null)
        nodes.add(node.rightNode);
      total++;
    }
    System.out.println();
  }
  System.out.println(total+" nodes visited, from "+level+" levels");
}

Collectives™ on Stack Overflow

Binary tree breadth first search algorithm

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related