Question: Write methods to Basic Binary Tree Operations like No of Nodes, No. of leaf nodes, in order, pre order, post order and level order tree traversals
Solution:
/**
*
Count number of nodes in a Binary Tree
*
* @param T
* @return
*/
public int countNodes(TreeNode T)
{
if(T == null)
return 0;
else
return countNodes(T.left)+countNodes(T.right)+1;
}
/**
*
Count number of leaf nodes
*
* @param T
* @return
*/
public int CountLeafNodes(TreeNode T)
{
if(T == null) {
return 0;
}
else if(T.left == null && T.right == null) {
return 1;
}
else {
return CountLeafNodes(T.left)+CountLeafNodes(T.right);
}
}
public int Max(int l, int r)
{
return l>r?l:r;
}
/**
*
Depth of Binary Tree
*
* @param T
* @return
*/
public int Depth(TreeNode T)
{
if(T == null) {
return -1;
}
else {
return Max(Depth(T.left), Depth(T.right))+1;
}
}
/**
*
Height of Binary Tree
*
* @param T
* @return
*/
public int Height(TreeNode T)
{
if(T==null) {
return -1;
}
else {
return Max(Height(T.left), Height(T.right))+1;
}
}
/**
*
InOrder traversal
*
* @param T
*/
public void InOrder(TreeNode T)
{
if(T!=null) {
InOrder(T.left);
System.out.print(T.element + " ");
InOrder(T.right);
}
}
/**
*
PreOrder Traversal
*
* @param T
*/
public void PreOrder(TreeNode T)
{
if(T!=null) {
System.out.print(T.element + " ");
PreOrder(T.left);
PreOrder(T.right);
}
}
/**
*
PostOrder Traversal
*
* @param T
*/
public void PostOrder(TreeNode T)
{
if(T!=null) {
PostOrder(T.left);
PostOrder(T.right);
System.out.print(T.element + " ");
}
}
/**
*
Level Order Traversal
*
* @param T
*/
public void levelOrder(TreeNode T)
{
if(T==null){
System.out.println("Empty Tree");
return;
}
else {
Queue<TreeNode> queue = new ArrayBlockingQueue<TreeNode>(50);
queue.add(T);
while(!queue.isEmpty()){
TreeNode node = queue.peek();
System.out.print(node.element + " ");
if(node.left!=null) {
queue.add(node.left);
}
if(node.right!=null) {
queue.add(node.right);
}
queue.remove();
}
}
}
/**
* Zig
Zag order
*
* @param T
*/
public void ZigZagOrder(TreeNode T)
{
if(T==null) {
System.out.println(" Empty
Tree");
return;
}
else {
Stack<TreeNode> curLevel = new Stack<TreeNode>();
Stack<TreeNode> nextLevel = new Stack<TreeNode>();
curLevel.push(T);
boolean leftToRight=true;
while(!curLevel.isEmpty()) {
TreeNode p = curLevel.pop();
if(p!=null) {
System.out.print(p.element + " ");
if(leftToRight) {
nextLevel.push(p.left);
nextLevel.push(p.right);
}
else {
nextLevel.push(p.right);
nextLevel.push(p.left);
}
}
if(curLevel.isEmpty()) {
// change the order
leftToRight=!leftToRight;
// Swap curLevel and nextLevel
Stack<TreeNode>
temp = curLevel;
curLevel = nextLevel;
nextLevel = temp;
}
}
}
}
/**
*
*
*/
public void PathsSum(TreeNode T, int sum){
if(T == null) {
System.out.println("Empty tree");
}
sum += T.element;
if(T.left == null && T.right == null) {
System.out.println(sum);
}
if(T.left != null) {
PathsSum(T.left, sum);
}
if(T.right != null) {
PathsSum(T.right, sum);
}
}
public TreeNode verticalSum(TreeNode T, Integer vLevel){
if(T == null)
return null;
TreeNode temp = verticalSum(T.left, --vLevel);
if(temp == null)
vLevel++;
if(treeMap.get(vLevel) != null) {
// add current node value to existing value in the map
treeMap.put(vLevel, T.element + treeMap.get(vLevel));
}
else{
// put current node value in the map
treeMap.put(vLevel, T.element);
}
return verticalSum(T.right, ++vLevel);
}
public void
printVerticalSum(TreeMap<Integer, Integer> map) {
for(Integer key : map.keySet()) {
System.out.print(map.get(key) + " ");
}
}
