Tuesday 22 September 2015

Print a binary tree from bottom to top

Problem

Print a binary tree from bottom to top in level order. For example,
            Given binary tree is:
                    1
                 /      \
                2        3
              /  \        \
             4   5        6
                        /    \
                       7      8


      The output will be 7,8,4,5,6,2,3,1

        

Solution

We will do normal level order traversal using a queue, while doing that we will keep on adding the nodes to a stack. So that it reverses during print. As we will print it from left to right, while putting it into the queue for level order traversal, we will put right node first and then the left node, so that after reversing from the stack it will become left, right.

Code

import java.util.List;
import java.util.Stack;

public class PrintBinartyTreeBottomToTop
{
 public static void main(String[] args)
 {
  Node a = new Node(1);
  Node b = new Node(2);
  Node c = new Node(3);
  Node d = new Node(4);
  Node e = new Node(5);
  Node f = new Node(6);
  Node g = new Node(7);
  Node h = new Node(8);
  a.left = b;
  a.right = c;
  b.left = d;
  c.left = e;
  c.right = f;
  f.left = g;
  f.right = h;

  printLevelFromBottomToTop(a);
 }

 
 private static void printLevelFromBottomToTop(Node root)
 {
  LinkedList < node > queue=new LinkedList < node >();
  Stack < node > stack=new Stack < node >();
  queue.add(root);
  while(!queue.isEmpty())
  {
   Node node=queue.poll();
   stack.push(node);
   if(node.right!=null)
   {
    queue.add(node.right);
   }
   if(node.left!=null)
   {
    queue.add(node.left);
   }
  }
  while(!stack.isEmpty())
  {
   System.out.print(stack.pop().value+", ");
  }
 }


 static class Node
 {
  Node left;
  Node right;
  int value;

  public Node(int value)
  {
   this.value = value;
  }
 }
}

No comments:

Post a Comment