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

So start saving your soap pieces in this until it

ReplyDeleteis 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