Problem statement

https://binarysearch.com/problems/Palindromic-Tree/

Solution

O(n) space complexity solution is easy. If we want to have O(h) space complexity, let us use inorder traversal and reversed inorder traversal in the way of generators and then compare element by element.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def solve(self, root):
        def inorder1(node):
            if not node: return
            yield from inorder1(node.left)
            yield node.val
            yield from inorder1(node.right)

        def inorder2(node):
            if not node: return
            yield from inorder2(node.right)
            yield node.val
            yield from inorder2(node.left)

        return all(a1 == a2 for a1, a2 in zip(inorder1(root), inorder2(root)))