Jobs

Interviews

Discussions

Univalued Binary Tree #2 Most Asked

Easy

Twilio

6 views

Topics:

TreesRecursion

A binary tree is uni-valued if every node in the tree has the same value.

Given the root of a binary tree, return true if the given tree is uni-valued, or false otherwise.

Example 1:

Input: root = [1,1,1,1,1,null,1]
Output: true

Example 2:

Input: root = [2,2,2,5,2]
Output: false

Constraints:

The number of nodes in the tree is in the range [1, 100].
0 <= Node.val < 100

Try coding it in LeetCode

Univalued Binary Tree #2 Most Asked

Easy

Twilio

6 views

Topics:

TreesRecursion

A binary tree is uni-valued if every node in the tree has the same value.

Given the root of a binary tree, return true if the given tree is uni-valued, or false otherwise.

Example 1:

Input: root = [1,1,1,1,1,null,1]
Output: true

Example 2:

Input: root = [2,2,2,5,2]
Output: false

Constraints:

The number of nodes in the tree is in the range [1, 100].
0 <= Node.val < 100

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 be empty (null)?
What is the range of values for the nodes in the tree?
If the tree is null, should I return true or false?
Does 'univalued' mean that *all* nodes must have the same value, or just that each subtree must have a single value throughout?
Is the TreeNode data type a standard binary tree node with left and right children?

Brute Force Solution

Approach

The brute force approach to checking if a tree is univalued involves looking at every single node in the tree. We essentially compare each node's value with the value of the root node to make sure they all match.

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

First, look at the very top node, which we can call the root node, and remember its value.
Next, look at every other node in the tree, one by one.
For each node, compare its value to the value of the root node we remembered.
If you find even a single node whose value is different from the root node's value, you know the tree is not univalued, and you can stop checking.
If you go through every single node in the tree and each one has the same value as the root node, then you know the entire tree is univalued.

Code Implementation

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

def is_univalued_binary_tree_brute_force(root):
    if not root:
        return True

    root_value = root.value

    def is_univalued(node):
        if not node:
            return True

        # If current node's value differs, tree is not univalued.
        if node.value != root_value:
            return False

        # Recursively check the left and right subtrees
        return is_univalued(node.left) and is_univalued(node.right)

    return is_univalued(root)

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary tree once to compare its value with the root node's value. The input size, n, represents the number of nodes in the tree. Therefore, the time complexity is directly proportional to the number of nodes visited. Thus, the algorithm performs approximately n operations, which simplifies to O(n).

Space Complexity

O(1) – The provided algorithm only stores the root node's value for comparison. No additional data structures like arrays, hash maps, or lists are created. The space used is constant regardless of the number of nodes (N) in the binary tree. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The task is to check if all nodes in a tree have the same value. The fastest way is to start at the root and then check if all the other nodes match the root's value. We can do this recursively.

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

First, determine the value of the root node.
Then, check if the left side of the tree exists. If it does, ensure all nodes in the left side have the same value as the root. If not, the tree is not univalued.
Similarly, check if the right side of the tree exists. If it does, ensure all nodes in the right side have the same value as the root. If not, the tree is not univalued.
If both left and right sides (when present) are univalued and have the same value as the root, then the entire tree is univalued.

Code Implementation

def is_unival_tree(root):
    if not root:
        return True

    root_value = root.val

    def is_unival(node, value):
        if not node:
            return True

        if node.val != value:
            return False

        return is_unival(node.left, value) and is_unival(node.right, value)

    # Check if the left subtree exists
    if root.left:
        if not is_unival(root.left, root_value):
            return False

    # Check if the right subtree exists
    if root.right:
        if not is_unival(root.right, root_value):
            return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node of the binary tree exactly once to compare its value with the root's value. The input size 'n' represents the number of nodes in the tree. In the worst-case scenario, the algorithm traverses all 'n' nodes. Therefore, the time complexity is directly proportional to the number of nodes, resulting in O(n) time complexity.

Space Complexity

O(H) – The algorithm employs a recursive approach to traverse the binary tree. In the worst-case scenario, the recursion depth can be equal to the height (H) of the tree, leading to H function calls on the call stack. Each recursive call consumes a constant amount of space for storing local variables and return addresses. Therefore, the auxiliary space complexity is proportional to the height of the tree, which is O(H). In the worst case for a skewed tree H can equal N the number of nodes.

Edge Cases

Case	How to Handle
Null root node	Return true because an empty tree is trivially univalued.
Single node tree	Return true, as a single node tree is always univalued.
Tree with all nodes having the same value	The algorithm should correctly return true since all nodes have equal values.
Tree with a different value at the root but all other nodes matching	The algorithm should return false as the root value differs from other nodes.
Deeply skewed tree (e.g., only left or right children)	Ensure the recursive calls do not cause a stack overflow for extreme depths.
Tree with a large number of nodes	Ensure the algorithm scales efficiently (O(n)) and doesn't have unnecessary overhead.
Integer overflow in node values (if applicable depending on language)	Consider using a larger data type if the problem specifies a range that could cause overflow.
Values in left subtree are equal, but the values in right subtree differ from left subtree's value	The algorithm should correctly return false since not all nodes have equal values.

Null root node

How to Handle:

Return true because an empty tree is trivially univalued.

Single node tree

How to Handle:

Return true, as a single node tree is always univalued.

Tree with all nodes having the same value

How to Handle:

The algorithm should correctly return true since all nodes have equal values.

Tree with a different value at the root but all other nodes matching

How to Handle:

The algorithm should return false as the root value differs from other nodes.

Deeply skewed tree (e.g., only left or right children)

How to Handle:

Ensure the recursive calls do not cause a stack overflow for extreme depths.

Tree with a large number of nodes

How to Handle:

Ensure the algorithm scales efficiently (O(n)) and doesn't have unnecessary overhead.

Integer overflow in node values (if applicable depending on language)

How to Handle:

Consider using a larger data type if the problem specifies a range that could cause overflow.

Values in left subtree are equal, but the values in right subtree differ from left subtree's value

How to Handle:

The algorithm should correctly return false since not all nodes have equal values.

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 be empty (null)?
What is the range of values for the nodes in the tree?
If the tree is null, should I return true or false?
Does 'univalued' mean that *all* nodes must have the same value, or just that each subtree must have a single value throughout?
Is the TreeNode data type a standard binary tree node with left and right children?

Brute Force Solution

Approach

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

First, look at the very top node, which we can call the root node, and remember its value.
Next, look at every other node in the tree, one by one.
For each node, compare its value to the value of the root node we remembered.
If you find even a single node whose value is different from the root node's value, you know the tree is not univalued, and you can stop checking.
If you go through every single node in the tree and each one has the same value as the root node, then you know the entire tree is univalued.

Code Implementation

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

def is_univalued_binary_tree_brute_force(root):
    if not root:
        return True

    root_value = root.value

    def is_univalued(node):
        if not node:
            return True

        # If current node's value differs, tree is not univalued.
        if node.value != root_value:
            return False

        # Recursively check the left and right subtrees
        return is_univalued(node.left) and is_univalued(node.right)

    return is_univalued(root)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The task is to check if all nodes in a tree have the same value. The fastest way is to start at the root and then check if all the other nodes match the root's value. We can do this recursively.

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

First, determine the value of the root node.
Then, check if the left side of the tree exists. If it does, ensure all nodes in the left side have the same value as the root. If not, the tree is not univalued.
Similarly, check if the right side of the tree exists. If it does, ensure all nodes in the right side have the same value as the root. If not, the tree is not univalued.
If both left and right sides (when present) are univalued and have the same value as the root, then the entire tree is univalued.

Code Implementation

def is_unival_tree(root):
    if not root:
        return True

    root_value = root.val

    def is_unival(node, value):
        if not node:
            return True

        if node.val != value:
            return False

        return is_unival(node.left, value) and is_unival(node.right, value)

    # Check if the left subtree exists
    if root.left:
        if not is_unival(root.left, root_value):
            return False

    # Check if the right subtree exists
    if root.right:
        if not is_unival(root.right, root_value):
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root node	Return true because an empty tree is trivially univalued.
Single node tree	Return true, as a single node tree is always univalued.
Tree with all nodes having the same value	The algorithm should correctly return true since all nodes have equal values.
Tree with a different value at the root but all other nodes matching	The algorithm should return false as the root value differs from other nodes.
Deeply skewed tree (e.g., only left or right children)	Ensure the recursive calls do not cause a stack overflow for extreme depths.
Tree with a large number of nodes	Ensure the algorithm scales efficiently (O(n)) and doesn't have unnecessary overhead.
Integer overflow in node values (if applicable depending on language)	Consider using a larger data type if the problem specifies a range that could cause overflow.
Values in left subtree are equal, but the values in right subtree differ from left subtree's value	The algorithm should correctly return false since not all nodes have equal values.

Null root node

How to Handle:

Return true because an empty tree is trivially univalued.

Single node tree

How to Handle:

Return true, as a single node tree is always univalued.

Tree with all nodes having the same value

How to Handle:

The algorithm should correctly return true since all nodes have equal values.

Tree with a different value at the root but all other nodes matching

How to Handle:

The algorithm should return false as the root value differs from other nodes.

Deeply skewed tree (e.g., only left or right children)

How to Handle:

Ensure the recursive calls do not cause a stack overflow for extreme depths.

Tree with a large number of nodes

How to Handle:

Ensure the algorithm scales efficiently (O(n)) and doesn't have unnecessary overhead.

Integer overflow in node values (if applicable depending on language)

How to Handle:

Consider using a larger data type if the problem specifies a range that could cause overflow.

Values in left subtree are equal, but the values in right subtree differ from left subtree's value

How to Handle:

The algorithm should correctly return false since not all nodes have equal values.

0/0 Twilio questions completed

0/0 completed