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