CODEWITHSUNDEEP
java
rickygrimes
rickygrimes

Reputation: 2716

Binary tree breadth first search algorithm

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);
}

Upvotes: 1

Views: 143

Answers (5)

tevemadar
tevemadar

Reputation: 13205

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");
}

Upvotes: 0

Karan Matalia
Karan Matalia

Reputation: 75

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

Upvotes: 0

Maurice Perry
Maurice Perry

Reputation: 9651

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.

Upvotes: 0

Tobias
Tobias

Reputation: 2575

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.

Upvotes: 0

Eran
Eran

Reputation: 393771

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.

Upvotes: 1

Related Questions