Oct 27, 2013

Textual description of firstImageUrl

Find size of binary tree in Java - Iterative and recursive

Size of binary tree is total number of nodes in the given binary tree.For the following binary tree size is 11. In this post we have discussed both recursive and iterative approach to find size of binary tree. 

Sample code for searching  an element in binary tree in Java - recursive approach 
Algorithm:-
1. Traverse given binary tree and increment size by 1 for each node.
2. Call recursive method for each left and right child and repeat step 1 and step 2.
3. While returning from leaf to root, size is added and returned.
Time and space complexity :- Time complexity and space complexity is order of O(n).
/* Recursive approach to find total number of nodes */
public int findSizeOfBinaryTreeRecursive(Node root) {
int size = 0;
if (root == null) {
return 0;
}
/*
* for each node increment size and call function recursively for left
* and right child.
*/
size = 1 + findSizeOfBinaryTreeRecursive(root.leftChild)
+ findSizeOfBinaryTreeRecursive(root.rightChild);
return size;
}

Sample code for searching  an element in binary tree in Java - iterative approach 
Algorithm:- 
1. Do level order traversal and increment size for each node.

2. Once queue is empty, return size of binary tree. 
Note:-
We can also use other iterative traversals(preorder, postorder and inorder) for calculating size of tree.
Time and space complexity :-
Time complexity and space complexity is order of O(n).

/* Iterative approach to find total number of nodes-level order traversal */
public int findSizeOfBinaryTreeIterative(Node root) {
Node temp;
int size = 0;
Queue<Node> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
temp = queue.remove();
size++; // Increment size on each pop up operation
Node lc = temp.leftChild;
Node rc = temp.rightChild;
if (lc != null) {
queue.add(lc);
}
if (rc != null) {
queue.add(rc);
}

}
return size;
}

Complete sample program -finding size of binary tree in Java (Iterative and Recursive) 

package com.devinline.trees;

import java.util.ArrayDeque;
import java.util.Queue;

public class SizeOfBinaryTree {
/* Iterative approach to find total number of nodes-level order traversal */
public int findSizeOfBinaryTreeIterative(Node root) {
Node temp;
int size = 0;
Queue<Node> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
temp = queue.remove();
size++; // Increment size on each pop up operation
Node lc = temp.leftChild;
Node rc = temp.rightChild;
if (lc != null) {
queue.add(lc);
}
if (rc != null) {
queue.add(rc);
}

}
return size;
}

/* Recursive approach to find total number of nodes */
public int findSizeOfBinaryTreeRecursive(Node root) {
int size = 0;
if (root == null) {
return 0;
}
/*
* for each node increment size and call function recursively for left
* and right child.
*/
size = 1 + findSizeOfBinaryTreeRecursive(root.leftChild)
+ findSizeOfBinaryTreeRecursive(root.rightChild);
return size;
}

public static void main(String[] args) {
SizeOfBinaryTree sizeObj = new SizeOfBinaryTree();
Node root = sizeObj.new BinaryTree().createTree();
int size = sizeObj.findSizeOfBinaryTreeIterative(root);
System.out.println("Iterative -size of binary tree :- " + size);

size = sizeObj.findSizeOfBinaryTreeRecursive(root);
System.out.println("Recursive size of binary tree :- " + size);

}

class Node {
private int data;
private Node leftChild;
private Node rightChild;

public Node(int data) {
this.data = data;
leftChild = null;
rightChild = null;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public Node getLeftChild() {
return leftChild;
}

public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}

public Node getRightChild() {
return rightChild;
}

public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}
}

class BinaryTree {
Node root;

public BinaryTree() {
root = null;
}

public Node createTree() {
if (root == null) {
root = new Node(12);
}
root.setLeftChild(new Node(23));
root.setRightChild(new Node(18));
root.getLeftChild().setLeftChild(new Node(11));
root.getLeftChild().setRightChild(new Node(43));
root.getRightChild().setRightChild(new Node(27));
root.getRightChild().setLeftChild(new Node(12));
root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
root.getLeftChild().getLeftChild().setRightChild(new Node(78));
root.getRightChild().getLeftChild().setRightChild(new Node(98));
root.getRightChild().getLeftChild().setLeftChild(new Node(32));
return root;
}
}
}
=======Sample output========
Iterative -size of binary tree :-   11
Recursive size of binary tree :-  11
=========================

Oct 25, 2013

Textual description of firstImageUrl

Iterative(non-recursive) postorder traversal of binary tree in Java - Using one stack

Iterative postorder traversal is not easy as iterative preorder and iterative inorder. Why? -In preorder and inorder traversal after visiting node it is removed from stack and we do not need  visit it again. However in postorder traversal, after processing both left and right subtree control returns back to current node and each node in post order traversal is traversed twice, once after visiting left subtree and another after visiting right subtree. So the trick here is to devise some way to differentiate between - whether we are returning from left subtree and right subtree.
"After popping of element from stack - check whether popped element and right child of stack top element are same or not" - if same we have covered both left and right subtree, pop one more element and display otherwise, process right child.

Node visit sequence in postorder -  56 78 11 43 23 98 12 18 12
Algorithm:-
  1. If tress is not empty(root is not null), push all right child followed by current node into stack.
  2. Loop until stack is not empty. Pop an element and check whether popped element has right child or not -
    If right child exist and poppedElement.rightChild == stackTop, then process right child before(pop stack and puch popped element back to stack)
    Otherwise, we have processed both left and right child - display popped element 
  3.  Repeat 1 to 3, and exit outer loop when stack is empty. 
  4. Process/display root of the tree.
Time and space complexity :- Time complexity is order of O(n) and space complexity is O(n).

Sample code for postorder traversal of binary tree in Java - Using one stack 

public String iterativePostorderTraversalUsingOneStack(Node root) {
 StringBuffer sbf = new StringBuffer();
 /* java.util.Stack */
 Stack<Node> stack = new Stack<>();
 if (root != null) {
  while (true) {
   /*
    * Traverse tree until left child exist and push right and
    * current node into stack
    */
   while (root != null) {
    if (root.rightChild != null)
     stack.push(root.rightChild);
    stack.push(root);
    root = root.leftChild;
   }

   /* Pop an element from stack */
   root = stack.pop();

   /* Exit outer loop, if stack is empty */
   if (stack.isEmpty()) {
    break;
   } else {
    /*
     * check whether root's right child exist or not .If exist
     * process it before root
     */
    if (root.rightChild != null
      && root.rightChild.equals(stack.peek())) {
     stack.pop();
     stack.push(root);
     root = root.rightChild;
    } else {
     sbf.append(root.getData() + " ");
     root = null;
    }
   }
  }
 }
 /* process root of the tree,once stack is empty and root is not null*/
 if (root != null) {
  sbf.append(root.data);
 }
 return sbf.toString();
}
Explanation:- As discussed in algorithm, traverse tree and push right child followed by current node (root) into stack. On each pop operation, check whether right child of that popped element exist or not(root.rightChild != null && root.rightChild.equals(stack.peek()), if exist pop the current eleemnt from stack which is right child of tree and push previously popped element(root) otherwise process node because both left and right has been processed.

Complete sample program of postorder traversal of binary tree in Java - Using one stack

package com.devinline.trees;

import java.util.Stack;

public class IterativePostOrderUsingOneStack {
public String iterativePostorderTraversalUsingOneStack(Node root) {
 StringBuffer sbf = new StringBuffer();
 /* java.util.Stack */
 Stack<Node> stack = new Stack<>();
 if (root != null) {
  while (true) {
   /*
    * Traverse tree until left child exist and push right and
    * current node into stack
    */
   while (root != null) {
    if (root.rightChild != null)
     stack.push(root.rightChild);
    stack.push(root);
    root = root.leftChild;
   }

   /* Pop an element from stack */
   root = stack.pop();

   /* Exit outer loop, if stack is empty */
   if (stack.isEmpty()) {
    break;
   } else {
    /*
     * check whether root's right child exist or not .If exist
     * process it before root
     */
    if (root.rightChild != null
      && root.rightChild.equals(stack.peek())) {
     stack.pop();
     stack.push(root);
     root = root.rightChild;
    } else {
     sbf.append(root.getData() + " ");
     root = null;
    }
   }
  }
 }
 /* process root of the tree,once stack is empty */
 if (root != null) {
  sbf.append(root.data);
 }
 return sbf.toString();
}

 public static void main(String[] args) {
  IterativePostOrderUsingOneStack ipo2SObj = new IterativePostOrderUsingOneStack();
  Node root = ipo2SObj.new BinaryTree().createTree();
  String nodesStr = ipo2SObj
    .iterativePostorderTraversalUsingOneStack(root);
  System.out.println("Postorder traversal is: " + nodesStr);
 }

 class BinaryTree {
  Node root;

  public BinaryTree() {
   root = null;
  }

  public Node createTree() {
   if (root == null) {
    root = new Node(12);
   }
   root.setLeftChild(new Node(23));
   root.setRightChild(new Node(18));
   root.getLeftChild().setLeftChild(new Node(11));
   root.getLeftChild().setRightChild(new Node(43));
   root.getRightChild().setLeftChild(new Node(12));
   root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
   root.getLeftChild().getLeftChild().setRightChild(new Node(78));
   root.getRightChild().getLeftChild().setRightChild(new Node(98));
   return root;
  }
 }

 class Node {

  private int data;
  private Node leftChild;
  private Node rightChild;

  public Node(int data) {
   this.data = data;
   leftChild = null;
   rightChild = null;
  }

  public int getData() {
   return data;
  }

  public void setData(int data) {
   this.data = data;
  }

  public Node getLeftChild() {
   return leftChild;
  }

  public void setLeftChild(Node leftChild) {
   this.leftChild = leftChild;
  }

  public Node getRightChild() {
   return rightChild;
  }

  public void setRightChild(Node rightChild) {
   this.rightChild = rightChild;
  }
 }
}
======Sample output==============
Postorder traversal is: 56 78 11 43 23 98 12 18 12
===============================


Oct 15, 2013

Textual description of firstImageUrl

Find number of full and half nodes in binary tree

Problem Statement :- Find Number of full-nodes in given binary tree.
Full-node of binary tree  - has both left and right child non-null.
Half node of binary tree is 
Left Binary tree(Tree 1) and Right binary tree(Tree 2)
No of full and half nodes of binary tree(left side) :-    5 and 2
No of full and half nodes of binary tree(right side) :-  2 and 3

Number of full and half nodes of binary tree
 - Iterative approach 
Algorithm : Idea here is to do level order traversal and check for whether left and right child is not null for a given node. If true, increment count for fullNodeCount and similarly, if one of the left or right child is null, increment count of halfNodeCount.
1. Loop until queue is not empty.
2. Do check for null condition of left and right child, if true increment count for fullNodeCount(both left and right is not null) and halfNodeCount (One of left and right is null).
3. Once all nodes has been traversed, fullNodeCount and halfNodeCount has number of full nodes and half nodes of binary tree.
Time and space complexity :- TC = O(n) and SC = O(n), n is number of nodes in given binary tree.
Sample code for finding number of full nodes and half nodes in binary tree
/* Iterative method to find no. full nodes in a binary tree. */
public int[] findNumberOfFullNodesIterative(Node root) {
 int[] fullNhalfNodesCount = { 0, 0 };
 Queue<Node> queue = new ArrayDeque<>();
 queue.add(root);
 if (root != null) {
  while (!queue.isEmpty()) {
   root = queue.remove();
   /* Full node has both left and right child */
   if (root.leftChild != null && root.rightChild != null) {
    fullNhalfNodesCount[0] += 1;
   }
   /* Half node has one of the left and right child is null */
   if ((root.leftChild == null || root.rightChild == null)
     && !(root.leftChild == null && 
     root.rightChild == null)) {
    fullNhalfNodesCount[1] += 1;
   }
   Node lc = root.leftChild;
   Node rc = root.rightChild;
   if (lc != null) {
    queue.add(lc);
   }
   if (rc != null) {
    queue.add(rc);
   }
  }
 }
 return fullNhalfNodesCount;
}

Number of full and half nodes of binary tree
 - Recursive approach 
Algorithm :- Do recursive pre-order traversal and  check for full/half nodes and increment counter accordingly.
1. Make recursive call and check for full and half nodes.
2. Increment fullNodes[0] for full node and  fullNodes[1] for half nodes. 
3. Once all nodes is traversed, static fullNodes array has count of full/half nodes.
Note:- 
fullNodes[] is a static array, a class variable.
Sample program for find diameter of binary tree - time complexity O(n)
/* Recursive method to find no. full nodes in a binary tree. */
public void findNumberOfFullNodesRecursive(Node root) {
 if (root == null) {
  return;
 }
 /* Full node has both left and right child */
 if (root.leftChild != null && root.rightChild != null) {
  /* increment static variable */
  fullNodes[0] += 1;
 }
 /* Half node has one of the left and right child is null */
 if ((root.leftChild == null || root.rightChild == null)
   && !(root.leftChild == null && root.rightChild == null)) {
  fullNodes[1] += 1;
 }
 findNumberOfFullNodesRecursive(root.leftChild);
 findNumberOfFullNodesRecursive(root.rightChild);
}

Complete sample program- number of full and half nodes of binary tree 

package com.devinline.trees;

import java.util.ArrayDeque;
import java.util.Queue;

public class FullNodesBinaryTree {
 static int[] fullNodes = { 0, 0 };

 /* Iterative method to find no. full nodes in a binary tree. */
 public int[] findNumberOfFullNodesIterative(Node root) {
  int[] fullNhalfNodesCount = { 0, 0 };
  Queue<Node> queue = new ArrayDeque<>();
  queue.add(root);
  if (root != null) {
   while (!queue.isEmpty()) {
    root = queue.remove();
    /* Full node has both left and right child */
    if (root.leftChild != null && root.rightChild != null) {
     fullNhalfNodesCount[0] += 1;
    }
    /* Half node has one of the left and right child is null */
    if ((root.leftChild == null || root.rightChild == null)
      && !(root.leftChild == null && 
      root.rightChild == null)) {
     fullNhalfNodesCount[1] += 1;
    }
    Node lc = root.leftChild;
    Node rc = root.rightChild;
    if (lc != null) {
     queue.add(lc);
    }
    if (rc != null) {
     queue.add(rc);
    }
   }
  }
  return fullNhalfNodesCount;
 }

 /* Recursive method to find no. full nodes in a binary tree. */
 public void findNumberOfFullNodesRecursive(Node root) {
  if (root == null) {
   return;
  }
  /* Full node has both left and right child */
  if (root.leftChild != null && root.rightChild != null) {
   /* increment static variable */
   fullNodes[0] += 1;
  }
  /* Half node has one of the left and right child is null */
  if ((root.leftChild == null || root.rightChild == null)
    && !(root.leftChild == null && root.rightChild == null)) {
   fullNodes[1] += 1;
  }
  findNumberOfFullNodesRecursive(root.leftChild);
  findNumberOfFullNodesRecursive(root.rightChild);
 }

 public static void main(String[] args) {
  FullNodesBinaryTree nbt = new FullNodesBinaryTree();
  Node root = nbt.new BinaryTree().createTree1();

  int[] count = nbt.findNumberOfFullNodesIterative(root);
  System.out.print("Numbers of full nodes and half nodes "
    + "in binary tree-1 (Iterative): ");
  System.out.println(count[0] + " and " + count[1]);

  nbt.findNumberOfFullNodesRecursive(root);
  System.out.print("Numbers of full nodes and half nodes "
    + "in binary tree-1 (Recursive): ");
  System.out.println(fullNodes[0] + " and " + fullNodes[1]);
  /* Reset static variable to 0 */
  fullNodes[0] = 0;
  fullNodes[1] = 0;

  root = nbt.new BinaryTree().createTree2();
  count = nbt.findNumberOfFullNodesIterative(root);
  System.out.print("Numbers of full nodes and half nodes "
    + "in binary tree-2 (Iterative): ");
  System.out.println(count[0] + " and " + count[1]);
  nbt.findNumberOfFullNodesRecursive(root);
  System.out.print("Numbers of full nodes and half nodes "
    + "in binary tree-2 (Recursive): ");
  System.out.println(fullNodes[0] + " and " + fullNodes[1]);

 }

 class Node {
  private int data;
  private Node leftChild;
  private Node rightChild;

  public Node(int data) {
   this.data = data;
   leftChild = null;
   rightChild = null;
  }

  public int getData() {
   return data;
  }

  public void setData(int data) {
   this.data = data;
  }

  public Node getLeftChild() {
   return leftChild;
  }

  public void setLeftChild(Node leftChild) {
   this.leftChild = leftChild;
  }

  public Node getRightChild() {
   return rightChild;
  }

  public void setRightChild(Node rightChild) {
   this.rightChild = rightChild;
  }
 }

 class BinaryTree {
  Node root;

  public BinaryTree() {
   root = null;
  }

  public Node createTree1() {
   if (root == null) {
    root = new Node(12);
   }
   root.setLeftChild(new Node(23));
   root.setRightChild(new Node(18));
   root.getLeftChild().setLeftChild(new Node(11));
   root.getLeftChild().setRightChild(new Node(43));
   root.getRightChild().setRightChild(new Node(27));
   root.getRightChild().setLeftChild(new Node(12));
   root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
   root.getLeftChild().getLeftChild().setRightChild(new Node(78));
   root.getRightChild().getLeftChild().setRightChild(new Node(98));
   root.getRightChild().getLeftChild().setLeftChild(new Node(32));
   root.getLeftChild().getLeftChild().getRightChild()
     .setLeftChild(new Node(87));
   root.getRightChild().getLeftChild().getRightChild()
     .setLeftChild(new Node(29));
   return root;
  }

  public Node createTree2() {
   if (root == null) {
    root = new Node(12);
   }
   root.setLeftChild(new Node(18));
   root.setRightChild(new Node(23));
   root.getLeftChild().setLeftChild(new Node(43));
   root.getLeftChild().getLeftChild().setLeftChild(new Node(143));
   root.getLeftChild().setRightChild(new Node(11));
   root.getLeftChild().getRightChild().setRightChild(new Node(12));
   root.getLeftChild().getRightChild().getRightChild()
     .setLeftChild(new Node(121));
   return root;
  }
 }

}
================Sample output=====================
Numbers of full nodes and half nodes in binary tree-1 (Iterative): 5 and 2
Numbers of full nodes and half nodes in binary tree-1 (Recursive): 5 and 2
Numbers of full nodes and half nodes in binary tree-2 (Iterative): 2 and 3
Numbers of full nodes and half nodes in binary tree-2 (Recursive): 2 and 3
==============================================
Similar problem:- 
1. Find number of leaf nodes in binary tree Increment count only when both left and right child nodes are null