# Print common nodes on path from root (or common ancestors)

Given a binary tree and two nodes, the task is to Print all the nodes that are common for 2 given nodes in a binary tree.

Examples:

```Given binary tree is :
1
/
2       3
/        /
4     5   6    7
/        /
8        9   10

Given nodes 9 and 7, so the common nodes are:-
1, 3
```

Asked in : Amazon

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

1. Find the LCA of given two nodes.
2. Print all ancestors of the LCA as done in this post, also print the LCA.

## C/C++

 `// C++ Program to find common nodes for given two nodes ` `#include ` `using` `namespace` `std; ` ` `  `// A Binary Tree Node ` `struct` `Node { ` `    ``struct` `Node* left, *right; ` `    ``int` `key; ` `}; ` ` `  `// Utility function to create a new tree Node ` `Node* newNode(``int` `key) ` `{ ` `    ``Node* temp = ``new` `Node; ` `    ``temp->key = key; ` `    ``temp->left = temp->right = NULL; ` `    ``return` `temp; ` `} ` ` `  `// Utility function to find the LCA of two given values ` `// n1 and n2. ` `struct` `Node* findLCA(``struct` `Node* root, ``int` `n1, ``int` `n2) ` `{ ` `    ``// Base case ` `    ``if` `(root == NULL) ` `        ``return` `NULL; ` ` `  `    ``// 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 ` `    ``if` `(root->key == n1 || root->key == n2) ` `        ``return` `root; ` ` `  `    ``// Look for keys in left and right subtrees ` `    ``Node* left_lca = findLCA(root->left, n1, n2); ` `    ``Node* right_lca = findLCA(root->right, n1, n2); ` ` `  `    ``// 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 ` `    ``if` `(left_lca && right_lca) ` `        ``return` `root; ` ` `  `    ``// Otherwise check if left subtree or right ` `    ``// subtree is LCA ` `    ``return` `(left_lca != NULL) ? left_lca : right_lca; ` `} ` ` `  `// Utility Function to print all ancestors of LCA ` `bool` `printAncestors(``struct` `Node* root, ``int` `target) ` `{ ` `    ``/* base cases */` `    ``if` `(root == NULL) ` `        ``return` `false``; ` ` `  `    ``if` `(root->key == target) { ` `        ``cout << root->key << ``" "``; ` `        ``return` `true``; ` `    ``} ` ` `  `    ``/* If target is present in either left or right ` `      ``subtree of this node, then print this node */` `    ``if` `(printAncestors(root->left, target) || ` `        ``printAncestors(root->right, target)) { ` `        ``cout << root->key << ``" "``; ` `        ``return` `true``; ` `    ``} ` ` `  `    ``/* Else return false */` `    ``return` `false``; ` `} ` ` `  `// Function to find nodes common to given two nodes ` `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); ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``// Let us create binary tree given in the above ` `    ``// example ` `    ``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; ` `} `

## Java

 `// Java Program to find common nodes for given two nodes ` `import` `java.util.LinkedList; ` `  `  `// Class to represent Tree node  ` `class` `Node  ` `{ ` `    ``int` `data; ` `    ``Node left, right; ` `  `  `    ``public` `Node(``int` `item)  ` `    ``{ ` `        ``data = item; ` `        ``left = ``null``; ` `        ``right = ``null``; ` `    ``} ` `} ` `  `  `// Class to count full nodes of Tree  ` `class` `BinaryTree  ` `{ ` `    ``static` `Node root; ` `// Utility function to find the LCA of two given values ` `// n1 and n2. ` `static` `Node findLCA(Node root, ``int` `n1, ``int` `n2) ` `{ ` `    ``// Base case ` `    ``if` `(root == ``null``) ` `        ``return` `null``; ` `  `  `    ``// 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 ` `    ``if` `(root.data == n1 || root.data == n2) ` `        ``return` `root; ` `  `  `    ``// Look for keys in left and right subtrees ` `    ``Node left_lca = findLCA(root.left, n1, n2); ` `    ``Node right_lca = findLCA(root.right, n1, n2); ` `  `  `    ``// 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 ` `    ``if` `(left_lca!=``null` `&& right_lca!=``null``) ` `        ``return` `root; ` `  `  `    ``// Otherwise check if left subtree or right ` `    ``// subtree is LCA ` `    ``return` `(left_lca != ``null``) ? left_lca : right_lca; ` `} ` `  `  `// Utility Function to print all ancestors of LCA ` `static` `boolean` `printAncestors(Node root, ``int` `target) ` `{ ` `    ``/* base cases */` `    ``if` `(root == ``null``) ` `        ``return` `false``; ` `  `  `    ``if` `(root.data == target) { ` `        ``System.out.print(root.data+ ``" "``); ` `        ``return` `true``; ` `    ``} ` `  `  `    ``/* If target is present in either left or right ` `    ``subtree of this node, then print this node */` `    ``if` `(printAncestors(root.left, target) || ` `        ``printAncestors(root.right, target)) { ` `        ``System.out.print(root.data+ ``" "``); ` `        ``return` `true``; ` `    ``} ` `  `  `    ``/* Else return false */` `    ``return` `false``; ` `} ` `  `  `// Function to find nodes common to given two nodes ` `static` `boolean` `findCommonNodes(Node root, ``int` `first, ` `                                    ``int` `second) ` `{ ` `    ``Node LCA = findLCA(root, first, second); ` `    ``if` `(LCA == ``null``) ` `        ``return` `false``; ` `  `  `    ``printAncestors(root, LCA.data); ` `    ``return` `true``; ` `} ` `  `  `// Driver program to test above functions ` `    ``public` `static` `void` `main(String args[])  ` `    ``{ ` `    ``/*Let us create Binary Tree shown in  ` `        ``above example */` `  `  `        ``BinaryTree tree = ``new` `BinaryTree(); ` `        ``tree.root = ``new` `Node(``1``); ` `        ``tree.root.left = ``new` `Node(``2``); ` `        ``tree.root.right = ``new` `Node(``3``); ` `        ``tree.root.left.left = ``new` `Node(``4``); ` `        ``tree.root.left.right = ``new` `Node(``5``); ` `        ``tree.root.right.left = ``new` `Node(``6``); ` `        ``tree.root.right.right = ``new` `Node(``7``); ` `        ``tree.root.left.left.left = ``new` `Node(``8``); ` `        ``tree.root.right.left.left = ``new` `Node(``9``); ` `        ``tree.root.right.left.right = ``new` `Node(``10``); ` `  `  `   ``if` `(findCommonNodes(root, ``9``, ``7``) == ``false``) ` `    ``System.out.println(``"No Common nodes"``); ` `  `  `    ``} ` `} ` ` `  `// This code is contributed by Mr Somesh Awasthi `

## Python3

 `# Python3 Program to find common ` `# nodes for given two nodes  ` ` `  `# Utility class to create a new tree Node  ` `class` `newNode: ` `    ``def` `__init__(``self``, key): ` `        ``self``.key ``=` `key  ` `        ``self``.left ``=` `self``.right ``=` `None` `     `  `# Utility function to find the LCA of ` `# two given values n1 and n2.  ` `def` `findLCA(root, n1, n2): ` `     `  `    ``# Base case  ` `    ``if` `(root ``=``=` `None``): ` `        ``return` `None` ` `  `    ``# 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  ` `    ``if` `(root.key ``=``=` `n1 ``or` `root.key ``=``=` `n2):  ` `        ``return` `root  ` ` `  `    ``# Look for keys in left and right subtrees  ` `    ``left_lca ``=` `findLCA(root.left, n1, n2)  ` `    ``right_lca ``=` `findLCA(root.right, n1, n2)  ` ` `  `    ``# If both of the above calls return Non-None,  ` `    ``# then one key is present in once subtree and  ` `    ``# other is present in other, So this node is the LCA  ` `    ``if` `(left_lca ``and` `right_lca):  ` `        ``return` `root  ` ` `  `    ``# Otherwise check if left subtree or  ` `    ``# right subtree is LCA ` `    ``if` `(left_lca !``=` `None``): ` `        ``return` `left_lca ` `    ``else``: ` `        ``return` `right_lca  ` ` `  `# Utility Function to prall ancestors of LCA  ` `def` `printAncestors(root, target): ` `     `  `    ``# base cases  ` `    ``if` `(root ``=``=` `None``): ` `        ``return` `False` ` `  `    ``if` `(root.key ``=``=` `target):  ` `        ``print``(root.key, end ``=` `" "``)  ` `        ``return` `True` ` `  `    ``# If target is present in either left or right  ` `    ``# subtree of this node, then prthis node  ` `    ``if` `(printAncestors(root.left, target) ``or`  `        ``printAncestors(root.right, target)): ` `            ``print``(root.key, end ``=` `" "``)  ` `            ``return` `True` ` `  `    ``# Else return False  ` `    ``return` `False` ` `  `# Function to find nodes common to given two nodes  ` `def` `findCommonNodes(root, first, second): ` `    ``LCA ``=` `findLCA(root, first, second)  ` `    ``if` `(LCA ``=``=` `None``): ` `        ``return` `False` ` `  `    ``printAncestors(root, LCA.key) ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `'__main__'``: ` ` `  `    ``# Let us create binary tree given  ` `    ``# in the above example  ` `    ``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``):  ` `        ``print``(``"No Common nodes"``) ` ` `  `# This code is contributed by PranchalK `

## C#

 `using` `System; ` ` `  `// C# Program to find common nodes for given two nodes  ` ` `  `// Class to represent Tree node  ` `public` `class` `Node ` `{ ` `    ``public` `int` `data; ` `    ``public` `Node left, right; ` ` `  `    ``public` `Node(``int` `item) ` `    ``{ ` `        ``data = item; ` `        ``left = ``null``; ` `        ``right = ``null``; ` `    ``} ` `} ` ` `  `// Class to count full nodes of Tree  ` `public` `class` `BinaryTree ` `{ ` `    ``public` `static` `Node root; ` `// Utility function to find the LCA of two given values  ` `// n1 and n2.  ` `public` `static` `Node findLCA(Node root, ``int` `n1, ``int` `n2) ` `{ ` `    ``// Base case  ` `    ``if` `(root == ``null``) ` `    ``{ ` `        ``return` `null``; ` `    ``} ` ` `  `    ``// 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  ` `    ``if` `(root.data == n1 || root.data == n2) ` `    ``{ ` `        ``return` `root; ` `    ``} ` ` `  `    ``// Look for keys in left and right subtrees  ` `    ``Node left_lca = findLCA(root.left, n1, n2); ` `    ``Node right_lca = findLCA(root.right, n1, n2); ` ` `  `    ``// 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  ` `    ``if` `(left_lca != ``null` `&& right_lca != ``null``) ` `    ``{ ` `        ``return` `root; ` `    ``} ` ` `  `    ``// Otherwise check if left subtree or right  ` `    ``// subtree is LCA  ` `    ``return` `(left_lca != ``null``) ? left_lca : right_lca; ` `} ` ` `  `// Utility Function to print all ancestors of LCA  ` `public` `static` `bool` `printAncestors(Node root, ``int` `target) ` `{ ` `    ``/* base cases */` `    ``if` `(root == ``null``) ` `    ``{ ` `        ``return` `false``; ` `    ``} ` ` `  `    ``if` `(root.data == target) ` `    ``{ ` `        ``Console.Write(root.data + ``" "``); ` `        ``return` `true``; ` `    ``} ` ` `  `    ``/* If target is present in either left or right  ` `    ``subtree of this node, then print this node */` `    ``if` `(printAncestors(root.left, target)  ` `    ``|| printAncestors(root.right, target)) ` `    ``{ ` `        ``Console.Write(root.data + ``" "``); ` `        ``return` `true``; ` `    ``} ` ` `  `    ``/* Else return false */` `    ``return` `false``; ` `} ` ` `  `// Function to find nodes common to given two nodes  ` `public` `static` `bool` `findCommonNodes(Node root,  ` `                            ``int` `first, ``int` `second) ` `{ ` `    ``Node LCA = findLCA(root, first, second); ` `    ``if` `(LCA == ``null``) ` `    ``{ ` `        ``return` `false``; ` `    ``} ` ` `  `    ``printAncestors(root, LCA.data); ` `    ``return` `true``; ` `} ` ` `  `// Driver program to test above functions  ` `    ``public` `static` `void` `Main(``string``[] args) ` `    ``{ ` `    ``/*Let us create Binary Tree shown in  ` `        ``above example */` ` `  `        ``BinaryTree tree = ``new` `BinaryTree(); ` `        ``BinaryTree.root = ``new` `Node(1); ` `        ``BinaryTree.root.left = ``new` `Node(2); ` `        ``BinaryTree.root.right = ``new` `Node(3); ` `        ``BinaryTree.root.left.left = ``new` `Node(4); ` `        ``BinaryTree.root.left.right = ``new` `Node(5); ` `        ``BinaryTree.root.right.left = ``new` `Node(6); ` `        ``BinaryTree.root.right.right = ``new` `Node(7); ` `        ``BinaryTree.root.left.left.left = ``new` `Node(8); ` `        ``BinaryTree.root.right.left.left = ``new` `Node(9); ` `        ``BinaryTree.root.right.left.right = ``new` `Node(10); ` ` `  `if` `(findCommonNodes(root, 9, 7) == ``false``) ` `{ ` `    ``Console.WriteLine(``"No Common nodes"``); ` `} ` ` `  `    ``} ` `} ` ` `  `// This code is contributed by Shrikant13 `

Output:

```3 1
```

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Tree LCA Tree