Misc

114. Flatten Binary Tree to Linked List

Medium·

Flatten binary tree to linked list

M

114Flatten Binary Tree to Linked List

4 Approachesclick to switch

1

Sentinel + Preorder

O(n)

O(h)

2

Recursive with Tail Return

O(n)

O(h)

3

Iterative Stack

O(n)

O(h)

4

Morris-like (Space Optimized)

O(n)

O(1)

FIG. FLATTEN BINARY TREE TO LINKED LIST● INTERACTIVE

visualization loads as you reach it

Time

O(n)

• rec visits each of the n nodes exactly once, rewiring curr.right and recursing into left and right.

Space

O(h)

• The recursion stack holds one frame per level, so it grows to the tree's height h (up to n for a fully skewed tree).

class Solution:

def flatten(self, root: Optional[TreeNode]) -> None:

def rec(node):

nonlocal curr

if node:

curr.right = node

curr = curr.right

left, right = curr.left, curr.right

curr.left = curr.right = None

rec(left)

rec(right)

 

sentinel = curr = TreeNode(None)

rec(root)

return sentinel.right

---

234. Palindrome Linked List

Easy·

Palindrome Linked List

M

234Palindrome Linked List

3 Approachesclick to switch

1

Array Approach

O(3n)

O(2n)

2

Recursive Approach

O(n)

O(n)

3

Two Pointers with Reversal (Optimal)

O(2n)

O(1)

FIG. PALINDROME LINKED LIST 2● INTERACTIVE

visualization loads as you reach it

Time

O(3n)

• One O(n) pass to build arr, one O(n) pass for arr[::-1] to build the reversed copy, and one O(n) pass for the == comparison - 3n, where n is the number of nodes.

Space

O(2n)

• arr holds all n node values, and arr[::-1] allocates a second n-length list - 2n.

class Solution:

def isPalindrome(self, head: Optional[ListNode]) -> bool:

arr = []

while head:

arr.append(head.val)

head = head.next

return arr == arr[::-1]

---