Palindromes in 3 data structures
Hey guys! This is my first article, so let me know how you guys like it! I will be using JavaScript, but feel free to follow along in your language of choice.
A palindrome is defined as, “a word, phrase, or sequence that reads the same backward as forward…” (Oxford Languages). Great, I think that definition does justice! So… how can one represent a palindrome in 3 different data structures?
For simplicity, we will use just 3 different data structures (array, list and binary tree).
An array can easily be represented as a list with invertibility:
As for a linked list, we can just view our list in a linear way:
As for binary trees, we are going to have to say bye to hannah:
This one might be a little harder to think about. However, if you imagine squashing down our tree, you can see the symmetry.
Now that you guys have seem the visualizations, let’s get coding!
As for the array palindrome, we remember that any index has a mirror on the other side. A nice way of implementing this would be using the 2-pointer (or n-pointer) approach and walk two pointers inward until symmetry broke or we finished looking at the array:
The code above benefits from the O(n) and O(1) respective time and space complexity from the 2-pointer approach.
Now for the linked list. We cannot randomly access elements, so just using the 2-pointer approach would not work. We could encode it to any array and then run isPalindrome, but that would entail O(n) space complexity. Google does not like O(n) space complexity, so we will try and find a lower order. Let’s recall our earlier list:
If you try and imagine flipping the first half of a list over the first half so that it is backwards, we get N-A-H-N-A-H-null. Woah! That looks a lot like a linked list cycle. Guess what? 2-pointer approach. This will be a little more involved, as we need to find where to place our first and second pointer, which we will also find by the 2-pointer approach (and fast pointer approach).
Implementing this:
I assumed you guys know how to reverse a linked list. If enough of you guys do not know how, I will make another article visualizing that.
2 down, 1 to go!
So the binary tree is a little bit more to think about, but it will come out with a lot cleaner of a solution. Let us recall our tree again:
What can we notice? This definitely has symmetry. If we look at the root’s left and right children, we can see that their values are equal. Likewise for the left child’s left subtree and the right child’s right subtree. Finally we can notice that the left child’s right subtree matches the right child’s left subtree. If we take the recursive leap of faith, we can generalize this quite concisely.
Along with these and implementation details, we can come up with this:
I hope you guys liked this article! Like I said, I will put up reversing a linked list as well as continue with algorithms problems. Thanks for reading and have a great week!
