easy Cousins in Binary Tree

Problem Statement

Given the root of a binary tree with unique values and two different nodes x and y, return a boolean value based on whether the nodes corresponding to the values x and y are cousins.

Two nodes are cousins if they are at the same depth but have different parents.

Examples

Example 1:

• Input: root = [1, 2, 3, 4, null, 5, 6], x = 4, y = 5

    1
   / \
  2   3
 /   / \
4   5   6  

• Expected Output: true
• Justification: Nodes 4 and 5 both are at depth 2 with parent 2. They are cousins because their parents are different and they are at the same depth.

Example 2:

• Input: root = [1, 2, 3, 4, 5, null, null, null, null, 6, 7], x = 6, y = 7

    1
   / \
  2   3
 / \  
4   5   
   / \
  6   7

• Expected Output: false
• Justification: Both nodes 6 and 7 are at depth 3, but they have the same parent 5.

Example 3:

• Input: root = [1, 2, 3, null, 4, 5, null], x = 4, y = 5

    1
  /  \
 2    3
  \   /
   4 5

• Expected Output: true
• Justification: Node 4 is at depth 2 with parent 2. Node 5 is at depth 2 with parent 3. Both nodes are at the same depth but have different parents.

Constraints:

• The number of nodes in the tree is in the range [2, 100].
• 1 <= Node.val <= 100
• Each node has a unique value.
• x != y
• x and y are exist in the tree.

Solution

To solve this problem, we need to traverse the binary tree to find the depth and parent of each node. We can use a Breadth-First Search (BFS) approach to ensure we explore each level of the tree fully before moving on to the next. This will help us easily determine the depth of each node. During this traversal, we will keep track of the parent of each node. Once we have this information, we can check if the nodes x and y are at the same depth and have different parents.

This approach is effective because it ensures that we traverse each node only once, making it time-efficient. Additionally, using BFS allows us to process nodes level by level, which is helpful for maintaining the depth information. This method leverages the structure of the binary tree efficiently and ensures that we meet the problem's requirements without unnecessary complexity.

Step-by-Step Algorithm

1. Initialize Data Structures:

   • Create a map to store depth and parent information for each node.
   • Create a queue to perform BFS. Initially, add the root node to the queue with depth 0 and no parent.

2. Perform BFS Traversal:

   • While the queue is not empty, do the following:
     • Dequeue the front element from the queue.
     • If the current node has a left child:
       • Enqueue the left child with an incremented depth and the current node as its parent.
       • Store the left child's depth and parent in the map.
     • If the current node has a right child:
       • Enqueue the right child with an incremented depth and the current node as its parent.
       • Store the right child's depth and parent in the map.

3. Check Cousin Condition:

   • Retrieve the depth and parent information of nodes x and y from the map.
   • Return true if the depths of x and y are the same and their parents are different. Otherwise, return false.

Algorithm Walkthrough

Given input: [1, 2, 3, 4, null, 5, 6], x = 4, y = 5

Initialization:

• Map to store depth and parent information.
• Queue for BFS, starting with the root node:
  • Queue: [(1, 0, None)]

Step 1: Process the root node (1)

• Dequeue (1, 0, None):
  • Current node: 1
  • Depth: 0
  • Parent: None
• Enqueue its children (2 and 3):
  • Queue: [(2, 1, 1), (3, 1, 1)]
• Update the map:
  • Map: {1: (0, None)}

Step 2: Process node (2)

• Dequeue (2, 1, 1):
  • Current node: 2
  • Depth: 1
  • Parent: 1
• Enqueue its left child (4):
  • Queue: [(3, 1, 1), (4, 2, 2)]
• Update the map:
  • Map: {1: (0, None), 2: (1, 1)}

Step 3: Process node (3)

• Dequeue (3, 1, 1):
  • Current node: 3
  • Depth: 1
  • Parent: 1
• Enqueue its children (5 and 6):
  • Queue: [(4, 2, 2), (5, 2, 3), (6, 2, 3)]
• Update the map:
  • Map: {1: (0, None), 2: (1, 1), 3: (1, 1)}

Step 4: Process node (4)

• Dequeue (4, 2, 2):
  • Current node: 4
  • Depth: 2
  • Parent: 2
• Node 4 has no children, so nothing is added to the queue.
• Update the map:
  • Map: {1: (0, None), 2: (1, 1), 3: (1, 1), 4: (2, 2)}

Step 5: Process node (5)

• Dequeue (5, 2, 3):
  • Current node: 5
  • Depth: 2
  • Parent: 3
• Node 5 has no children, so nothing is added to the queue.
• Update the map:
  • Map: {1: (0, None), 2: (1, 1), 3: (1, 1), 4: (2, 2), 5: (2, 3)}

Step 6: Process node (6)

• Dequeue (6, 2, 3):
  • Current node: 6
  • Depth: 2
  • Parent: 3
• Node 6 has no children, so nothing is added to the queue.
• Update the map:
  • Map: {1: (0, None), 2: (1, 1), 3: (1, 1), 4: (2, 2), 5: (2, 3), 6: (2, 3)}

Check Cousin Condition

• Retrieve the information of nodes 4 and 5:
  • Node 4: Depth = 2, Parent = 2
  • Node 5: Depth = 2, Parent = 3
• Since the depths are the same and the parents are different, return true.

Code

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) {
//         val = x;
//     }
// }

class Solution {
    class NodeInfo {
        int depth;
        TreeNode parent;
        NodeInfo(int depth, TreeNode parent) {
            this.depth = depth;
            this.parent = parent;
        }
    }

    public boolean isCousins(TreeNode root, int x, int y) {
        // Map to store depth and parent information
        Map<Integer, NodeInfo> map = new HashMap<>();
        // Queue for BFS
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        map.put(root.val, new NodeInfo(0, null));

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            NodeInfo nodeInfo = map.get(node.val);
            
            // Add left child to the queue
            if (node.left != null) {
                queue.add(node.left);
                map.put(node.left.val, new NodeInfo(nodeInfo.depth + 1, node));
            }
            // Add right child to the queue
            if (node.right != null) {
                queue.add(node.right);
                map.put(node.right.val, new NodeInfo(nodeInfo.depth + 1, node));
            }
        }

        NodeInfo xInfo = map.get(x);
        NodeInfo yInfo = map.get(y);
        // Check if x and y are cousins
        return xInfo.depth == yInfo.depth && xInfo.parent != yInfo.parent;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // Example 1
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(3);
        root1.left.left = new TreeNode(4);
        root1.right.left = new TreeNode(5);
        root1.right.right = new TreeNode(6);
        System.out.println(sol.isCousins(root1, 4, 5)); // true

        // Example 2
        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(3);
        root2.left.left = new TreeNode(4);
        root2.left.right = new TreeNode(5);
        root2.left.right.left = new TreeNode(6);
        root2.left.right.right = new TreeNode(7);
        System.out.println(sol.isCousins(root2, 6, 7)); // false

        // Example 3
        TreeNode root3 = new TreeNode(1);
        root3.left = new TreeNode(2);
        root3.right = new TreeNode(3);
        root3.left.right = new TreeNode(4);
        root3.right.left = new TreeNode(5);
        System.out.println(sol.isCousins(root3, 4, 5)); // true
    }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is , where N is the number of nodes in the binary tree. This is because we traverse each node exactly once during the BFS traversal.

Space Complexity

The space complexity is also . In the worst case, the queue used for BFS could store all the nodes at the deepest level of the tree, which is proportional to the total number of nodes. Additionally, the hash map used to store node information also requires space.