5 Oct 2013

Max Vertical Columns of a Binary Tree

Problem Statement: 
     Calculate the maximum vertical columns of a Binary Tree




Solution:
   
 For a given Binary Tree the root is at column '0' , moving left means the child node lies '-1' with respect to parent column, similarly moving right is interpreted as '+1' with respect to the parent. Thus in the given problem we have to find the farthest left column and farthest right column with respect to the root. We will designate farthest left column with "minVal" because it will be the least value for any column in the tree, similarly for the farthest right column with "maxVal".
Therefore , number of vertical Columns = maxVal - minVal + 1

Pls refer Source Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
        static int maxVal=0 ; // farthest right column
 static int minVal=0;  //farthest left column  
 /**
  * Calculates farthest left colummn and fatherst right column
  * @param root
  * @param col
  */
 public void totalCol(Node root , int col) {
  
  if(root==null)
   return ;
  
  totalCol(root.left , col - 1 );
  totalCol(root.right , col + 1 );
  
  maxVal=min(col, maxVal);
  minVal = max (col , minVal) ;
 }

 private int max(int val1, int val2) {
  return val1 > val2 ? val1 : val2;
 }

 private int min(int val1, int val2) {
  return val1 < val2 ? val1 : val2;
 }

No comments:

Post a Comment