Sum of specially balanced nodes from a given Binary Tree | Java 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
import java . util . * ; class GFG { static int sum ; static class Node { int data ; Node left , right ; } ; static Node newnode ( int data ) { Node temp = new Node ( ) ; temp . data = data ; temp . left = null ; temp . right = null ; return temp ; } static Node insert ( String s , int i , int N , Node root , Node temp ) { if ( i == N ) return temp ; if ( s . charAt ( 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 ; } static int SBTUtil ( Node root ) { if ( root == null ) return 0 ; if ( root . left == null && root . right == null ) return root . data ; int left = SBTUtil ( root . left ) ; int right = SBTUtil ( root . right ) ; if ( root . left != null && root . right != null ) { if ( ( left % 2 == 0 && right % 2 != 0 ) || ( left % 2 != 0 && right % 2 == 0 ) ) { sum += root . data ; } } return left + right + root . data ; } static 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 . length ( ) , root , temp ) ; } return root ; } static void speciallyBalancedNodes ( int R , int N , String str [ ] , int values [ ] ) { Node root = build_tree ( R , N , str , values ) ; sum = 0 ; SBTUtil ( root ) ; System . out . print ( sum + " ▁ " ) ; } public static void main ( String [ ] args ) { int N = 7 ; int R = 12 ; String str [ ] = { " L " , " R " , " RL " , " RR " , " RLL " , " RLR " } ; int values [ ] = { 17 , 16 , 4 , 9 , 2 , 3 } ; speciallyBalancedNodes ( R , N , str , values ) ; } }