Magic of BFS on Tree Problems
kirankrish
292

One might have come across one of the below eazy to moderate Tree problems either in phone screening or as one of the coding questions in interviews:

  • Find / Print Left view nodes
  • Find / Print Right view nodes
  • Find / Print bottom Left view node
  • Find / Print botton Right view node
  • Find/ Print Leaf nodes
  • Find the depth/ number of levels
  • Print All nodes

Here is a simple technique using BFS (Breadth firt search) to solve all of the above tree problems in one go. For the BFS (level order traversal) we use a queue and then getting the size of the queue for each level is the key which gives the number of nodes in that particular level.

I have inline comments which should make the code self explanatory.

void run_BFS(Node* root) { //Level order traversal
  if (root == nullptr)
    return;

  vector<int> LeftViewNodes;
  vector<int> RightViewNodes;
  vector<int> AllNodes;
  vector<int> LeafNodes;

  queue<Node*> q;
  q.push(root);   // start with root

  int level = 0;

  while (!q.empty()) {
    // number of nodes at current level 
    int n = q.size(); 
    level++;

    // traverse all the nodes in current level
    for (int i=1; i <= n; i++) {
      Node *tmpnode = q.front();
      q.pop();

      //i==1 first node in the level - left view node
      //i==n last node in the level - right view node
      if (i == 1) {
        LeftViewNodes.push_back(tmpnode->data);
      }

      if (i == n ) {
        RightViewNodes.push_back(tmpnode->data);
      }

      //push the current nodes to allNodes list
      AllNodes.push_back(tmpnode->data);
        
      //current nodes does not have any descendant its a leaf node
      if(tmpnode->left == nullptr && tmpnode->right == nullptr)
        LeafNodes.push_back(tmpnode->data);

      //push the descendants to queue for next level
      if(tmpnode->left)
        q.push(tmpnode->left);

      if(tmpnode->right)
        q.push(tmpnode->right);  
    }
  }
  int bottomLeftViewNode = LeftViewNodes[LeftViewNodes.size()-1];
  int bottomRightViewNode = RightViewNodes[RightViewNodes.size()-1];
  
  /*
  print_output(level, LeftViewNodes, RightViewNodes, 
						bottomLeftViewNode,  bottomRightViewNode,
						AllNodes, LeafNodes);
 */
}

This technique can be also applied with trivial changes to various other tree problems like

  • Find/ Print sibling or parent of a given node.
  • Find/ Print all the nodes of given level.
  • Find/ Print cousins of a given node.

Working example code can found at this playground: https://leetcode.com/playground/2afNmmz9

Hope you find this information interesting and useful, please Upvote. Thanks.

Comments (1)