**π‘ 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.

Emily Rosemary Collins is a tech enthusiast with a strong background in computer science, always staying up-to-date with the latest trends and innovations. Apart from her love for technology, Emily enjoys exploring the great outdoors, participating in local community events, and dedicating her free time to painting and photography. Her interests and passion for personal growth make her an engaging conversationalist and a reliable source of knowledge in the ever-evolving world of technology.