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
class Solution {
boolean foundP = false;
boolean foundQ = false;
public Node lowestCommonAncestor(Node root, int p, int q) {
if (root == null)
return root;
if (root.val == p || root.val == q) {
foundP = root.val == p ? true : foundP;
foundQ = root.val == q ? true : foundQ;
}
Node left = lowestCommonAncestor(root.left, p, q);
Node right = lowestCommonAncestor(root.right, p, q);
if (root.val == p || root.val == q) {
return root;
} else {
if (left != null && right != null)
return root;
else if (left != null)
return left;
else if (right != null)
return right;
return null;
}
}
public boolean findPath(Node node, Node target, ArrayList<Integer> path) {
if (node == null)
return false;
if (node.equals(target)) {
path.add(node.val);
return true;
}
path.add(node.val);
if (findPath(node.left, target, path) || findPath(node.right, target, path))
return true;
path.remove(path.size() - 1);
return false;
}
public void lca(Node node, int p, int q) {
Node lca = lowestCommonAncestor(node, p, q);
if (foundP && foundQ) {
ArrayList<Integer> path = new ArrayList<>();
findPath(node, lca, path);
for (int x : path) {
System.out.print(x + " ");
}
}
}
}
Last updated