Katkat
Back

Solve Tree Diameter and Palindromic Counts

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to perform recursive depth-first searches on binary trees and efficient string manipulation to count palindromic subsequences or paths.

Part 1: Binary Tree Diameter

Given the root of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them.

Function Signature

def diameterOfBinaryTree(root: Optional[TreeNode]) -> int:

Example

Input: root = [1, 2, 3, 4, 5] Output: 3 Explanation: The longest path is [4, 2, 1, 3] or [5, 2, 1, 3], which has 3 edges.

Part 2: Palindromic Substrings

Given a string s, return the number of palindromic substrings in s. A string is a palindrome if it reads the same forward and backward. A substring is a contiguous sequence of characters within the string.

Function Signature

def countSubstrings(s: str) -> int:

Example

Input: s = "aaa" Output: 6 Explanation: The palindromic substrings are "a", "a", "a", "aa", "aa", "aaa".

Constraints

  • Tree nodes are in the range [1, 10^4].
  • The length of s is between 1 and 1000.
  • You should aim for O(n) time complexity for the tree problem and O(n^2) for the string problem.

Hints

Hint 1

For the tree diameter, consider a helper function that returns the height of a subtree while updating a global variable for the diameter.

Hint 2

For the palindromic substrings, consider using the 'expand around center' approach for every character or pair of adjacent characters as a potential palindrome center.

Hint 3

Ensure you handle the difference between even-length palindromes (centered between characters) and odd-length palindromes (centered on a character) in your counting logic.

Follow-up questions

  • How would you modify the tree diameter algorithm to find the longest path that specifically must pass through the root node?
  • Can you solve the palindromic substrings problem in O(n) time using Manacher's Algorithm?
  • If the binary tree were instead a general N-ary tree, how would the diameter calculation change?