Jobs

Interviews

Discussions

Same Tree

Easy

Asked by:

More companies

51 views

Topics:

TreesRecursion

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints:

The number of nodes in both trees is in the range [0, 100].
-10⁴ <= Node.val <= 10⁴

Try coding it in LeetCode

Same Tree

Easy

Asked by:

51 views

Topics:

TreesRecursion

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints:

The number of nodes in both trees is in the range [0, 100].
-10⁴ <= Node.val <= 10⁴

Try coding it in LeetCode

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:

Can the binary tree nodes contain any data type, or are they specifically integers?
What is the range of possible values for the node values?
Can either `p` or `q` be null or empty trees, and how should that be handled?
By 'structurally identical', do you mean the trees must have the exact same shape, including the placement of null nodes?
Should the function return `true` or `false` (or some other value) if both input trees are null?

Brute Force Solution

Approach

The brute force method for checking if two trees are the same involves directly comparing every single part of one tree with the corresponding part of the other tree. It is like meticulously going through a checklist for each tree to see if they are absolutely identical. If any difference is found, we immediately know they are not the same.

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

First, check if both trees are completely empty. If they are, they are the same.
Next, if only one tree is empty while the other is not, they are different.
If both trees have values at their starting points, compare these values. If they're different, the trees are different.
If the starting values are the same, then we must check the left side of both trees in the exact same way. Treat the left sides as if they are smaller trees and start this whole process over.
If the left sides are the same, then we must also check the right side of both trees in the same way. Again, treat the right sides as smaller trees and repeat the whole process.
The trees are considered the same only if every corresponding value and every corresponding structure, from the very top to the very bottom, matches exactly.

Code Implementation

def is_same_tree(tree_one, tree_two):
    # Check if both trees are empty.
    if not tree_one and not tree_two:
        return True

    # Check if only one tree is empty.
    if not tree_one or not tree_two:
        return False

    # Compare the values of the root nodes.
    if tree_one.val != tree_two.val:
        return False

    # Recursively check the left subtrees.
    left_trees_are_same = is_same_tree(tree_one.left, tree_two.left)

    # If left trees aren't the same, overall not the same
    if not left_trees_are_same:
        return False

    # Recursively check the right subtrees.
    right_trees_are_same = is_same_tree(tree_one.right, tree_two.right)

    return right_trees_are_same

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node of both trees exactly once to compare their values and structure. In the worst case, where the trees are identical up to the last node, the function will recursively call itself for every node in the tree. Therefore, the time complexity is directly proportional to the number of nodes n in the smaller tree, as we need to traverse all nodes of both trees in the worst-case scenario. This results in a time complexity of O(n).

Space Complexity

O(H) – The space complexity is determined by the depth of the recursion stack. In the worst-case scenario, such as a skewed tree, the recursion might go as deep as the height (H) of the tree, where each recursive call adds a new frame to the stack. Thus, the auxiliary space used is proportional to the height of the tree. Therefore, the space complexity is O(H), which in a balanced tree becomes O(log N) and in a skewed tree can be O(N), where N is the number of nodes.

Optimal Solution

Approach

The best way to check if two trees are the same is to compare them piece by piece, simultaneously. We'll go down both trees at the same time, checking if each corresponding part matches up, and if not, immediately conclude they are different.

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

First, check if both trees are empty. If they are, then they are the same.
If only one of the trees is empty, they can't be the same, so say they are different.
If both trees have a top part, compare the values of these parts. If they are different, the trees are different.
If the top parts are the same, then we need to check if the left parts of the trees are the same using this exact same process.
Then, we need to check if the right parts of the trees are the same, again using the exact same process.
If the top parts, the left parts, and the right parts are all the same, then the trees are the same.

Code Implementation

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

def is_same_tree(tree_one, tree_two):
    # If both trees are empty, they are identical.
    if not tree_one and not tree_two:
        return True

    # If only one tree is empty, they cannot be identical.
    if not tree_one or not tree_two:
        return False

    # If the values of the current nodes are different, trees differ.
    if tree_one.val != tree_two.val:
        return False

    # Recursively check if the left subtrees are the same.
    left_subtree_is_same = is_same_tree(tree_one.left, tree_two.left)

    # Recursively check if the right subtrees are the same.
    right_subtree_is_same = is_same_tree(tree_one.right, tree_two.right)

    # The trees are the same if both subtrees are the same.
    return left_subtree_is_same and right_subtree_is_same

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses both trees simultaneously, comparing the values of corresponding nodes. In the worst-case scenario, the trees are identical, and the algorithm must visit all n nodes in both trees to confirm their sameness. Therefore, the time complexity is proportional to the number of nodes, resulting in O(n).

Space Complexity

O(H) – The provided algorithm uses recursion. Each recursive call adds a new frame to the call stack. In the worst-case scenario, the recursion might go all the way down to the leaf nodes of the tree, resulting in a call stack depth equal to the height (H) of the tree. Thus, the auxiliary space complexity is determined by the maximum depth of the recursion call stack, which is O(H), where H is the height of the tree. In the balanced tree case, H would be log(N), while in the skewed tree case, it would be N.

Edge Cases

Case	How to Handle
Both input trees are null	Return true, as two null trees are considered identical.
One tree is null, and the other is not null	Return false, as one tree having nodes while the other is empty means they are different.
Trees have different structures (different shapes), but the same values at corresponding nodes up to a point	The recursive or iterative check will eventually reach differing structural parts, returning false.
Trees have identical structure, but different values at one or more nodes	The value comparison within the recursive/iterative logic will identify the mismatch, returning false.
Large trees exceeding recursion depth limits (stack overflow)	Consider using an iterative approach (e.g., with a stack) to avoid recursion depth limitations.
Trees with only one node each, but different values	The root value comparison will immediately detect the difference, returning false.
Trees with only one node each, and the same values	The root value comparison will confirm equality, and since no further nodes exist, it returns true.
Trees with negative, zero, and positive integer values in their nodes	The standard integer comparison will handle all these value types correctly without special treatment.

Both input trees are null

How to Handle:

Return true, as two null trees are considered identical.

One tree is null, and the other is not null

How to Handle:

Return false, as one tree having nodes while the other is empty means they are different.

Trees have different structures (different shapes), but the same values at corresponding nodes up to a point

How to Handle:

The recursive or iterative check will eventually reach differing structural parts, returning false.

Trees have identical structure, but different values at one or more nodes

How to Handle:

The value comparison within the recursive/iterative logic will identify the mismatch, returning false.

Large trees exceeding recursion depth limits (stack overflow)

How to Handle:

Consider using an iterative approach (e.g., with a stack) to avoid recursion depth limitations.

Trees with only one node each, but different values

How to Handle:

The root value comparison will immediately detect the difference, returning false.

Trees with only one node each, and the same values

How to Handle:

The root value comparison will confirm equality, and since no further nodes exist, it returns true.

Trees with negative, zero, and positive integer values in their nodes

How to Handle:

The standard integer comparison will handle all these value types correctly without special treatment.

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:

Can the binary tree nodes contain any data type, or are they specifically integers?
What is the range of possible values for the node values?
Can either `p` or `q` be null or empty trees, and how should that be handled?
By 'structurally identical', do you mean the trees must have the exact same shape, including the placement of null nodes?
Should the function return `true` or `false` (or some other value) if both input trees are null?

Brute Force Solution

Approach

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

First, check if both trees are completely empty. If they are, they are the same.
Next, if only one tree is empty while the other is not, they are different.
If both trees have values at their starting points, compare these values. If they're different, the trees are different.
If the starting values are the same, then we must check the left side of both trees in the exact same way. Treat the left sides as if they are smaller trees and start this whole process over.
If the left sides are the same, then we must also check the right side of both trees in the same way. Again, treat the right sides as smaller trees and repeat the whole process.
The trees are considered the same only if every corresponding value and every corresponding structure, from the very top to the very bottom, matches exactly.

Code Implementation

def is_same_tree(tree_one, tree_two):
    # Check if both trees are empty.
    if not tree_one and not tree_two:
        return True

    # Check if only one tree is empty.
    if not tree_one or not tree_two:
        return False

    # Compare the values of the root nodes.
    if tree_one.val != tree_two.val:
        return False

    # Recursively check the left subtrees.
    left_trees_are_same = is_same_tree(tree_one.left, tree_two.left)

    # If left trees aren't the same, overall not the same
    if not left_trees_are_same:
        return False

    # Recursively check the right subtrees.
    right_trees_are_same = is_same_tree(tree_one.right, tree_two.right)

    return right_trees_are_same

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, check if both trees are empty. If they are, then they are the same.
If only one of the trees is empty, they can't be the same, so say they are different.
If both trees have a top part, compare the values of these parts. If they are different, the trees are different.
If the top parts are the same, then we need to check if the left parts of the trees are the same using this exact same process.
Then, we need to check if the right parts of the trees are the same, again using the exact same process.
If the top parts, the left parts, and the right parts are all the same, then the trees are the same.

Code Implementation

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

def is_same_tree(tree_one, tree_two):
    # If both trees are empty, they are identical.
    if not tree_one and not tree_two:
        return True

    # If only one tree is empty, they cannot be identical.
    if not tree_one or not tree_two:
        return False

    # If the values of the current nodes are different, trees differ.
    if tree_one.val != tree_two.val:
        return False

    # Recursively check if the left subtrees are the same.
    left_subtree_is_same = is_same_tree(tree_one.left, tree_two.left)

    # Recursively check if the right subtrees are the same.
    right_subtree_is_same = is_same_tree(tree_one.right, tree_two.right)

    # The trees are the same if both subtrees are the same.
    return left_subtree_is_same and right_subtree_is_same

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both input trees are null	Return true, as two null trees are considered identical.
One tree is null, and the other is not null	Return false, as one tree having nodes while the other is empty means they are different.
Trees have different structures (different shapes), but the same values at corresponding nodes up to a point	The recursive or iterative check will eventually reach differing structural parts, returning false.
Trees have identical structure, but different values at one or more nodes	The value comparison within the recursive/iterative logic will identify the mismatch, returning false.
Large trees exceeding recursion depth limits (stack overflow)	Consider using an iterative approach (e.g., with a stack) to avoid recursion depth limitations.
Trees with only one node each, but different values	The root value comparison will immediately detect the difference, returning false.
Trees with only one node each, and the same values	The root value comparison will confirm equality, and since no further nodes exist, it returns true.
Trees with negative, zero, and positive integer values in their nodes	The standard integer comparison will handle all these value types correctly without special treatment.

Both input trees are null

How to Handle:

Return true, as two null trees are considered identical.

One tree is null, and the other is not null

How to Handle:

Return false, as one tree having nodes while the other is empty means they are different.

Trees have different structures (different shapes), but the same values at corresponding nodes up to a point

How to Handle:

The recursive or iterative check will eventually reach differing structural parts, returning false.

Trees have identical structure, but different values at one or more nodes

How to Handle:

The value comparison within the recursive/iterative logic will identify the mismatch, returning false.

Large trees exceeding recursion depth limits (stack overflow)

How to Handle:

Consider using an iterative approach (e.g., with a stack) to avoid recursion depth limitations.

Trees with only one node each, but different values

How to Handle:

The root value comparison will immediately detect the difference, returning false.

Trees with only one node each, and the same values

How to Handle:

The root value comparison will confirm equality, and since no further nodes exist, it returns true.

Trees with negative, zero, and positive integer values in their nodes

How to Handle:

The standard integer comparison will handle all these value types correctly without special treatment.