331. Verify Preorder Serialization of a Binary Tree

Problem Description

The given problem revolves around the concept of serialization of a binary tree using preorder traversal. Preorder traversal means to visit the root node first, then the left subtree, and finally the right subtree. When serializing a tree, each non-null node is represented by its integer value, and null nodes are represented by a sentinel value '#'.

For instance, a binary tree may be serialized into a string representing the order in which nodes are visited. Notably, null child pointers are also serialized, which creates a unique representation for the structure of the original tree. The challenge here is to determine if a given string preorder, which contains comma-separated integer values and '#' symbols, is a valid serialization of a binary tree, without actually reconstructing the tree.

A valid preorder serialization must satisfy the requirements of a binary tree structure. Each node should have two children (which can be null), and the string should represent a tree where every node has been visited correctly in preorder, including null children.

Intuition

The intuition behind the solution is to simulate the traversal of a binary tree using a stack to keep track of the nodes being visited. As we iterate through the preorder string, each value can be seen as an action in this simulated traversal.

When we hit a non-null node (an integer), we push it onto the stack since it represents a node that could have left and right children. Conversely, when encountering a null node (represented by '#'), we consider it as closing off a path in the tree (i.e., marking a leaf node).

However, a valid serialized binary tree cannot have two consecutive null nodes without them being the right and left children of some node before them. So if we have two null nodes on the top of the stack, there must be an integer just below them representing their parent node. We perform a check, and if that pattern is found, we remove (pop) the two nulls and the integer, simulating that we visited a complete subtree. We then replace them with a single null value on the stack to indicate that the entire subtree is now closed off and treated as a leaf.

We repeat this process as we move through the string. If the serialization is correct, we should end up with one single null value in the stack, which signifies the end of the traversal of a well-formed tree. On the contrary, if we're left with a different pattern, the serialization is deemed incorrect.

Learn more about Stack, Tree and Binary Tree patterns.

Solution Approach

The provided Python code uses a stack to simulate the traversal of a binary tree during deserialization. The algorithm employs a for loop to iterate over nodes represented in the preorder serialization string split by commas. It pushes each value onto the stack, which not only represents inserting nodes but also helps to track the tree structure.

During this simulated traversal, the code looks for a specific pattern in the stack. This pattern comprises two consecutive '#' characters, representing null nodes or leaf nodes, followed by an integer, which would represent their parent node in a binary tree.

When this pattern is detected (stk[-1] == stk[-2] == "#" and stk[-3] != "#") it indicates that we've completed the visit to a subtree - specifically, the left and right children are both null, and we have their parent node just before these nulls.

At this point, the algorithm removes the three entries (stk = stk[:-3]) and replaces them with a single '#' to represent the whole subtree as a null or leaf for any higher-level nodes that might be present in the stack. This action effectively rolls up the null children into their parent, making it into a new leaf node.

Ultimately, if the preorder string represents a valid serialization of a binary tree, we'll end up with exactly one element in the stack after processing the entire input (len(stk) == 1). This remaining element must be the sentinel value '#' indicating that all nodes have been accounted for, and the full tree has been traversed (stk[0] == "#") without reconstructing it. If these conditions are met, the function returns True. Otherwise, if the stack does not adhere to this pattern, the function returns False, signaling that the given preorder serialization is not valid.

The solution is elegant as it simulates traversal without the overhead of tree construction and cleverly handles the serialization pattern-check using a stack that reflects the current state of the traversal process.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Suppose we have a given preorder serialization string of a binary tree: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#". This serialization suggests that we have a tree with the root node value 9, a left child 3, which itself has a left child 4 that has no children (indicated by two consecutive # symbols), a right child 1 with no children, and finally a right child of the root, 2, which has a left child 6 with no children.

Initialize an empty stack stk.
Split the preorder serialization by commas and iterate through the values:
- For the first value 9, push it onto stk: stk = [9].
- The next value 3 goes onto the stack: stk = [9, 3].
- Then, 4 is pushed: stk = [9, 3, 4].
- A '#' is encountered, indicating a null child: stk = [9, 3, 4, '#'].
- Another '#' is encountered, so now we have two null children, which means 4 is a leaf node. We pop three times, and push a '#': stk = [9, 3, '#'].
- We encounter 1 and push it onto the stack: stk = [9, 3, '#', 1].
- Again, two '#' symbols follow, indicating that 1 is a leaf node. Pop three and push '#': stk = [9, '#', '#'].
At this point, we have two '#' characters at the top of the stack, which suggests that the left and right children of 9 have been completely visited. We pop three and replace them with a '#': stk = ['#'].
Now, 2 enters the stack: stk = ['#', 2]. This is not correct as we have finished the tree rooted at 9 and should not add more nodes at the same level.
As we continue, we encounter 6 and the subsequent '#' symbols indicating its children, which after the process will result in a stk = ['#', '#' ], which is not a valid serialization as we are left with two sentinel values.

The correct result, in this case, should be the function returning False, which indicates that preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#" is not a valid preorder serialization of a binary tree. If the serialization was valid, after processing all elements, the stack would have ended up with exactly one '#', reflecting the traversal of the entire tree.

Solution Implementation

1class Solution:
2    def isValidSerialization(self, preorder: str) -> bool:
3        # Initialize an empty stack to keep track of the nodes
4        stack = []
5      
6        # Split the input string by commas to process each tree node
7        for node in preorder.split(","):
8            # Append the current node onto the stack
9            stack.append(node)
10          
11            # While there are at least three elements in the stack,
12            # and the last two are "#" which denotes null nodes,
13            # and the one before them is not "#",
14            # It means we have completed a subtree with a valid leaf node.
15            while len(stack) >= 3 and stack[-1] == "#" and stack[-2] == "#" and stack[-3] != "#":
16                # Remove the last two "#" and the parent node which was before them
17                stack.pop()  # Remove first '#'
18                stack.pop()  # Remove second '#'
19                stack.pop()  # Remove the parent non-null node
20              
21                # Append "#" to represent the completed subtree
22                stack.append("#")
23      
24        # If only one element is left in the stack and it's "#",
25        # it means the entire tree is accurately represented by the serialization,
26        # so it is a valid serialization
27        return len(stack) == 1 and stack[0] == "#"
28

1class Solution {
2
3    // Method to validate if the preorder serialization of a binary tree is correct
4    public boolean isValidSerialization(String preorder) {
5        // Use a stack represented by a list to keep track of tree nodes.
6        List<String> stack = new ArrayList<>();
7      
8        // Split the input string by commas to work with each node/leaf individually.
9        String[] nodes = preorder.split(",");
10        for (String node : nodes) {
11            // Push the current node onto the stack.
12            stack.add(node);
13          
14            // Check the last three elements in the stack if they form a pattern of two 
15            // consecutive '#' symbols which denote null children followed by a numeric node.
16            while (stack.size() >= 3 && stack.get(stack.size() - 1).equals("#")
17                && stack.get(stack.size() - 2).equals("#") && !stack.get(stack.size() - 3).equals("#")) {
18              
19                // Since the last two '#' symbols represent the null children of the previous numeric
20                // node, we can remove them all mimicking the null leaves falling off,
21                // which means they don't take up space in serialization.
22                stack.remove(stack.size() - 1); // Remove last null child
23                stack.remove(stack.size() - 1); // Remove second last null child
24                stack.remove(stack.size() - 1); // Remove parent node
25              
26                // After removing a parent node and its two null children, 
27                // we add one '#' to the stack to indicate that the subtree has been fully traversed.
28                stack.add("#");
29            }
30        }
31      
32        // After processing all nodes, a valid serialization will end up with only one element in the stack,
33        // which must be '#', representing that all nodes have been matched with their children.
34        return stack.size() == 1 && stack.get(0).equals("#");
35    }
36}
37

1#include <sstream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7    // Function to check if the given preorder traversal string of a binary tree
8    // represents a valid serialization of a binary tree.
9    bool isValidSerialization(std::string preorder) {
10        std::vector<std::string> stack;
11        std::stringstream ss(preorder); // Using stringstream to parse the string
12        std::string node;
13
14        // Splitting the input string by commas and processing each node
15        while (getline(ss, node, ',')) {
16            stack.push_back(node); // Push the current node onto the stack
17
18            // Check if the last three elements on the stack are two "#"
19            // followed by a non-#" node, which represents a valid subtree
20            while (stack.size() >= 3 && stack[stack.size() - 1] == "#" && 
21                   stack[stack.size() - 2] == "#" && stack[stack.size() - 3] != "#") {
22                // Pop the two "#" nodes representing null children
23                stack.pop_back(); // Remove right null child
24                stack.pop_back(); // Remove left null child
25              
26                // Pop the parent node of the null children
27                stack.pop_back();
28
29                // The complete subtree is replaced by "#", which signifies that
30                // this part of the tree is properly serialized
31                stack.push_back("#");
32            }
33        }
34
35        // If the stack contains only one element and it is "#", then it is a valid serialization
36        return stack.size() == 1 && stack[0] == "#";
37    }
38};
39

1function isValidSerialization(preorder: string): boolean {
2    let stack: string[] = []; // Initialize stack as an array of strings
3    const nodes = preorder.split(','); // Split the string by commas to process nodes individually
4
5    for (let node of nodes) {
6        stack.push(node); // Push the current node onto the stack
7
8        // Keep reducing the nodes that form a complete subtree into one '#'
9        while (stack.length >= 3 && 
10               stack[stack.length - 1] === "#" &&
11               stack[stack.length - 2] === "#" &&
12               stack[stack.length - 3] !== "#") {
13          
14            // Here we found a pattern which is two null child nodes followed by a non-null parent node
15            stack.pop(); // Remove right null child
16            stack.pop(); // Remove left null child
17
18            // Pop the parent node of the null children to replace that subtree with a '#'
19            stack.pop(); 
20
21            // Substitute the entire subtree with a single "#" to denote the presence of a valid subtree
22            stack.push("#");
23        }
24    }
25
26    // If at the end there's only one element in the stack and it's '#', it's a correctly serialized tree
27    return stack.length === 1 && stack[0] === "#";
28}
29

Time and Space Complexity

Time Complexity

The given Python code primarily consists of iterating through each character in the preorder string once, which means it operates on each element in linear time. Specifically, the split() function that operates on preorder runs in O(n) time, where n is the length of the input string, since it must visit each character to split the string by commas.

Inside the loop, there is a while loop that could potentially run multiple times for certain stacks. However, each element can be added and removed from the stack at most once. Due to this property, despite the while loop, the overall number of append and subsequently pop operations is still linear with respect to the number of nodes or elements in the preorder sequence.

Consequently, the time complexity of the code is O(n).

Space Complexity

The space complexity is determined by the additional space used which is primarily for the stack (stk). In the worst case, the stack could contain all leaf nodes before it begins replacing them with "#". In a full binary tree, the number of leaf nodes is approximately n/2. Thus, in the worst-case scenario, the space complexity would also be O(n).

However, it should be noted that this space complexity analysis assumes that the input string is not considered as extra space used (as it is usually considered input size). If we were to consider any extra space required for the stack itself, then the space complexity is O(n) as we did above.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don’t know