medium Verify Preorder Serialization of a Binary Tree

Problem Statement

You are given a string called preorder that represents the serialization of a binary tree.

This serialization string is created using a preorder traversal, where each node's value is recorded if it is a non-null node. Otherwise, we record using a sentinel value such as '#'.

The string preorder contains only integers and the character '#', separated by commas. The format is always valid, so there will be no cases like two consecutive commas (e.g., "1,,4").

Return true, if this string is a valid serialization of a binary tree. Otherwise, return false.

Note: Note: You are not allowed to reconstruct the tree.

Examples

1. Example 1:
   • Input: "5,2,#,#,3,1,#,#,#"
   • Expected Output: true
   • Justification: The preorder traversal "5,2,#,#,3,1,#,#,#" represents a valid binary tree. It can be visualized as:

    5
   /
  2
   \
    3
    /
   1

1. Example 2:
   • Input: "7,3,1,#,#,4,#,#,8,#,2,#,#"
   • Expected Output: true
   • Justification: The serialization "7,3,1,#,#,4,#,#,8,#,2,#,#" corresponds to a valid binary tree:

    7
   / \
  3   1
     /
    4
     \
      8
       \
        2

1. Example 3:
   • Input: "1,#,#,2"
   • Expected Output: false
   • Justification: The serialization "1,#,#,2" cannot represent a valid binary tree. After the node 1 and its two null children, there should not be any additional nodes left, but 2 appears, which violates the preorder traversal structure.

Solution

To solve this problem, we start by recognizing that every non-null node in a binary tree requires a slot and provides two additional slots for its children. Meanwhile, a null node ('#') occupies a slot without adding any new slots. We initialize our available slots to 1 for the root node. As we traverse through the preorder string, each comma indicates the end of a node description. We decrement the available slots by one for every node processed. If the processed node is non-null, we add two more slots (since it provides room for two children); if it's null, we simply continue. The algorithm checks whether all slots are used up correctly by the end of the string.

The approach is efficient because it ensures a linear traversal through the input, checking at each step whether any inconsistencies exist in the structure of the binary tree. By the end of the string, if the slots available are exactly zero, then the preorder string is a valid serialization of a binary tree. Otherwise, it is not. This method allows us to validate the input without reconstructing the tree, keeping the solution optimal in both time and space complexity.

Step-by-Step Algorithm

1. Initialize a variable availableSlots to 1. This represents the initial slot required for the root node.
2. Calculate the length of the input string preorder and store it in the variable length.
3. Loop through each character in the preorder string from the first to the second last character:
   • Check if the current character is a comma (,):
     • If true, decrement availableSlots by 1, since processing a node consumes one slot.
     • Check if availableSlots is less than 0:
       • If true, return false immediately since there are not enough slots for the upcoming nodes.
     • If the previous character is not '#', increment availableSlots by 2, indicating that a non-null node was processed, which creates two more slots for its children.
4. Process the last node:
   • If the last character of preorder is '#', decrement availableSlots by 1 since it consumes one slot.
   • If the last character is not '#', increment availableSlots by 1. Here, the last non-null node adds 2 slots and consumes 1 slot. So, we are adding remaining 1 slot only.
5. Check the final count of availableSlots:
   • If availableSlots is 0, return true, indicating a valid serialization.
   • Otherwise, return false.

Algorithm Walkthrough

Let's walk through the input "5,2,#,#,3,1,#,#,#" step-by-step:

1. Initialize availableSlots = 1.
2. Calculate length = 17 (length of the input string).
3. Start loop with i = 0 to i = 16 (excluding the last character for separate processing):
   • i = 0: preorder.charAt(0) = '5', not a comma, continue to the next character.
   • i = 1: preorder.charAt(1) = ',', a comma is found.
     • Decrement availableSlots by 1: availableSlots = 0.
     • Check the previous character preorder.charAt(0) = '5', which is not '#'.
     • Increment availableSlots by 2: availableSlots = 2.
   • i = 2: preorder.charAt(2) = '2', not a comma, continue to the next character.
   • i = 3: preorder.charAt(3) = ',', a comma is found.
     • Decrement availableSlots by 1: availableSlots = 1.
     • Check the previous character preorder.charAt(2) = '2', which is not '#'.
     • Increment availableSlots by 2: availableSlots = 3.
   • i = 4: preorder.charAt(4) = '#', not a comma, continue to the next character.
   • i = 5: preorder.charAt(5) = ',', a comma is found.
     • Decrement availableSlots by 1: availableSlots = 2.
     • Check the previous character preorder.charAt(4) = '#', which is '#', no new slots created.
   • i = 6: preorder.charAt(6) = '#', not a comma, continue to the next character.
   • i = 7: preorder.charAt(7) = ',', a comma is found.
     • Decrement availableSlots by 1: availableSlots = 1.
     • Check the previous character preorder.charAt(6) = '#', which is '#', no new slots created.
   • i = 8: preorder.charAt(8) = '3', not a comma, continue to the next character.
   • i = 9: preorder.charAt(9) = ',', a comma is found.
     • Decrement availableSlots by 1: availableSlots = 0.
     • Check the previous character preorder.charAt(8) = '3', which is not '#'.
     • Increment availableSlots by 2: availableSlots = 2.
   • i = 10: preorder.charAt(10) = '1', not a comma, continue to the next character.
   • i = 11: preorder.charAt(11) = ',', a comma is found.
     • Decrement availableSlots by 1: availableSlots = 1.
     • Check the previous character preorder.charAt(10) = '1', which is not '#'.
     • Increment availableSlots by 2: availableSlots = 3.
   • i = 12: preorder.charAt(12) = '#', not a comma, continue to the next character.
   • i = 13: preorder.charAt(13) = ',', a comma is found.
     • Decrement availableSlots by 1: availableSlots = 2.
     • Check the previous character preorder.charAt(12) = '#', which is '#', no new slots created.
   • i = 14: preorder.charAt(14) = '#', not a comma, continue to the next character.
   • i = 15: preorder.charAt(15) = ',', a comma is found.
     • Decrement availableSlots by 1: availableSlots = 1.
     • Check the previous character preorder.charAt(14) = '#', which is '#', no new slots created.
4. Process the last node:
   • preorder.charAt(16) = '#', decrement availableSlots by 1: availableSlots = 0.
5. Check final slot count: availableSlots is 0, so return true.

By following this step-by-step process, we verify that the serialization "5,2,#,#,3,1,#,#,#" is valid.

Code

public class Solution {
    public boolean isValidSerialization(String preorder) {
        // Initialize the number of available slots for nodes in the binary tree.
        int availableSlots = 1; 

        // Get the length of the input string.
        int length = preorder.length(); 

        // Traverse through each character in the input string.
        for (int i = 0; i < length; ++i) {
            // If a comma is encountered, a new node has been processed.
            if (preorder.charAt(i) == ',') {
                // Decrease the available slots by 1 as the node consumes one slot.
                --availableSlots; 

                // If no slots are available, the serialization is invalid.
                if (availableSlots < 0) return false;

                // If the previous character is not '#', it represents a non-null node,
                // which creates two additional slots for its children.
                if (preorder.charAt(i - 1) != '#') availableSlots += 2; 
            }
        }

        // Process the last node in the input string.
        availableSlots = (preorder.charAt(length - 1) == '#') ? availableSlots - 1 : availableSlots + 1;

        // The serialization is valid if all slots are exactly filled.
        return availableSlots == 0; 
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isValidSerialization("5,2,#,#,3,1,#,#,#")); // true
        System.out.println(solution.isValidSerialization("7,3,1,#,#,4,#,#,8,#,2,#,#")); // true
        System.out.println(solution.isValidSerialization("1,#,#,2")); // false
    }
}

Complexity Analysis

Time Complexity

• The algorithm iterates over each character in the input string exactly once. Therefore, the time complexity is , where n is the length of the input string.

Space Complexity

• The space complexity is since the algorithm only uses a fixed amount of extra space (i.e., a few variables like availableSlots and length) regardless of the size of the input string.