Height of a binary tree using Recursion

 Pseduo Logic -Height of a binary tree is to return Max of height of left subtree and right subtree + 1

/*

The height of a node is the number of edges on the longest path from the node to a leaf.

A leaf node will have a height of 0.

*/

public class HeightBinaryTree {

     public static void main(String[] args) {

          BinarySearch bs = new BinarySearch();

          bs.insertNode(15);

          bs.insertNode(10);

          bs.insertNode(20);

          bs.insertNode(5);

          bs.insertNode(25);

          bs.insertNode(3);

          HeightBinaryTree hbt= new HeightBinaryTree();

          int height =hbt.heightBinaryTree(bs.root);

          System.out.println("Height of binary tree is "+ height);

     }

     public int heightBinaryTree(Node node){

          if(node==null)

              return 0;

          int leftHeight=heightBinaryTree(node.leftChild);

          int rightHeight=heightBinaryTree(node.rightChild);

          return Math.max(leftHeight, rightHeight)+1;

     }

}

Output:

Height of binary tree is 4

Level Order Traversal- Algo 14

 Using Queue Data structure

Approach 1 – For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.

Pseudo Code :

printLevelorder(tree)

1) Create an empty queue q

2) temp_node = root /*start from root*/

3) Loop while temp_node is not NULL

    a) print temp_node->data.

    b) Enqueue temp_node’s children (first left then right children) to q

    c) Dequeue a node from q and assign it’s value to temp_node

import java.util.LinkedList;

import java.util.Queue;

public class LevelOrderTraversal {

     public static void main(String[] args) {

          BinarySearch bs = new BinarySearch();

          bs.insertNode(20);

          bs.insertNode(10);

          bs.insertNode(25);

          bs.insertNode(5);

          bs.insertNode(15);

          bs.insertNode(23);

          bs.insertNode(8);

          bs.insertNode(12);

          LevelOrderTraversal lot= new LevelOrderTraversal();

          lot.levelOrderTraversal(bs.root);

     }

     public void levelOrderTraversal(Node node){

          Node currentNode=null;

          if(node == null)

              return;

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

          queue.add(node);

          while(!queue.isEmpty()){

              currentNode= queue.poll();

              System.out.println(currentNode.data);

              if(currentNode.leftChild!=null)

                   queue.add(currentNode.leftChild);

              if(currentNode.rightChild!=null)

                   queue.add(currentNode.rightChild);

          }

     }

}

Output:

20        10        25        5          15        23        8          12        

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