Palindromic Tree

Given a binary tree root where each node contains a digit from 0-9, return whether its in-order traversal is a palindrome.

Bonus: solve in \(\mathcal{O}(h)\) space where h is height of the tree.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

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

Examples

Example 1

Input

• root =

Output

• answer = True

Explanation

The in-order traversal is [1, 5, 9, 5, 1] which is a palindrome

Example 2

Input

• root =

Output

• answer = False

Solution