Path length having maximum number of bends | Java program to find path length having maximum number of bends ; structure node ; Utility function to create a new node ; Recursive function to calculate the path length having maximum number of bends . The following are parameters for this function . node - . pointer to the current node dir - . determines whether the current node is left or right child of it 's parent node bends -. number of bends so far in the current path. maxBends -. maximum number of bends in a path from root to leaf soFar -. length of the current path so far traversed len -. length of the path having maximum number of bends  ; Base Case ; Leaf node ; Recurring for both left and right child ; Helper function to call findMaxBendsUtil ( ) ; Call for left subtree of the root ; Call for right subtree of the root ; Include the root node as well in the path length ; Driver code ; Constructed binary tree is 10 / \ 8 2 / \ / 3 5 2 \ 1 / 9
import java . util . * ; class GFG { static class Node { int key ; Node left ; Node right ; } ; static Node newNode ( int key ) { Node node = new Node ( ) ; node . left = null ; node . right = null ; node . key = key ; return node ; } static int maxBends ; static int len ; static void findMaxBendsUtil ( Node node , char dir , int bends , int soFar ) { if ( node == null ) return ; if ( node . left == null && node . right == null ) { if ( bends > maxBends ) { maxBends = bends ; len = soFar ; } } else { if ( dir == ' l ' ) { findMaxBendsUtil ( node . left , dir , bends , soFar + 1 ) ; findMaxBendsUtil ( node . right , ' r ' , bends + 1 , soFar + 1 ) ; } else { findMaxBendsUtil ( node . right , dir , bends , soFar + 1 ) ; findMaxBendsUtil ( node . left , ' l ' , bends + 1 , soFar + 1 ) ; } } } static int findMaxBends ( Node node ) { if ( node == null ) return 0 ; len = 0 ; maxBends = - 1 ; int bends = 0 ; if ( node . left != null ) findMaxBendsUtil ( node . left , ' l ' , bends , 1 ) ; if ( node . right != null ) findMaxBendsUtil ( node . right , ' r ' , bends , 1 ) ; len ++ ; return len ; } public static void main ( String [ ] args ) { Node root = newNode ( 10 ) ; root . left = newNode ( 8 ) ; root . right = newNode ( 2 ) ; root . left . left = newNode ( 3 ) ; root . left . right = newNode ( 5 ) ; root . right . left = newNode ( 2 ) ; root . right . left . right = newNode ( 1 ) ; root . right . left . right . left = newNode ( 9 ) ; System . out . print ( findMaxBends ( root ) - 1 ) ; } }