331. Verify Preorder Serialization of a Binary Tree LeetCode Solution

In this guide, you will get 331. Verify Preorder Serialization of a Binary Tree LeetCode Solution with the best time and space complexity. The solution to Verify Preorder Serialization of a Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Verify Preorder Serialization of a Binary Tree solution in C++
  4. Verify Preorder Serialization of a Binary Tree solution in Java
  5. Verify Preorder Serialization of a Binary Tree solution in Python
  6. Additional Resources
331. Verify Preorder Serialization of a Binary Tree LeetCode Solution image

Problem Statement of Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as ‘#’.

For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#”, where ‘#’ represents a null node.
Given a string of comma-separated values preorder, return true if it is a correct preorder traversal serialization of a binary tree.
It is guaranteed that each comma-separated value in the string must be either an integer or a character ‘#’ representing null pointer.
You may assume that the input format is always valid.

For example, it could never contain two consecutive commas, such as “1,,3”.

Note: You are not allowed to reconstruct the tree.

Example 1:
Input: preorder = “9,3,4,#,#,1,#,#,2,#,6,#,#”
Output: true
Example 2:
Input: preorder = “1,#”
Output: false
Example 3:
Input: preorder = “9,#,#,1”
Output: false

See also  65. Valid Number LeetCode Solution

Constraints:

1 <= preorder.length <= 104
preorder consist of integers in the range [0, 100] and '#' separated by commas ','.

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

331. Verify Preorder Serialization of a Binary Tree LeetCode Solution in C++

class Solution {
 public:
  bool isValidSerialization(string preorder) {
    int degree = 1;  // out-degree (children) - in-degree (parent)
    istringstream iss(preorder);

    for (string node; getline(iss, node, ',');) {
      if (--degree < 0)
        return false;
      if (node != "#")
        degree += 2;
    }

    return degree == 0;
  }
};
/* code provided by PROGIEZ */

331. Verify Preorder Serialization of a Binary Tree LeetCode Solution in Java

class Solution {
  public boolean isValidSerialization(String preorder) {
    int degree = 1; // out-degree (children) - in-degree (parent)

    for (final String node : preorder.split(",")) {
      if (--degree < 0) // One parent
        return false;
      if (!node.equals("#"))
        degree += 2; // Two children
    }

    return degree == 0;
  }
}
// code provided by PROGIEZ

331. Verify Preorder Serialization of a Binary Tree LeetCode Solution in Python

class Solution:
  def isValidSerialization(self, preorder: str) -> bool:
    degree = 1  # out-degree (children) - in-degree (parent)

    for node in preorder.split(','):
      degree -= 1
      if degree < 0:
        return False
      if node != '#':
        degree += 2

    return degree == 0
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: