Find maximum matching in a given Binary Tree | Javascript Program to implement the above approach ; Adjacency list to store edges ; Add an edge between U and V in tree ; Edge from u to v ; Edge from V to U ; Function that finds the maximum matching of the DFS ; Go further as we are not allowed to go towards its parent ; If U and its parent P is not taken then we must take & mark them as taken ; Increment size of edge set ; Function to find the maximum matching in a graph ; Taking 1 as a root of the tree ; Print maximum Matching ; Driver Code ; Joining edge between two nodes in tree ; Function call
let N = 10000 ; let adj = new Array ( N ) ; let used = new Array ( N ) ; used . fill ( 0 ) ; let max_matching = 0 ; function AddEdge ( u , v ) { adj [ u ] . push ( v ) ; adj [ v ] . push ( u ) ; } function Matching_dfs ( u , p ) { for ( let i = 0 ; i < adj [ u ] . length ; i ++ ) { if ( adj [ u ] [ i ] != p ) { Matching_dfs ( adj [ u ] [ i ] , u ) ; } } if ( used [ u ] == 0 && used [ p ] == 0 && p != 0 ) { max_matching ++ ; used [ u ] = used [ p ] = 1 ; } } function maxMatching ( ) { Matching_dfs ( 1 , 0 ) ; document . write ( max_matching + " " ) ; } for ( let i = 0 ; i < adj . length ; i ++ ) adj [ i ] = [ ] ; AddEdge ( 1 , 2 ) ; AddEdge ( 1 , 3 ) ; AddEdge ( 3 , 4 ) ; AddEdge ( 3 , 5 ) ; maxMatching ( ) ;