I understand two nodes are cousins if they are on the same level and have different parents so here goes my logic/algorithm. I am creating two boolean methods findLevel and siblings (using preorder traversal for both methods). I am then checking in the main method printCousins, if findLevel is true and not siblings, add into the arrayList. But my solution is wrong if anyone can tell me what I am doing wrong.

static boolean findLevel(Node root, Node find, int level) {
    boolean status = false;

    if (root == null || find == null)
        return false;

    if (root == find)
        status = true;

    findLevel(root.left, find, level   1);
    findLevel(root.right, find, level   1);

    return status;
}

static boolean sibling(Node root, Node find) {
    boolean status = false;

    if (root == null || find == null)
        return false;

    if (root.left == find && root.right == find)
        status = true;

    sibling(root.left, find);
    sibling(root.right, find);

    return status;

}

CodePudding user response：

In your approach, you seem to assume that cousins can have only 1 different parent. The more we go deeper, the more the different parents for a particular find node or you can say the more the cousins. Also, if(root.left == find && root.right == find){ doesn't make sense since there can't be 2 same nodes in the tree, especially with find.

In your printCousins, you will need to find the level of the find node and then collect all it's cousins by passing it to siblings method.

public static ArrayList<Integer> printCousins(Node root, Node find){
    //code here
    ArrayList<Integer> arr = new ArrayList<>();
    int level = findLevel(root, find, 0);
    if(level == -1){
        arr.add(-1);
        return arr;
    }

    siblings(root, find, arr, 0, level);
    if(arr.isEmpty()){
        arr.add(-1);
    }
    return arr;
}

Since you use depth first search technique, you can find the level of the find node first like below:

 static int findLevel(Node root, Node find, int level){
    if(root == null) return -1;
    if(root == find) return level;
    
    int level = findLevel(root.left, find, level   1);
    if(level == -1) level = findLevel(root.right, find, level   1);// only go to the right side of the node if not found on the left part
    
    return -1;
}

In siblings, you will add all those nodes to arr that are located at level with a careful check of the parent not having find as one of their kids thereby ensuring different parents same level requirement.

static void siblings(Node root, Node find, ArrayList<Integer> arr, int curr_level, int level){
    if(root == null || curr_level > level || root == find) return;
    if(curr_level   1 == level){
        if(root.left == find || root.right == find) return; // making sure either of the kids isn't 'find'
    }

    if(curr_level == level){
        arr.add(root.val);
        return;
    }
    
    siblings(root.left, find, arr, curr_level   1, level);
    siblings(root.right, find, arr, curr_level   1, level);
}

CodePudding user response：

I can see in this task is simple BFS - Breadth-first search. All you need is to find a level where your target node and print all other nodes at the same level with different parents, which could be quite easy if you keep the parent of each node (I offer to do this with the additional class NodeWithParent).

// This is a class you have to provide a Tree
public static class Node {

    private final int value;
    private Node left;
    private Node right;

    public Node(int value) {
        this.value = value;
    }

}

// This is an internal class to keep the node's parent
private static class NodeWithParent {

    private final Node delegate;
    private final Integer parent;

    public NodeWithParent(Node delegate, Integer parent) {
        this.delegate = delegate;
        this.parent = parent;
    }

}

public static Set<Integer> printCousins(Node root, int find) {
    NodeWithParent tmp = new NodeWithParent(root, null);
    Deque<NodeWithParent> levelNodes = new LinkedList<>();
    levelNodes.add(tmp);

    // not null means target node was found at current level
    NodeWithParent findNode = root.value == find ? tmp : null;

    while (!levelNodes.isEmpty()) {
        if (findNode != null)
            return getNodesNotForParent(levelNodes, findNode);

        int total = levelNodes.size();

        for (int i = 0; i < total; i  ) {
            NodeWithParent node = levelNodes.remove();
            NodeWithParent findNode1 = addNotNullChild(node.delegate.left, node.delegate.value, find, levelNodes);
            NodeWithParent findNode2 = addNotNullChild(node.delegate.right, node.delegate.value, find, levelNodes);

            if (findNode == null)
                findNode = findNode1 == null ? findNode2 : findNode1;
        }
    }

    return Set.of();
}

private static NodeWithParent addNotNullChild(Node childNode, int parentValue, int find, Deque<NodeWithParent> levelNodes) {
    if (childNode == null)
        return null;
    
    NodeWithParent node = new NodeWithParent(childNode, parentValue);
    levelNodes.add(node);
    return childNode.value == find ? node : null;
}

private static Set<Integer> getNodesNotForParent(Collection<NodeWithParent> nodes, NodeWithParent findNode) {
    return nodes.stream()
                .filter(node -> !Objects.equals(node.parent, findNode.parent))
                .map(node -> node.delegate.value)
                .collect(Collectors.toSet());
}