fork(6) download
copy 
  1. /**
  2.  * Longest Zig-Zag Path:
  3.  * Find the longest zig-zag path in binary Tree
  4.  * It can be LRLRLRLRL....  or  RLRLRL....
  5.  * @author Prateek Rathore
  6.  */
  7. class LongestZigZagPath {
  8.  
  9. 	/**
  10. 	 * Calculates Longest Zig-Zag Path in Binary Tree
  11. 	 * @return max value of longest path
  12. 	 */
  13. 	public int longestZigZag(Node root,int max){
  14.  
  15. 		if(root==null)
  16. 			return 0;
  17.  
  18. 		int lh=countUtil(root,true,0);
  19. 		int rh=countUtil(root,false,0);
  20.  
  21. 		max= Math.max(lh, rh);
  22. 		max=  Math.max(max,longestZigZag(root.left, max));
  23. 		max=  Math.max(max,longestZigZag(root.right,max));
  24. 		return max;
  25. 	}
  26.  
  27. 	/**
  28. 	 * Count Utility to count the steps covered, for a given node
  29. 	 * @param node
  30. 	 * @param moveLeft : if true , move left , else move right
  31. 	 * @param count: current count
  32. 	 * @return the count of ZIG-ZAG path traversed
  33. 	 */
  34. 	public int countUtil(Node node, boolean moveLeft , int count){
  35. 		if(node==null)
  36. 			return count;
  37.  
  38. 		if(moveLeft)
  39. 			count=countUtil(node.left,!moveLeft,count+1);
  40. 		else
  41. 			count=countUtil(node.right,!moveLeft,count+1);
  42.  
  43. 		return count;
  44. 	}
  45.  
  46. 	public static void main(String[] args) {
  47. 		/*Node root = new Node(1) ;
  48. 		root.left= new Node(2) ;
  49. 		root.right= new Node(3) ;
  50. 		root.left.left= new Node(4) ;
  51. 		root.left.right= new Node(5) ;  	
  52. 		root.right.left= new Node(6) ;
  53. 		root.right.right= new Node(7) ;  
  54. 		root.left.right.left= new Node(8) ;  
  55. 		root.left.right.right= new Node(9) ;
  56. 		root.left.right.left.right= new Node(10) ;  */
  57.  
  58. 		Node root = new Node(1) ;
  59. 		root.left= new Node(2) ;
  60. 		root.right= new Node(3) ;
  61. 		root.left.left= new Node(4) ;
  62. 		root.left.right= new Node(5) ;  	
  63. 		root.right.left= new Node(6) ;
  64. 		root.right.right= new Node(7) ; 
  65.  
  66.  
  67. 		root.left.left.right= new Node(8) ;  
  68. 		root.left.left.right.left= new Node(9) ;
  69.  
  70. 		LongestZigZagPath obj= new LongestZigZagPath();
  71. 		System.out.println("Longest ZIG-ZAG Path : "+obj.longestZigZag(root,0));
  72. 	}
  73. }
  74.  
  75. class Node {
  76. 	public Node left;
  77. 	public int data;
  78. 	public Node right;
  79.  
  80. 	public Node(int val)	{
  81. 		this.data=val;
  82. 	}
  83.  
  84. 	@Override
  85. 	public String toString(){
  86. 		return this.data + "";
  87. 	}
  88. }
  89.  
  90.  
Success #stdin #stdout 0.06s 381248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Longest ZIG-ZAG Path : 4
https://ideone.com/lXX5A1
Longest Zig Zag Path in Binary Tree
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!