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!! :)