Solve palindrome-check and vertical-order traversal

You are asked to solve two separate coding questions. You do not need to run code; be prepared to explain your approach and walk through examples.

Question 1: Near-palindrome with one deletion

Given a string s, determine whether it can become a palindrome after deleting at most one character.

• Input: a string s (consisting of lowercase English letters)
• Output: true if s can be made a palindrome by removing 0 or 1 character; otherwise false
• Constraints (typical): 1 <= len(s) <= 1e5

Example:

• s = "abca" → true (delete 'b' or 'c' )
• s = "abc" → false

Question 2: Binary tree vertical order traversal

Given the root of a binary tree, return its vertical order traversal.

Define a node’s column as follows:

• Root is at column 0
• Left child is column col - 1
• Right child is column col + 1

Return a list of columns from leftmost to rightmost. Within each column, list nodes in top-to-bottom order. If multiple nodes share the same row and column, order them in the same order they would appear in a level-order (BFS) traversal from left to right.

• Input: root of a binary tree
• Output: List[List[int]] (values grouped by column)
• Constraints (typical): up to 1e4 – 1e5 nodes

Example: For the tree:

• 3 as root
• left child 9 , right child 8
• 9 has children 4 and 0
• 8 has children 1 and 7

Vertical order output:

• [[4], [9], [3, 0, 1], [8], [7]]

Explain your algorithm and its time/space complexity.