algoadvance

Leetcode 331. Verify Preorder Serialization of a Binary Tree

Problem Statement

The problem asks us to verify if a given preorder serialization of a binary tree is valid.

The given serialization is a string of comma-separated values where each value could either be an integer or a ‘#’ which denotes a null node.

According to the properties of preorder serialization, the root node appears first, followed by the left subtree, and then the right subtree. The task is to ensure that the given serialization represents a valid binary tree.

Clarifying Questions

  1. Input Format:
    • Is the input guaranteed to be a non-empty string?
    • Can we assume that the input format is strictly compliant with the rules (comma-separated values where each value is either an integer representing a node or ‘#’ representing a null)?
  2. Output Format:
    • What should the function return if the serialization is valid or invalid?
    • Are there specific constraints on the length of the input string?

Assuming reasonable answers to these questions, we can proceed to the strategy.

Strategy

To validate the serialization, we can use the concept of out-degree and in-degree. In a valid binary tree:

The main steps are:

  1. Split the input string by commas.
  2. Use a counter to track the difference between out-degrees and in-degrees (slots).
  3. For every node encountered:
    • Decrease slots by 1 because every node takes a slot.
    • If slots becomes negative any time before the end, it’s invalid.
    • If the node is not ‘#’, it provides two new slots (increase slots by 2).
  4. At the end, slots should be exactly 0.

Code

Here’s the Java code to implement the solution:

public class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        int slots = 1; // Initially, we start with one slot for the root
        
        for (String node : nodes) {
            slots--; // One slot is taken by the current node
            
            if (slots < 0) {
                return false; // If slots become negative, it's invalid
            }
            
            if (!node.equals("#")) {
                slots += 2; // Non-null nodes provide two new slots
            }
        }
        
        return slots == 0;
    }
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string. This is because:

The space complexity is O(n) due to the storage of the split nodes array.

By using this approach, we efficiently determine the validity of the given preorder serialization of a binary tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI