LeetCode 297 Serialize and Deserialize Binary Tree - Example and Complexity Analysis

Serialize 1(2, 3(4, 5)).

Preorder with nulls:

• Visit 1, output "1"
• Left: visit 2, output "2"
  • Left of 2: null, output "null"
  • Right of 2: null, output "null"
• Right: visit 3, output "3"
  • Left: visit 4, output "4,null,null"
  • Right: visit 5, output "5,null,null"

Result: "1,2,null,null,3,4,null,null,5,null,null".

Deserialize: Read "1", create root. Read "2", create left child. Read "null" twice (2's children are null). Read "3", create right child of 1. Continue...

Visit each node once for both operations. $O(n)$ time. Recursion stack and output string: $O(n)$ space.