Cousins in Binary Tree
Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise. Two nodes of a binary tree are cousins if they have the same depth with different parents. Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.
Approach 1: Iterative
class Solution {
public boolean isCousins(TreeNode root, int A, int B) {
if (root == null)
return false;
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
boolean isAexist = false;
boolean isBexist = false;
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
if (cur.val == A)
isAexist = true;
if (cur.val == B)
isBexist = true;
if (cur.left != null && cur.right != null) {
if (cur.left.val == A && cur.right.val == B) {
return false;
}
if (cur.left.val == B && cur.right.val == A) {
return false;
}
}
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
if (isAexist && isBexist)
return true;
}
return false;
}
}
Time Complexity: O(n) and Space Complexity: O(n)
Approach 2: Recursive dfs
class Solution {
TreeNode xParent = null;
TreeNode yParent = null;
int xDepth = -1, yDepth = -1;
public boolean isCousins(TreeNode root, int x, int y) {
getDepthAndParent(root, x, y, 0, null);
return xDepth == yDepth && xParent != yParent ? true : false;
}
// get both the depth and parent for x and y
public void getDepthAndParent(TreeNode root, int x, int y, int depth, TreeNode parent) {
if (root == null) {
return;
}
if (root.val == x) {
xParent = parent;
xDepth = depth;
} else if (root.val == y) {
yParent = parent;
yDepth = depth;
}
getDepthAndParent(root.left, x, y, depth + 1, root);
getDepthAndParent(root.right, x, y, depth + 1, root);
}
}
Time Complexity: O(n) and Space Complexity: O(n)
The problem Cousins in Binary Tree involves checking if two nodes in a binary tree are cousins. Two nodes are cousins if they are at the same depth but have different parents. This problem tests your understanding of tree traversal and depth calculation.
Problem Statement
Given a binary tree and two node values x and y, determine if they are cousins. A node x and a node y are cousins if:
- They are at the same depth in the tree.
- They have different parents.
You need to return true if the nodes are cousins and false otherwise.
Approach to Solve the Problem
The solution involves using a breadth-first search (BFS) or depth-first search (DFS) to calculate the depth of each node and track its parent. Once we know the depth and parent for both nodes, we can easily determine if they are cousins.
Steps to Solve:
- Perform a BFS or DFS to find the depth and parent of both nodes
xandy. - Check if both nodes have the same depth.
- Ensure the nodes have different parents.
- If both conditions are met, return
true; otherwise, returnfalse.
Implementation
Here is the Python implementation:
class Solution:
def isCousins(self, root, x, y):
def dfs(node, depth, parent, x, y, info):
if not node:
return
if node.val == x or node.val == y:
info[node.val] = (depth, parent)
dfs(node.left, depth + 1, node, x, y, info)
dfs(node.right, depth + 1, node, x, y, info)
info = {}
dfs(root, 0, None, x, y, info)
if x in info and y in info:
depth_x, parent_x = info[x]
depth_y, parent_y = info[y]
return depth_x == depth_y and parent_x != parent_y
return False
Here is the Java implementation:
class Solution {
public boolean isCousins(TreeNode root, int x, int y) {
Map> info = new HashMap<>();
dfs(root, 0, null, x, y, info);
if (info.containsKey(x) && info.containsKey(y)) {
Pair xInfo = info.get(x);
Pair yInfo = info.get(y);
return xInfo.getKey().equals(yInfo.getKey()) && xInfo.getValue() != yInfo.getValue();
}
return false;
}
private void dfs(TreeNode node, int depth, TreeNode parent, int x, int y, Map> info) {
if (node == null) {
return;
}
if (node.val == x || node.val == y) {
info.put(node.val, new Pair<>(depth, parent));
}
dfs(node.left, depth + 1, node, x, y, info);
dfs(node.right, depth + 1, node, x, y, info);
}
}
Example
Consider the binary tree:
Tree Structure:
1
/ \
2 3
/ \ / \
4 5 6 7
We are given x = 4 and y = 5. These two nodes are at the same level (depth = 2) and have different parents (2 and 2). Therefore, x and y are cousins. The answer is true.
Complexity Analysis
Time Complexity: O(n), where n is the number of nodes in the binary tree. We traverse the tree once to find the depths and parents of both nodes.
Space Complexity: O(n), where n is the number of nodes. We use a map to store the depth and parent information of the nodes.
Applications
- Useful in problems where relationships between nodes matter, especially in hierarchical data like family trees or organizational structures.
- Can be applied in social network analysis to find relationships between different people in a network.
Conclusion
The Cousins in Binary Tree problem is an excellent exercise for understanding tree traversal techniques and how to efficiently store and compare node information during traversal. With BFS or DFS, we can easily determine the relationships between nodes and solve this problem efficiently.
Practice this problem to strengthen your skills in binary tree traversal and understand how parent-child relationships work in a tree structure.
