21 Dec 2013

Longest Zig-Zag Path

Problem Statement:
        Calculate the longest Zig-Zag Path in a Binary Tree.

Fig: Find longest Zig-Zag Path

Longest Zig-Zag path here is : 2 , 4, 8, 9 ,
hence the length is 4
Solution:

Full Source  Code: LINK

The longest zig-zag path may not include the root of the tree, the path can either start from Right child or Left child.
Possible combinations are :
1. LRLRLR ......
2. RLRLRL.......


Main Logic implementation is given below:


 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
27
28
29
30
31
32
33
34
35
36
/**
  * Calculates Longest Zig-Zag Path in Binary Tree
  * @return max value of longest path
  */
 public int longestZigZag(Node root,int max){
  
  if(root==null)
   return 0;
  
  int lh=countUtil(root,true,0);
  int rh=countUtil(root,false,0);
 
  max= Math.max(lh, rh);
  max=  Math.max(max,longestZigZag(root.left, max));
  max=  Math.max(max,longestZigZag(root.right,max));
  return max;
 }

 /**
  * Count Utility to count the steps covered, for a given node
  * @param node
  * @param moveLeft : if true , move left , else move right
  * @param count: current count
  * @return the count of ZIG-ZAG path traversed
  */
 public int countUtil(Node node, boolean moveLeft , int count){
  if(node==null)
   return count;
  
  if(moveLeft)
   count=countUtil(node.left,!moveLeft,count+1);
  else
   count=countUtil(node.right,!moveLeft,count+1);
  
  return count;
 }

Please post your comments and suggestions.
Happy Coding!! :)

1 comment:

  1. So start saving your soap pieces in this until it
    is as full as it can be in the form of bottles and jars
    without sending them to the plant. The industry is making strides in the development of more earth-friendly
    techniques, but the retail cost does not always tell the whole story.
    However, zters portable toilets is also good for preventing environmental pollution to some
    extent the labor shortage in Southern China.

    My site :: best portable toilet

    ReplyDelete