How do I check if all the elements of a nested list tree are identical?

user_13633196 0
Viewed 343

I am trying to create a function allsametree(tree) that takes a list, tree, as an input and returns TRUE or FALSE if all the elements of the list are numerically identical. So far, I have the following function:

def allsametree(tree):
    if not type(tree) == list:
        return tree
    if type(tree) is list:
        final_lst = []
        for item in tree:
            final_lst.append(allsametree(item))
        return final_lst[1:] == final_lst[:-1]

While for the most part, this function works, it runs into an issue when evaluating allsametree([1, [[[[[2]]]]]])

Any tips, or alternative ways you would approach this problem?

recursion python-3.x python
2 Answers

You can recursively convert the list to a set of items and return true if the length of the overall set is 1:

def allsametree(tree):
    def to_set(tree):
        if isinstance(tree, list):
            return {item for obj in tree for item in to_set(obj)}
        return {tree}
    return len(to_set(tree)) == 1
user_68909120

Another way to do it. Split it into two operations a flatten and a check that all the values are the same.

The flatten will convert a nested iterable into one of a single dimension. So [1, [[[[[2]]]]]] becomes [1,2].

Then read the first value and cycle through the rest to check they are the same as it.

Here's the code

from collections.abc import Iterable

def flatten(iterable):
    for i in iterable:
        if isinstance(i, Iterable):
            yield from flatten(i)
        else:
            yield i


def allsametree(tree):
    flat = flatten(tree)
    iterator = iter(flat)
    try:
        first = next(iterator)
    except StopIteration:
        return True
    return all(first == rest for rest in iterator)

This will work for any iterable not just lists and because it uses lazy evaluation, it will stop when it finds two values that are not equal. This saves you from doing unnecessary work. It also avoid instantiating temporary collections (lists, sets etc.) being constructed on each recursive call.

Here's a few test inputs.

user_15404680
Related