Jobs

Interviews

Discussions

Symmetric Tree

Easy

Amazon

3 views

Topics:

TreesRecursion

Given the root of a binary tree, determine if it is a mirror of itself (symmetric around its center). For example:

Example 1:

Consider the following binary tree:

This tree is symmetric because the left and right subtrees are mirror images of each other. Therefore, the output should be true.

Example 2:

Consider the following binary tree:

This tree is not symmetric because the left and right subtrees are not mirror images of each other. Specifically, the right child of the left subtree is 3, while the left child of the right subtree is null. Therefore, the output should be false.

Write a function that takes the root of a binary tree as input and returns true if the tree is symmetric and false otherwise.

Things to consider:

What are the base cases for recursion?
How do you compare the structure and values of the left and right subtrees?
How does your function handle null nodes?

Symmetric Tree

Easy

Amazon

3 views

Topics:

TreesRecursion

Given the root of a binary tree, determine if it is a mirror of itself (symmetric around its center). For example:

Example 1:

Consider the following binary tree:

This tree is symmetric because the left and right subtrees are mirror images of each other. Therefore, the output should be true.

Example 2:

Consider the following binary tree:

Write a function that takes the root of a binary tree as input and returns true if the tree is symmetric and false otherwise.

Things to consider:

What are the base cases for recursion?
How do you compare the structure and values of the left and right subtrees?
How does your function handle null nodes?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes can contain?
Can the tree be empty or contain only one node?
Is the symmetric check based on node values or node structure (i.e., can different values be in symmetric positions)?
Does the solution need to be iterative or recursive, or can I choose?
Are we concerned with integer overflow when comparing values or performing calculations within the tree nodes?

Brute Force Solution

Approach

The brute force approach to determine if a tree is symmetric involves checking all possible arrangements of the tree's structure to see if any of them form a mirrored image of itself. We essentially explore every possible combination to exhaustively test for symmetry. It is like meticulously comparing each node's position and value with its potential mirror counterpart in the entire tree.

Here's how the algorithm would work step-by-step:

Start by considering the very top node of the tree; this is our starting point.
Then, look at its two immediate children, one on the left and one on the right.
Compare their values. If they are different, we immediately know the tree is not symmetric, and we stop.
If the values of the immediate children are the same, move deeper into the tree.
Now, for each level down, carefully check if the left side of the tree mirrors the right side.
This means that for every pair of nodes that are supposed to be mirror images, their values must be equal.
And, crucially, their children (the nodes below them) must also be mirror images of each other, following the same rules.
If at any point you find two nodes that should be mirroring each other but don't have the same value or structure, the tree is not symmetric, and you stop.
Continue this comparison process for every possible pair of nodes that should be mirror images throughout the entire tree.
If, after checking every single pair, you never find a mismatch, then the tree is symmetric.

Code Implementation

def is_symmetric_brute_force(root):
    # Handle the base case where the tree is empty
    if not root:
        return True

    # This helper function exhaustively checks all possible mirror images
    def are_nodes_symmetric(left_node, right_node):
        if not left_node and not right_node:
            return True
        if not left_node or not right_node:
            return False

        # If values are unequal, subtree cannot be symmetric
        if left_node.val != right_node.val:
            return False

        # Recursively check the mirroring subtrees
        return are_nodes_symmetric(left_node.left, right_node.right) and \
               are_nodes_symmetric(left_node.right, right_node.left)

    return are_nodes_symmetric(root.left, root.right)

Big(O) Analysis

Time Complexity

O(n!) – The described brute force approach explores every possible arrangement of the tree. In the worst-case scenario, it might involve checking all permutations of the nodes to find a matching mirrored structure. This is because the algorithm, as described, compares every node's potential mirror counterpart. Comparing every possible arrangement of 'n' nodes leads to n! (n factorial) comparisons. Therefore, the time complexity of this exhaustive approach is O(n!).

Space Complexity

O(N) – The provided algorithm uses a recursive approach to traverse the tree. In the worst-case scenario, such as a skewed tree, the recursion depth can reach N, where N is the number of nodes in the tree. Each recursive call adds a frame to the call stack, consuming memory. Therefore, the auxiliary space complexity is proportional to the maximum depth of the recursion, which is O(N).

Optimal Solution

Approach

The problem asks us to check if a tree is symmetric, meaning it's a mirror image of itself. The most efficient way to do this is to compare the left and right subtrees simultaneously to see if they match up perfectly.

Here's how the algorithm would work step-by-step:

First, consider the root. The left and right children of the root should be mirror images of each other.
We can check if two trees are mirror images by comparing their structure and values at the same time.
Imagine comparing the left subtree and the reversed right subtree. If they are identical in structure and value, the original tree is symmetric.
To do this, use a function that takes two tree nodes as input: one from the left subtree, one from the right subtree. It should check the following:
Are both nodes null? If so, they match. Return true.
Is only one of the nodes null? If so, they don't match. Return false.
Do the values of the two nodes match? If not, they don't match. Return false.
If the values match, then recursively call the function to compare the left child of the 'left' node with the right child of the 'right' node, and the right child of the 'left' node with the left child of the 'right' node.
Only if all these checks pass will the two subtrees be mirror images. Using this approach we only ever visit each node once, making the solution fast.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_symmetric(root: TreeNode) -> bool:
    def are_mirror_images(left_node: TreeNode, right_node: TreeNode) -> bool:
        # If both are null, they are a mirror
        if not left_node and not right_node:
            return True

        # Only one is null, so not a mirror
        if not left_node or not right_node:
            return False

        # Values don't match, not a mirror
        if left_node.val != right_node.val:
            return False

        # Recursively check the subtrees
        return (are_mirror_images(left_node.left, right_node.right) and\
                are_mirror_images(left_node.right, right_node.left))

    # The tree is symmetric if the root's
    # left and right subtrees are mirrors.
    if not root:
        return True

    return are_mirror_images(root.left, root.right)

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses the binary tree by comparing nodes in the left and right subtrees simultaneously using recursion. In the worst-case scenario, it may need to visit every node in the tree to verify symmetry. Therefore, the time complexity is directly proportional to the number of nodes, n, in the tree, resulting in a linear time complexity of O(n).

Space Complexity

O(H) – The provided algorithm uses recursion. In the worst-case scenario, the recursion depth can be equal to the height (H) of the tree. Each recursive call adds a new frame to the call stack, consuming memory. Therefore, the auxiliary space complexity is determined by the maximum depth of the recursion, which is O(H), where H is the height of the tree. In the worst case (a skewed tree), H can be equal to N, the number of nodes, but in a balanced tree, H would be log(N).

Edge Cases

Case	How to Handle
Null root	Return true since a null tree is considered symmetric.
Single node tree	Return true as a single node tree is inherently symmetric.
Unbalanced tree where one side is deeper than the other	The recursive/iterative check will eventually encounter a null node on the shorter side and compare it to a non-null node on the deeper side, resulting in false.
Large tree depth, potential stack overflow with recursion	Consider using an iterative approach (e.g., using a queue) to avoid stack overflow errors, especially in languages with limited stack space.
Tree with identical values on all nodes, but asymmetric structure	The algorithm should compare structure as well as values; if the structure is different, even with identical values, it returns false.
One subtree is null, the other is not	Comparison of a null node with a non-null node will return false indicating asymmetry.
Integer overflow during comparison (if values can be very large)	The problem description usually assumes standard integers; if large numbers are expected, ensure the comparison method is robust to potential overflows.
Skewed tree (all nodes on one side)	A skewed tree is clearly not symmetric, and the algorithm should correctly identify this case and return false.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes can contain?
Can the tree be empty or contain only one node?
Is the symmetric check based on node values or node structure (i.e., can different values be in symmetric positions)?
Does the solution need to be iterative or recursive, or can I choose?
Are we concerned with integer overflow when comparing values or performing calculations within the tree nodes?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the very top node of the tree; this is our starting point.
Then, look at its two immediate children, one on the left and one on the right.
Compare their values. If they are different, we immediately know the tree is not symmetric, and we stop.
If the values of the immediate children are the same, move deeper into the tree.
Now, for each level down, carefully check if the left side of the tree mirrors the right side.
This means that for every pair of nodes that are supposed to be mirror images, their values must be equal.
And, crucially, their children (the nodes below them) must also be mirror images of each other, following the same rules.
If at any point you find two nodes that should be mirroring each other but don't have the same value or structure, the tree is not symmetric, and you stop.
Continue this comparison process for every possible pair of nodes that should be mirror images throughout the entire tree.
If, after checking every single pair, you never find a mismatch, then the tree is symmetric.

Code Implementation

def is_symmetric_brute_force(root):
    # Handle the base case where the tree is empty
    if not root:
        return True

    # This helper function exhaustively checks all possible mirror images
    def are_nodes_symmetric(left_node, right_node):
        if not left_node and not right_node:
            return True
        if not left_node or not right_node:
            return False

        # If values are unequal, subtree cannot be symmetric
        if left_node.val != right_node.val:
            return False

        # Recursively check the mirroring subtrees
        return are_nodes_symmetric(left_node.left, right_node.right) and \
               are_nodes_symmetric(left_node.right, right_node.left)

    return are_nodes_symmetric(root.left, root.right)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider the root. The left and right children of the root should be mirror images of each other.
We can check if two trees are mirror images by comparing their structure and values at the same time.
Imagine comparing the left subtree and the reversed right subtree. If they are identical in structure and value, the original tree is symmetric.
To do this, use a function that takes two tree nodes as input: one from the left subtree, one from the right subtree. It should check the following:
Are both nodes null? If so, they match. Return true.
Is only one of the nodes null? If so, they don't match. Return false.
Do the values of the two nodes match? If not, they don't match. Return false.
If the values match, then recursively call the function to compare the left child of the 'left' node with the right child of the 'right' node, and the right child of the 'left' node with the left child of the 'right' node.
Only if all these checks pass will the two subtrees be mirror images. Using this approach we only ever visit each node once, making the solution fast.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_symmetric(root: TreeNode) -> bool:
    def are_mirror_images(left_node: TreeNode, right_node: TreeNode) -> bool:
        # If both are null, they are a mirror
        if not left_node and not right_node:
            return True

        # Only one is null, so not a mirror
        if not left_node or not right_node:
            return False

        # Values don't match, not a mirror
        if left_node.val != right_node.val:
            return False

        # Recursively check the subtrees
        return (are_mirror_images(left_node.left, right_node.right) and\
                are_mirror_images(left_node.right, right_node.left))

    # The tree is symmetric if the root's
    # left and right subtrees are mirrors.
    if not root:
        return True

    return are_mirror_images(root.left, root.right)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root	Return true since a null tree is considered symmetric.
Single node tree	Return true as a single node tree is inherently symmetric.
Unbalanced tree where one side is deeper than the other	The recursive/iterative check will eventually encounter a null node on the shorter side and compare it to a non-null node on the deeper side, resulting in false.
Large tree depth, potential stack overflow with recursion	Consider using an iterative approach (e.g., using a queue) to avoid stack overflow errors, especially in languages with limited stack space.
Tree with identical values on all nodes, but asymmetric structure	The algorithm should compare structure as well as values; if the structure is different, even with identical values, it returns false.
One subtree is null, the other is not	Comparison of a null node with a non-null node will return false indicating asymmetry.
Integer overflow during comparison (if values can be very large)	The problem description usually assumes standard integers; if large numbers are expected, ensure the comparison method is robust to potential overflows.
Skewed tree (all nodes on one side)	A skewed tree is clearly not symmetric, and the algorithm should correctly identify this case and return false.