993. Cousins in Binary Tree

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree
Leetcode Link

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 and y that correspond to the values of two nodes within the binary tree.

The output is:

  • A boolean value true or false indicating whether the two nodes with values x and y 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:

  1. Is it a graph?

    • Yes: A binary tree is a type of graph.

  2. Is it a tree?

    • Yes: A binary tree, by definition, is a tree.

  3. 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:

  1. The depths of nodes x and y must be the same, which ensures they are at the same level of the tree.
  2. The parents of nodes x and y 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:

  1. 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 array t that stores the parent and depth information for nodes x and y.

  2. If the current node root is None (meaning we've reached a leaf or the tree is empty), the function simply returns as there is nothing further to explore.

  3. The function checks if the current node's value is equal to x or y. If it is, the corresponding tuple of (parent, depth) is stored in the array t. Specifically, t[0] is used for x and t[1] for y. This is how the function keeps track of the required information for determining if the nodes are cousins.

  4. 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.

  5. After initiating the DFS from the root node with a None parent and depth 0, the solution checks whether the stored parents are different and the stored depths are the same for x and y. It uses the statement return t[0][0] != t[1][0] and t[0][1] == t[1][1] which essentially says, return true if the parents are not the same and the depths are the same; otherwise, return false.

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 Evaluator

Example 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.

  1. We start DFS traversal from the root node (value 1). The dfs function is called with the arguments root (the current node), fa (the parent node), and d (the depth). So initially, dfs(1, None, 0) is called since 1 is the root with no parent and is at depth 0.

  2. The recursion now explores the left child of the root node > dfs(2, 1, 1).

    • At node 2, neither x nor y is found, so we proceed to its left child with a depth increased by 1 > dfs(4, 2, 2).

  3. At node 4, we have found x=4. We store the parent and depth information in t[0] = (2, 2) and return to the previous call.

  4. 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).

  5. At node 3, neither x nor y is found, so we proceed to its right child with increased depth > dfs(5, 3, 2).

  6. At node 5, we have found y=5. We store the parent and depth information in t[1] = (3, 2) and return to the previous call.

  7. 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 node 4, and
  • t[1] = (3, 2) for node 5.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Recommended Readings

Everything About Trees

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

DFS Fundamentals

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

BFS Fundamentals

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!

Raj Raj

Thanks for the fair implementation. Although, I have one concern with the above approach. Traversal will continue even through we have got both the parent and depth x/y. How can we come out of the recursion as soon as parent and depth of x/y is found.

Thu Oct 24 2024