Size of a Binary Tree- Algo 13

Using Recursion and Iteration

     a)   Recursion done most of the part by it own

     b)   Iteration method use Stack Data structure in order to find size of a      binary Tree

Java Implementation of Size of binary tree

import java.util.Stack;

public class SizeBinaryTreeRec {

    public static void main(String[] args) {

         BinarySearch bs = new BinarySearch();

         bs.insertNode(10);

         bs.insertNode(5);

         bs.insertNode(2);

         bs.insertNode(7);

         bs.insertNode(15);

         bs.insertNode(12);

         bs.insertNode(20);

         int size = new SizeBinaryTreeRec().size(bs.root);

         System.out.println("Size of a Binary tree is" + size);

         int sizeUsingIteration = new SizeBinaryTreeRec()

         .sizeUsingStack(bs.root);

           System.out.println("Size of a binary tree using Iteration                                      is "+ sizeUsingIteration);

System.out.println("Size of a Leaf nodes in a binary tree using Iteration is "+ newSizeBinaryTreeRec().sizeLeafNodesUsingStack(bs.root));
}

    public int size(Node node) {

         if (node == null)

             return 0;

         int left = size(node.leftChild);

         int right = size(node.rightChild);

         return left + right + 1;

    }

      * a) Push root node in stack

        b) While stack not empty

        c) Add node rightChild in stack and move node to node                                            leftChild and increment

        d) When node =null,it'll pop from the stack which store node                         rightChild

*/

    public int sizeUsingStack(Node n) {

         Stack<Node> sizeStack = new Stack<Node>();

         Node node;

         int count = 0;

         if (n == null) {

             return 0;

         }

         sizeStack.push(n);

         while (!sizeStack.isEmpty()) {

             node = sizeStack.pop();

             while (node != null) {

                 count++;

                 if (node.rightChild != null) {

                      sizeStack.push(node.rightChild);

                 }

                 node = node.leftChild;

             }

         }

         return count;

    }

}

public int sizeLeafNodesUsingStack(Node n){

         Stack<Node> sizeStack = new Stack<Node>();

         Node node;

         int count = 0;

         if (n == null) {

             return 0;

         }

         sizeStack.push(n);

         while (!sizeStack.isEmpty()) {

             node = sizeStack.pop();

             while (node != null) {

                if(node.leftChild==null &&                                node.rightChild==null)

                 count++;

                 if (node.rightChild != null) {

                      sizeStack.push(node.rightChild);

                 }

                 node = node.leftChild;

             }

         }

         return count;

       }

    }

Output:

Size of a Binary tree is7

Size of a binary tree using Iteration is 7

Size of a Leaf nodes in a binary tree using Iteration is 4