Problem: 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.
Example:
Input: root = [1,2,3,4], x = 4, y = 3 Output: false
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4 Output: true
Input: root = [1,2,3,null,4], x = 2, y = 3 Output: false
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.
Approach: We can use level order traversal to solve this question. Basically if both x and y are on the same level means both have the same depth.
Now while inserting current node's left and right in the queue, we can check left and right nodes have the value x and y. If yes, then we can return false as parent of x and y is same.
Implementation in C#:
public bool IsCousins(TreeNode root, int x, int y)
{
bool foundX = false, foundY = false;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while(queue.Count > 0)
{
int size = queue.Count;
for (int i = 0; i < size; ++i)
{
TreeNode node = queue.Dequeue();
if (node.val == x)
{
foundX = true;
}
else if (node.val == y)
{
foundY = true;
}
if (node.left != null && node.right != null)
{
// Check for same parent
if ((node.left.val == x && node.right.val == y)
|| (node.left.val == y && node.right.val == x))
{
return false;
}
}
if (node.left != null)
{
queue.Enqueue(node.left);
}
if (node.right != null)
{
queue.Enqueue(node.right);
}
}
if (foundX && foundY)
{
return true;
}
else if (foundX || foundY)
{
return false;
}
}
return false;
}
Complexity: O(n)
No comments:
Post a Comment