Program to Calculate Size of a Binary tree

Number of nodes available in a tree will be called size of tree. Below is the recursive program to calculate size of a binary tree.

       

package dataStructure.tree;

public class SizeOfTree {

 public static void main(String[] args) {
  
  Node rL = new Node(null, 5, null);
  Node rR = new Node(null, 15, null);
  Node root = new Node(rL, 10, rR);
  
  System.out.println(sizeOfTree(root));
 }
 
 public static int sizeOfTree(Node root){
  if(null == root){
   return 0;
  }
  return sizeOfTree(root.left) + 1 + sizeOfTree(root.right);
 }
 private static class Node{
  @SuppressWarnings("unused")
  public int key;
  public Node left;
  public Node right;
  /**
   * @param key
   * @param left
   * @param right
   */
  public Node(Node left, int key, Node right) {
   this.key = key;
   this.left = left;
   this.right = right;
  }
 }

}

        
 

Breadth First Traversal Or Level Order Traversal

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.

Time complexity:

BFS require O(n) time as it visits every node exactly once.

Extra Space:

Extra Space required for Level Order Traversal is O(w) where w is maximum width of Binary Tree. 

Output : 1 2 3 4 5 6 7

Java Code:

package dataStructure.tree;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

import java.util.Queue;

/**

 * @author Rajendar Kumar

 *

 */

public class BFSWithQueue {

/**

* @param args

*/

public static void main(String[] args) {

Node rLl = new Node(null, 4, null);

Node rLr = new Node(null, 5, null);

Node rRl = new Node(null, 6, null);

Node rRr = new Node(null, 7, null);

Node rL = new Node(rLl, 2, rLr);

Node rR = new Node(rRl, 3, rRr);

Node root = new Node(rL, 1, rR);

List<Integer> list =bfs(root);

for (Integer integer : list) {

System.out.print(integer+" ");

}

}

public static List<Integer> bfs(Node root){

List<Integer> list = new ArrayList<>();

Queue<Node> hList = new LinkedList<>();

Node temp = root;

while(null != temp){

list.add(temp.key);

if(null != temp.left){

hList.add(temp.left);

}

if(null != temp.right){

hList.add(temp.right);

}

temp = hList.poll();

}

return list;

}

}

package dataStructure.tree;

/**

 * @author Rajendar Kumar

 *

 */

public class Node {

public int key;

public Node left;

public Node right;

public Node(Node left, int key, Node right) {

this.key = key;

this.left = left;

this.right = right;

}

}