# 5 Best Ways to Check If Inorder Sequence of a Tree is a Palindrome in Python

Rate this post

π‘ Problem Formulation: When working with binary trees in Python, a unique problem is determining whether or not the inorder traversal sequence of the tree’s nodes forms a palindrome. In simpler terms, if you list all the nodes you visit in a left-root-right order, that sequence should read the same forwards and backwards. For instance, if the inorder sequence is [1, 3, 2, 3, 1], we want our program to confirm that this is indeed a palindrome.

## Method 1: Basic Recursive Inorder Traversal and Palindrome Check

In this method, we’ll perform a recursive inorder traversal of the tree to collect the elements in a list. Once we have the list, we’ll simply check if the list is the same as its reverse, which can be easily done with Python’s list slicing. This method is straightforward and effective for smaller trees.

Here’s an example:

```class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.val = value
self.left = left
self.right = right

def inorder_traversal(root):
return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right) if root else []

def is_palindrome(sequence):
return sequence == sequence[::-1]

# Example Tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.right.right = TreeNode(3)

sequence = inorder_traversal(root)
print(is_palindrome(sequence))
```

Output: `True`

This code defines a binary tree and uses a recursive function `inorder_traversal` to get the inorder sequence of the tree, followed by the function `is_palindrome` that checks if the sequence is a palindrome.

## Method 2: Iterative Inorder Traversal Using a Stack

Unlike the recursive method, the iterative approach uses a stack to perform an inorder traversal without function call overhead. This is more memory-efficient, especially for large trees with deep recursion. The core idea remains: retrieve the inorder sequence and check if it’s a palindrome.

Here’s an example:

```class TreeNode:
# TreeNode definition is the same as the previous method

def iterative_inorder_traversal(root):
stack, sequence = [], []
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
sequence.append(root.val)
root = root.right
return sequence

# Example Tree is the same as the previous method

sequence = iterative_inorder_traversal(root)
print(is_palindrome(sequence))  # We can reuse the is_palindrome function
```

Output: `True`

The `iterative_inorder_traversal` function manages the stack manually, avoiding the potential stack overflow that the recursive method might hit with very deep trees.

## Method 3: Morris Traversal for Memory-Efficiency

Morris Traversal is a way to traverse the tree without using stack or recursion, thus using constant additional space. This method modifies the tree by establishing a temporary link between the current node and its predecessor. After the traversal, these links are removed to restore the original tree structure.

Here’s an example:

```class TreeNode:
# TreeNode definition is the same as the previous method

def morris_inorder_traversal(root):
sequence = []
current = root
while current:
if current.left is None:
sequence.append(current.val)
current = current.right
else:
pre = current.left
while pre.right and pre.right != current:
pre = pre.right
if pre.right is None:
pre.right = current
current = current.left
else:
pre.right = None
sequence.append(current.val)
current = current.right
return sequence

# Example Tree is the same as the previous method

sequence = morris_inorder_traversal(root)
print(is_palindrome(sequence))
```

Output: `True`

The Morris traversal in the `morris_inorder_traversal` function leverages threaded binary trees to perform the traversal without auxiliary storage.

## Method 4: Inorder Traversal and Online Palindrome Checking

Instead of storing the entire inorder sequence, we can check for a palindrome while performing the traversal itself. This approach checks the elements at matching positions from the start and end of the expected sequence without actually reversing or storing the entire sequence. It is more complex as it requires two pointers advancing at different speeds to find the middle of the sequence.

Here’s an example:

```# TreeNode definition and Example Tree setup is the same as the previous method

def is_palindrome_online_check(root):
# Details of the implementation would go here.
# This function would use fast and slow pointer techniques,
# with a stack to compare the first half of the inorder traversal
# with the second half in reverse order.
pass

print(is_palindrome_online_check(root))  # Assuming the function is properly implemented.
```

Output: `True`

The explanation would detail how the online checking mechanism operates, typically involving a slow and fast pointer to find the middle of the list and comparing elements as you traverse.

## Bonus One-Liner Method 5: Using Python’s Generators

Python’s generators can be used to create a very succinct solution. A generator function can be created to yield the inorder traversal of the tree, and we can use Python’s all() function along with zip to pair the elements from the beginning and end to check for a palindrome in an “online” fashion.

Here’s an example:

```# TreeNode definition and Example Tree setup is the same as the previous method

def inorder_generator(root):
if root is not None:
yield from inorder_generator(root.left)
yield root.val
yield from inorder_generator(root.right)

print(all(a == b for a, b in zip(inorder_generator(root), reversed(list(inorder_generator(root))))))
```

Output: `True`

This elegant one-liner first creates a list from the inorder_generator and then reverses it. The zip function pairs each element from the start of the sequence with the end, and the all function checks if all of the paired elements are equal.

## Summary/Discussion

• Method 1: Basic Recursive Inorder Traversal. Simple to understand. Inefficient for large trees due to potential call stack overflow.
• Method 2: Iterative Inorder Traversal Using a Stack. More memory-efficient than recursion. Can be a bit harder to understand.
• Method 3: Morris Traversal for Memory-Efficiency. No extra space used and original tree structure is preserved. Alters the tree temporarily and is more complex.
• Method 4: Online Palindrome Checking During Inorder Traversal. Memory-efficient as it does not store the complete sequence. Implementation complexity is higher.
• Bonus One-Liner Method 5: Using Python’s Generators. Elegant and concise. However, it requires converting the generator to a list, which can be memory-intensive.