binary tree traversal: find longest unique paths

binary-tree-traversal.py

from typing import Optional

'''
     1
   /   \
  2     2
 / \   / \
1   2 4   1

1
 \
  2
 / \
1   1
   /
  4

       1
     /   \
    2     3
   / \   / \
  3   6 3   1
 /         / \
2         5   6
'''

testcases = [
    (1,
        (2,
            (1, None, None),
            (2, None, None)
        ),
        (2,
            (4, None, None),
            (1, None, None)
        )
    ),

    (1,
        None,
        (2,
            (1, None, None),
            (1,
                (4, None, None),
                None
            )
        )
    ),

    (1,
        (2,
            (3,
                (2, None, None),
                None
            ),
            (6, None, None)
        ),
        (3,
            (3, None, None),
            (1,
                (5, None, None),
                (6, None, None)
            )
        )
    )
]

class Tree:
    x: int
    l: Optional['Tree']
    r: Optional['Tree']

    def __init__(self, x, l, r):
        self.x = x
        self.l = Tree(*l) if l else l
        self.r = Tree(*r) if r else r

    def __repr__(self) -> str:
        return f'Tree({self.x}) <{hash(self)}>'  # , {self.l}, {self.r}


def solution(N):
    '''
     Find maximal unique path from the tree root
     Solution is using stack, no recursion
    '''
    maxlen = 0

    path = []
    stack = []
    while True:
        # print(N.x if N else ' ', path)

        if N and N.x not in path:
            stack.append(N)
            path.append(N.x)
            N = N.l
            continue

        if not stack:
            break

        N = stack.pop().r
        if not N or not stack:
            maxlen = max(len(path), maxlen)
            path.pop()

    return maxlen


if __name__ == '__main__':
    for t in testcases:
        T = Tree(*t)

        print(solution(T))