Are Twins? - codepath/compsci_guides GitHub Wiki

Unit 8 Session 1 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 10 mins
  • 🛠️ Topics: Binary Tree, Tree Comparison

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What does it mean for the children to be twins?
    • The children are twins if they have the same value.
  • What should the function return if the root has only one or no children?
    • The function should return False if the root has fewer than two children.
HAPPY CASE
Input: Binary tree with root value "Mermother" and children values "Coral", "Coral"
Output: True
Explanation: Both children of the root have the value "Coral", so they are considered twins.

EDGE CASE
Input: Binary tree with root value "Merenby" and only one child with value "Calypso"
Output: False
Explanation: The root has only one child, so it can't have twin children.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Tree Comparison problems, we want to consider the following approaches:

  • Binary Tree Comparison: Directly compare the values of the left and right children.
  • Conditional Logic: Use simple conditionals to check if the root has both children and if they are equal.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Check if the root has two children and if they have the same value.

1) If the root has no children or only one child, return False.
2) Compare the values of the left and right children.
3) If the values are equal, return True; otherwise, return False.

⚠️ Common Mistakes

  • Not accounting for the case where the tree has only one child.
  • Assuming that both children exist without checking, which could lead to errors.

4: I-mplement

Implement the code to solve the algorithm.

def mertwins(root):
    if not root.left or not root.right:
        return False  # If either left or right branch is missing, they can't be equal
    return root.left.val == root.right.val

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Test with the examples given:
    • Input 1: Binary tree with root "Mermother" and children "Coral", "Coral"
    • Expected Output: True
    • Input 2: Binary tree with root "Merpapa" and children "Calypso", "Coral"
    • Expected Output: False
    • Input 3: Binary tree with root "Merenby" and only one child "Calypso"
    • Expected Output: False
    • Verify that the outputs match the expected results.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of nodes in the binary tree.

  • Time Complexity: O(1) because the algorithm only checks the root's children without needing to traverse the tree.
  • Space Complexity: O(1) as no additional space is used beyond the input.