Print common nodes on path from root ( or common ancestors ) | C ++ Program to find common nodes for given two nodes ; A Binary Tree Node ; Utility function to create a new tree Node ; Utility function to find the LCA of two given values n1 and n2 . ; Base case ; If either n1 or n2 matches with root 's key,  report the presence by returning root (Note  that if a key is ancestor of other, then the  ancestor key becomes LCA ; Look for keys in left and right subtrees ; If both of the above calls return Non - NULL , then one key is present in once subtree and other is present in other , So this node is the LCA ; Otherwise check if left subtree or right subtree is LCA ; Utility Function to print all ancestors of LCA ; base cases ; If target is present in either left or right subtree of this node , then print this node ; Else return false ; Function to find nodes common to given two nodes ; Driver program to test above functions ; Let us create binary tree given in the above example
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { struct Node * left , * right ; int key ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> key = key ; temp -> left = temp -> right = NULL ; return temp ; } struct Node * findLCA ( struct Node * root , int n1 , int n2 ) { if ( root == NULL ) return NULL ; if ( root -> key == n1 root -> key == n2 ) return root ; Node * left_lca = findLCA ( root -> left , n1 , n2 ) ; Node * right_lca = findLCA ( root -> right , n1 , n2 ) ; if ( left_lca && right_lca ) return root ; return ( left_lca != NULL ) ? left_lca : right_lca ; } bool printAncestors ( struct Node * root , int target ) { if ( root == NULL ) return false ; if ( root -> key == target ) { cout << root -> key << " ▁ " ; return true ; } if ( printAncestors ( root -> left , target ) || printAncestors ( root -> right , target ) ) { cout << root -> key << " ▁ " ; return true ; } return false ; } bool findCommonNodes ( struct Node * root , int first , int second ) { struct Node * LCA = findLCA ( root , first , second ) ; if ( LCA == NULL ) return false ; printAncestors ( root , LCA -> key ) ; } int main ( ) { Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 5 ) ; root -> right -> left = newNode ( 6 ) ; root -> right -> right = newNode ( 7 ) ; root -> left -> left -> left = newNode ( 8 ) ; root -> right -> left -> left = newNode ( 9 ) ; root -> right -> left -> right = newNode ( 10 ) ; if ( findCommonNodes ( root , 9 , 7 ) == false ) cout << " No ▁ Common ▁ nodes " ; return 0 ; }