5 Best Ways to Check If All Values in a Python Tree Are the Same

Rate this post

πŸ’‘ Problem Formulation: You have a tree data structure in Python, where each node contains a value. The task is to create a program that checks if every node in the tree has the same value. For example, if every node in a given binary tree has a value of 4, the program should return True; otherwise, it should return False if there’s at least one node with a different value.

Method 1: Recursive Tree Traversal

The recursive tree traversal method involves writing a recursive function that compares the value of the current node to a reference value (usually the value of the root node) and returns False as soon as a discrepancy is found. This method is efficient because it stops the comparison as soon as a difference is detected without traversing the entire tree if not needed.

Here’s an example:

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

def is_unival_tree(root):
    def check_value(node, val):
        if not node:
            return True
        if node.val != val:
            return False
        return check_value(node.left, val) and check_value(node.right, val)
    
    return check_value(root, root.val) if root else True

# Example Tree: All nodes have value 4
root = TreeNode(4)
root.left = TreeNode(4)
root.right = TreeNode(4)

print(is_unival_tree(root))

Output:

True

The function is_unival_tree() checks whether all nodes’ values in the tree are equal to the root’s value. It does so by using the helper function check_value(), which recursively traverses the tree and compares each node value to the root’s value. If all values match, True is returned; otherwise, False is returned.

Method 2: Iterative Depth-First Search

Iterative depth-first search uses a stack to traverse the tree nodes. Similar to the recursive method, it compares the value of each visited node to the value of the root node. The iterative approach is helpful when avoiding the possibility of stack overflow in languages with limited recursion depth.

Here’s an example:

def is_unival_tree_iterative(root):
    if not root:
        return True
    stack = [root]
    value_to_compare = root.val
    while stack:
        node = stack.pop()
        if node.val != value_to_compare:
            return False
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return True

# Reusing the TreeNode class and 'root' from the previous example
print(is_unival_tree_iterative(root))

Output:

True

The function is_unival_tree_iterative() iteratively traverses the tree using depth-first search. It maintains a stack of nodes to visit, and compares each node’s value with the root node’s value. If any node’s value doesn’t match, it returns False; otherwise, after fully traversing the tree without finding a discrepancy, it returns True.

Method 3: Breadth-First Search

The breadth-first search method uses a queue to check each level of the tree systematically. It verifies that each node matches the value of the root node until no more nodes are left in the queue. This approach can be useful when working with very deep trees.

Here’s an example:

from collections import deque

def is_unival_tree_bfs(root):
    if not root:
        return True
    queue = deque([root])
    value_to_compare = root.val
    while queue:
        node = queue.popleft()
        if node.val != value_to_compare:
            return False
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return True

# Reusing the TreeNode class and 'root' from the previous examples
print(is_unival_tree_bfs(root))

Output:

True

The function is_unival_tree_bfs() checks for univalued trees leveraging breadth-first search. It enqueues nodes for traversal and systematically compares them against the root’s value. Once all nodes are assessed without finding a different value, the function concludes all tree values are the same.

Method 4: Leveraging Set Uniqueness

This method uses a set to keep track of unique values encountered during a tree traversal. Since sets automatically handle duplication, if the set size is more than one after traversal, then the tree has different values.

Here’s an example:

def is_unival_tree_set(root):
    unique_values = set()

    def traverse(node):
        if node:
            unique_values.add(node.val)
            traverse(node.left)
            traverse(node.right)

    traverse(root)
    return len(unique_values) == 1

# Reusing the TreeNode class and 'root' from the previous examples
print(is_unival_tree_set(root))

Output:

True

The function is_unival_tree_set() traverses the tree while adding each node’s value to a set. Having finished traversal, if the set only contains one value, then all nodes in the tree have the same value, returning True; otherwise False.

Bonus One-Liner Method 5: Set Comprehension

With set comprehension combined with generator expressions, we can create a one-liner function that traverses the tree and adds values to a set in one go. This method is concise but may not offer the best performance due to lack of early stopping.

Here’s an example:

def is_unival_tree_one_liner(root):
    return len({node.val for node in gen_tree_nodes(root)}) == 1

def gen_tree_nodes(node):
    if node:
        yield node
        yield from gen_tree_nodes(node.left)
        yield from gen_tree_nodes(node.right)

# Reusing the TreeNode class and 'root' from the previous examples
print(is_unival_tree_one_liner(root))

Output:

True

Using a generator function gen_tree_nodes() in set comprehension within is_unival_tree_one_liner(), all tree values are placed in a set. If all values are the same, the set’s length will be one, indicating a univalued tree.

Summary/Discussion

  • Method 1: Recursive Tree Traversal. Utilizes recursion for elegant code. Offers early termination on finding a different value. Not suitable for very deep trees due to potential stack overflow.
  • Method 2: Iterative Depth-First Search. Iterative approach. Good for deep trees. Requires managing a stack manually, which can be more cumbersome than recursion for some.
  • Method 3: Breadth-First Search. Interrogates trees level by level. Well-suited for wide as opposed to deep trees. May consume more memory due to queueing all nodes at the largest level.
  • Method 4: Leveraging Set Uniqueness. Simple and intuitive logic. Uses additional memory to store unique values. The whole tree must be traversed even if it’s determined not to be univalued early on.
  • Method 5: Set Comprehension. Concise one-liner method. No early termination is available, potentially less efficient than the other methods due to full traversal.