text: Sum of specially balanced nodes from a given Binary Tree | C ++ program for the above approach ; Structure of Binary Tree ; Function to create a new node ; Return the created node ; Function to insert a node in the tree ; Left insertion ; Right insertion ; Return the root node ; Function to find sum of specially balanced nodes in the Tree ; Base Case ; Find the left subtree sum ; Find the right subtree sum ; Condition of specially balanced node ; Condition of specially balanced node ; Return the sum ; Function to build the binary tree ; Form root node of the tree ; Insert nodes into tree ; Create a new Node ; Insert the node ; Return the root of the Tree ; Function to find the sum of specially balanced nodes ; Build Tree ; Stores the sum of specially balanced node ; Function Call ; Print required sum ; Driver Code ; Given nodes ; Given root ; Given path info of nodes from root ; Given node values ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; } ; Node * newnode ( int data ) { Node * temp = new Node ; temp -> data = data ; temp -> left = NULL ; temp -> right = NULL ; return temp ; } Node * insert ( string s , int i , int N , Node * root , Node * temp ) { if ( i == N ) return temp ; if ( s [ i ] == ' L ' ) root -> left = insert ( s , i + 1 , N , root -> left , temp ) ; else root -> right = insert ( s , i + 1 , N , root -> right , temp ) ; return root ; } int SBTUtil ( Node * root , int & sum ) { if ( root == NULL ) return 0 ; if ( root -> left == NULL && root -> right == NULL ) return root -> data ; int left = SBTUtil ( root -> left , sum ) ; int right = SBTUtil ( root -> right , sum ) ; if ( root -> left && root -> right ) { if ( ( left % 2 == 0 && right % 2 != 0 ) || ( left % 2 != 0 && right % 2 == 0 ) ) { sum += root -> data ; } } return left + right + root -> data ; } Node * build_tree ( int R , int N , string str [ ] , int values [ ] ) { Node * root = newnode ( R ) ; int i ; for ( i = 0 ; i < N - 1 ; i ++ ) { string s = str [ i ] ; int x = values [ i ] ; Node * temp = newnode ( x ) ; root = insert ( s , 0 , s . size ( ) , root , temp ) ; } return root ; } void speciallyBalancedNodes ( int R , int N , string str [ ] , int values [ ] ) { Node * root = build_tree ( R , N , str , values ) ; int sum = 0 ; SBTUtil ( root , sum ) ; cout << sum << " ▁ " ; } int main ( ) { int N = 7 ; int R = 12 ; string str [ N - 1 ] = { " L " , " R " , " RL " , " RR " , " RLL " , " RLR " } ; int values [ N - 1 ] = { 17 , 16 , 4 , 9 , 2 , 3 } ; speciallyBalancedNodes ( R , N , str , values ) ; return 0 ; }