Path length having maximum number of bends | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; struct Node * left ; struct Node * right ; } ; struct Node * newNode ( int key ) { struct Node * node = new Node ( ) ; node -> left = NULL ; node -> right = NULL ; node -> key = key ; return node ; } void findMaxBendsUtil ( struct Node * node , char dir , int bends , int * maxBends , int soFar , int * len ) { 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 , maxBends , soFar + 1 , len ) ; findMaxBendsUtil ( node -> right , ' r ' , bends + 1 , maxBends , soFar + 1 , len ) ; } else { findMaxBendsUtil ( node -> right , dir , bends , maxBends , soFar + 1 , len ) ; findMaxBendsUtil ( node -> left , ' l ' , bends + 1 , maxBends , soFar + 1 , len ) ; } } } int findMaxBends ( struct Node * node ) { if ( node == NULL ) return 0 ; int len = 0 , bends = 0 , maxBends = -1 ; if ( node -> left ) findMaxBendsUtil ( node -> left , ' l ' , bends , & maxBends , 1 , & len ) ; if ( node -> right ) findMaxBendsUtil ( node -> right , ' r ' , bends , & maxBends , 1 , & len ) ; len ++ ; return len ; } int main ( ) { struct 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 ) ; cout << findMaxBends ( root ) - 1 ; return 0 ; }