Cousins in Binary Tree — LeetCode 993 Python Solution
EasyTreeDepth-First SearchBreadth-First SearchBinary Tree
- Problem
- #993
- Pattern
- Tree Traversal
- Reading time
- 4 min
- Source
- leetcode.com
The 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.
Example
- Input
- root = [1,2,3,4], x = 4, y = 3
- Output
- false
Python solution
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
q = deque([(root, None)])
depth = 0
p1 = p2 = None
d1 = d2 = None
while q:
for _ in range(len(q)):
node, parent = q.popleft()
if node.val == x:
p1, d1 = parent, depth
elif node.val == y:
p2, d2 = parent, depth
if node.left:
q.append((node.left, node))
if node.right:
q.append((node.right, node))
depth += 1
return p1 != p2 and d1 == d2Complexity
| Measure | Complexity |
|---|---|
| Time | O(V+E) |
| Space | O(V) auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 993. Cousins in Binary Tree is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 993. Cousins in Binary Tree?
- LeetCode 993. Cousins in Binary Tree is rated Easy on LeetCode.
- What is the time complexity of LeetCode 993. Cousins in Binary Tree?
- The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 993. Cousins in Binary Tree?
- The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 993. Cousins in Binary Tree cover?
- LeetCode 993. Cousins in Binary Tree is tagged Tree, Depth-First Search, Breadth-First Search and Binary Tree on LeetCode.