993. Cousins in Binary Tree
Problem Description
The problem requires determining if two nodes within a binary tree are cousins. In binary tree terminology, cousins are defined as nodes that are on the same level (or depth) but do not share the same parent.
The inputs to the function are:
- A binary tree
root
, where each node contains a unique value. - Two integer values
x
andy
that correspond to the values of two nodes within the binary tree.
The output is:
- A boolean value
true
orfalse
indicating whether the two nodes with valuesx
andy
are indeed cousins.
It is important to clarify that the depth of the root node is considered to be 0
, and each successive level in the tree increments the depth by 1
.
Flowchart Walkthrough
Let's apply the algorithm using the Flowchart to analyze how to determine cousins in a binary tree, as presented in LeetCode problem 993. Here’s a step-by-step guide:
-
Is it a graph?
- Yes: A binary tree is a type of graph.
-
Is it a tree?
- Yes: A binary tree, by definition, is a tree.
-
DFS
- We follow this path since it directly relates to tree traversal. Depth-First Search (DFS) is particularly useful in trees for exploring nodes deeply before visiting siblings.
Conclusion: Based on the flowchart, Depth-First Search (DFS) is recommended for solving problems like finding cousins in a binary tree primarily because the problem involves deep diving into tree nodes to check conditions at each node's level and parent. Thus, DFS allows us to handle these checks effectively within a tree structure.
Intuition
The solution to this problem requires a way to traverse the tree and determine the depth and parent of each node we are interested in (x
and y
). The approach chosen here uses Depth-First Search (DFS) to explore the tree.
The DFS allows us to traverse down each branch of the tree until we hit a leaf, keeping track of the depth and parent node at each step. Each time we make a move to a child node, the depth increases by 1
.
During the DFS, whenever we come across either of the values x
or y
, we store the parent node and depth in a tuple. Since x
and y
are distinct and unique, when one is found, its corresponding information is stored in an array t
, at index 0
for x
, and index 1
for y
.
Lastly, after the traversal, we compare the stored depths and parents of nodes x
and y
. To be cousins, the following conditions must both hold:
- The depths of nodes
x
andy
must be the same, which ensures they are at the same level of the tree. - The parents of nodes
x
andy
must be different, which ensures they do not share the same parent.
If both conditions are satisfied, we return true
, confirming that the nodes are cousins; otherwise, we return false
.
Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.
Solution Approach
The provided solution uses Depth-First Search (DFS), a classic tree traversal algorithm that explores as far as possible down each branch before backtracking. DFS is well-suited for this problem because it allows us to track the depth and parent of each node as we traverse the tree.
Here's a step-by-step implementation of the DFS algorithm for this problem:
-
Create a helper function
dfs
that takes the current node being visited (root
), its parent (fa
), and the current depth (d
) as arguments. The helper function will also need access to an arrayt
that stores the parent and depth information for nodesx
andy
. -
If the current node
root
isNone
(meaning we've reached a leaf or the tree is empty), the function simply returns as there is nothing further to explore. -
The function checks if the current node's value is equal to
x
ory
. If it is, the corresponding tuple of(parent, depth)
is stored in the arrayt
. Specifically,t[0]
is used forx
andt[1]
fory
. This is how the function keeps track of the required information for determining if the nodes are cousins. -
Continue the DFS on the left and right children of the current node, increasing the depth by
1
and passing the current node as the new parent. -
After initiating the DFS from the root node with a
None
parent and depth0
, the solution checks whether the stored parents are different and the stored depths are the same forx
andy
. It uses the statementreturn t[0][0] != t[1][0] and t[0][1] == t[1][1]
which essentially says, returntrue
if the parents are not the same and the depths are the same; otherwise, returnfalse
.
This solution is efficient, as DFS ensures that each node is visited exactly once, resulting in a time complexity of O(n), where n is the number of nodes in the tree. No additional space is used besides the recursive stack and the array t
, leading to a space complexity of O(n) due to the height of the recursive call stack.
By leveraging DFS and efficiently keeping track of the parent and depth of each node, this solution effectively determines whether two nodes are cousins in a binary tree.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a simple binary tree and follow the steps of the solution approach to determine if two nodes are cousins. Here's our example binary tree:
1 / \ 2 3 / \ 4 5
Let's say we want to check if node 4 (with value x=4
) and node 5 (with value y=5
) are cousins.
-
We start DFS traversal from the root node (value
1
). Thedfs
function is called with the argumentsroot
(the current node),fa
(the parent node), andd
(the depth). So initially,dfs(1, None, 0)
is called since1
is the root with no parent and is at depth0
. -
The recursion now explores the left child of the root node >
dfs(2, 1, 1)
.- At node
2
, neitherx
nory
is found, so we proceed to its left child with a depth increased by 1 >dfs(4, 2, 2)
.
- At node
-
At node
4
, we have foundx=4
. We store the parent and depth information int[0] = (2, 2)
and return to the previous call. -
Since node
2
has no right child, the recursion ends here, and we go back to the root node to explore its right child >dfs(3, 1, 1)
. -
At node
3
, neitherx
nory
is found, so we proceed to its right child with increased depth >dfs(5, 3, 2)
. -
At node
5
, we have foundy=5
. We store the parent and depth information int[1] = (3, 2)
and return to the previous call. -
All nodes have been visited and the recursion concludes.
After traversing the tree, we examine the values in t
. We have:
t[0] = (2, 2)
for node4
, andt[1] = (3, 2)
for node5
.
We compare the parents, 2
and 3
, and find they are different. We also compare the depths, both 2
, and find they are the same.
According to our two conditions for the nodes to be cousins:
- The depths are the same (true).
- The parents are different (true).
Therefore, the function returns true
signifying that node 4
and node 5
are indeed cousins in the binary tree.
Solution Implementation
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
9 # Helper function to perform depth-first search (DFS)
10 def dfs(node, parent, depth):
11 if node is None:
12 return
13 if node.val == x:
14 # Record the parent and depth for x
15 found_nodes[0] = (parent, depth)
16 if node.val == y:
17 # Record the parent and depth for y
18 found_nodes[1] = (parent, depth)
19
20 # Recursion for left and right children
21 dfs(node.left, node, depth + 1)
22 dfs(node.right, node, depth + 1)
23
24 # Initialize nodes as a list to hold the pair (parent, depth) for x and y
25 found_nodes = [None, None]
26
27 # Call DFS starting from the root, without a parent and at depth 0
28 dfs(root, None, 0)
29
30 # Check if x and y have different parents and the same depth
31 return found_nodes[0][0] != found_nodes[1][0] and found_nodes[0][1] == found_nodes[1][1]
32
33# Example of using the class:
34# Create a binary tree with TreeNode instances, then
35# solution = Solution()
36# result = solution.isCousins(root, x, y)
37
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5 int val;
6 TreeNode left;
7 TreeNode right;
8
9 TreeNode() {}
10
11 TreeNode(int val) {
12 this.val = val;
13 }
14
15 TreeNode(int val, TreeNode left, TreeNode right) {
16 this.val = val;
17 this.left = left;
18 this.right = right;
19 }
20}
21
22class Solution {
23 private int targetValueX, targetValueY;
24 private TreeNode parentX, parentY;
25 private int depthX, depthY;
26
27 /**
28 * Determines if two nodes are cousins in a binary tree.
29 * Nodes are considered cousins if they are on the same level of the tree,
30 * but have different parents.
31 *
32 * @param root The root node of the binary tree.
33 * @param x The value of the first node.
34 * @param y The value of the second node.
35 * @return true if the nodes with values x and y are cousins, false otherwise.
36 */
37 public boolean isCousins(TreeNode root, int x, int y) {
38 this.targetValueX = x;
39 this.targetValueY = y;
40 // Start the depth-first search from the root, with null parent and depth 0
41 dfs(root, null, 0);
42 // Nodes are cousins if they have the same depth but different parents
43 return parentX != parentY && depthX == depthY;
44 }
45
46 /**
47 * Helper method to perform a depth-first search on the binary tree.
48 *
49 * @param node The current node to process.
50 * @param parent The parent of the current node.
51 * @param depth The current depth in the tree.
52 */
53 private void dfs(TreeNode node, TreeNode parent, int depth) {
54 if (node == null) {
55 return;
56 }
57 if (node.val == targetValueX) {
58 parentX = parent;
59 depthX = depth;
60 }
61 if (node.val == targetValueY) {
62 parentY = parent;
63 depthY = depth;
64 }
65 // Recursively process left and right subtrees, increasing the depth
66 dfs(node.left, node, depth + 1);
67 dfs(node.right, node, depth + 1);
68 }
69}
70
1#include <functional> // Include the functional header for std::function
2
3// Definition for a binary tree node.
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode() : val(0), left(nullptr), right(nullptr) {}
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15 // Determines if two nodes of a binary tree are cousins (same depth, but different parents)
16 bool isCousins(TreeNode* root, int x, int y) {
17 TreeNode *parentX, *parentY; // Nodes to keep track of each target node's parent
18 int depthX, depthY; // Variables to keep track of each target node's depth
19
20 // Depth-first search lambda function to find parent and depth of target nodes
21 std::function<void(TreeNode*, TreeNode*, int)> dfs = [&](TreeNode* node, TreeNode* parent, int depth) {
22 if (!node) {
23 return; // Base case: if the node is null, do nothing
24 }
25 if (node->val == x) {
26 // If the current node value is x, store the parent and depth
27 parentX = parent;
28 depthX = depth;
29 }
30 if (node->val == y) {
31 // If the current node value is y, store the parent and depth
32 parentY = parent;
33 depthY = depth;
34 }
35 // Recursive calls to search in the left and right subtrees, increasing depth by 1
36 dfs(node->left, node, depth + 1);
37 dfs(node->right, node, depth + 1);
38 };
39
40 // Initialize the search on the root with null parent and depth 0
41 dfs(root, nullptr, 0);
42
43 // Two nodes are cousins if they have different parents but the same depth
44 return parentX != parentY && depthX == depthY;
45 }
46};
47
1// Binary tree node structure
2interface TreeNode {
3 val: number;
4 left: TreeNode | null;
5 right: TreeNode | null;
6}
7
8// Function to create a new TreeNode given a value, left and right nodes
9function createTreeNode(val: number, left?: TreeNode, right?: TreeNode): TreeNode {
10 return {
11 val: val,
12 left: left || null,
13 right: right || null
14 };
15}
16
17// Variable to keep track of a target node's parent
18let parentNodeX: TreeNode | null;
19let parentNodeY: TreeNode | null;
20
21// Variables to keep track of each target node's depth
22let depthNodeX: number;
23let depthNodeY: number;
24
25// Depth-first search function to find parent and depth of target nodes
26function depthFirstSearch(node: TreeNode | null, parent: TreeNode | null, depth: number) {
27 if (!node) {
28 return; // Base case: if the node is null, do nothing
29 }
30 if (node.val === x) {
31 // If the current node value is x, store the parent and depth
32 parentNodeX = parent;
33 depthNodeX = depth;
34 }
35 if (node.val === y) {
36 // If the current node value is y, store the parent and depth
37 parentNodeY = parent;
38 depthNodeY = depth;
39 }
40
41 // Recursive calls to search in the left and right subtrees, increasing depth by 1
42 depthFirstSearch(node.left, node, depth + 1);
43 depthFirstSearch(node.right, node, depth + 1);
44}
45
46// Determines if two nodes of a binary tree are cousins (same depth, but different parents)
47function isCousins(root: TreeNode, x: number, y: number): boolean {
48 // Initialize the search on the root with null parent and depth 0
49 depthFirstSearch(root, null, 0);
50
51 // Two nodes are cousins if they have different parents but the same depth
52 return parentNodeX !== parentNodeY && depthNodeX === depthNodeY;
53}
54
55// Example usage:
56// let root = createTreeNode(1, createTreeNode(2), createTreeNode(3));
57// let result = isCousins(root, 2, 3); // Should be false since 2 and 3 are siblings, not cousins
58
Time and Space Complexity
Time Complexity
The given code traverses the binary tree to find the levels and parents of the nodes with values x
and y
. It uses a Depth First Search (DFS) approach that visits every node exactly once. Therefore, the time complexity of the code is O(n)
, where n
is the number of nodes in the binary tree. No matter what, the algorithm must visit every node to ensure that it finds the nodes x
and y
.
Space Complexity
The space complexity of the code is mainly determined by the maximum depth of the recursion stack, which depends on the height of the tree. In the worst-case scenario for a skewed tree, the height of the tree can be O(n)
, leading to a space complexity of O(n)
. However, in a balanced tree, the height would be O(log n)
, resulting in a space complexity of O(log n)
. The auxiliary space used to store the parent and depth (t[0]
and t[1]
) is constant, hence it doesn't significantly affect the space complexity. So, the overall space complexity is O(n)
in the worst case for a skewed tree or O(log n)
for a balanced tree.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Want a Structured Path to Master System Design Too? Don’t Miss This!