Cousins in Binary Tree

LeetCode Q 993 - Cousins in Binary Tree

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.
Two nodes of a binary tree are cousins if they have the same depth, but have different parents.
We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.
Return true if and only if the nodes corresponding to the values x and y are cousins.

Example 1: Input: root = [1,2,3,4], x = 4, y = 3 ; Output: false
Example 2: Input: root = [1,2,3,null,4,null,5], x = 5, y = 4 ; Output: true
Example 3: Input: root = [1,2,3,null,4], x = 2, y = 3 ; Output: false

Note:

• The number of nodes in the tree will be between 2 and 100.
• Each node has a unique integer value from 1 to 100.

Solution: Using maps

Code:

Map<Integer, TreeNode> parentsMap;
Map<Integer, Integer> depthsMap;
public boolean isCousins(TreeNode root, int x, int y) {
  parentsMap = new HashMap<>();
  depthsMap = new HashMap<>();
  
  buildsMap(root, 0);
  parentsMap.put(root.val, root);
  
  return depthsMap.get(x) == depthsMap.get(y) && parentsMap.get(x) != parentsMap.get(y);
}

private void buildsMap(TreeNode root, int depth) {
  depthsMap.put(root.val, depth);
  
  if (root.left != null) {
    parentsMap.put(root.left.val, root);
    buildsMap(root.left, depth + 1);
  }
  
  if (root.right != null) {
    parentsMap.put(root.right.val, root);
    buildsMap(root.right, depth + 1);
  }
}