# 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.

This article is attributed to GeeksforGeeks.org

Tree LCA Tree

code

load comments