331. Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order 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 #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

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, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

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".

Example 1:

Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

Example 2:

Input: "1,#"
Output: false

Example 3:

Input: "9,#,#,1"
Output: false

Solution

Approach 1: observe that in a preorder traversal, two consecutive #s means the previous number is a leaf. Use a stack to 'reduce' all leafs and we should be able to clear out the stack.

Approach 2: an extension to the stack based approach -- the numbers doesn't matter, just count the number of available leaf slots.

Approach 3: (this approach goes TLE) a valid preorder serialization can be broken up to 3 parts: the first item being a number, and two subtrees that are both valid preorder serializations (recursion). Can use a cache or dp to speed things up.

Code (Python)

Approach 1:

    def isValidSerialization(self, preorder):
        stack = []
        for node in preorder.split(','):
            stack.append(node)
            # to 'reduce' leaves: when seeing two consecutive #s on stack, pop both and replace the topmost element on the stack with a single #, essentially replacing a leaf with a null value
            while len(stack) >= 3 and stack[-2:] == ['#', '#']:
                if stack[-3] == '#': # a leaf can't have children
                    return False
                stack[-3:] = '#'
        return stack == ['#']

Approach 2:

    def isValidSerialization(self, preorder):
        available_slots = 1
        for node in preorder.split(','):
            if available_slots <= 0:
                return False
            if node != '#':
                available_slots += 1 # the number takes a slot, but increase 2 slots
            else:
                available_slots -= 1 # the pound takes a slot
        return available_slots == 0

Approach 3:

    def isValidSerialization(self, preorder):
        sequence = preorder.split(',')
        cache = {}
        return self._is_valid_preorder(sequence, 0, len(sequence) - 1, cache)

    def _is_valid_preorder(self, sequence, start, end, cache):
        # a leaf node can only be a #, not number
        if start == end:
            return sequence[start] == '#'
        # a root can't be a #
        if sequence[start] == '#':
            return False
        for i in range(start + 1, end):
            if (start + 1, i) not in cache:
                cache[(start + 1, i)] = self._is_valid_preorder(sequence, start + 1, i, cache)
            first_half_valid = cache[(start + 1, i)]
            if (i + 1, end) not in cache:
                cache[(i + 1, end)] = self._is_valid_preorder(sequence, i + 1, end, cache)
            second_half_valid = cache[(i + 1, end)]
            if first_half_valid and second_half_valid:
                return True
        return False

Code (C++)

Approach 1:

// Stack - O(n) space.
class Solution {
public:
    bool isValidSerialization(string preorder) {
        stack<string> st;
        int head = 0;
        int tail = 1;
        while (tail <= preorder.size())
        {
            if (tail == preorder.size() || preorder[tail] == ',')
            {
                string node = preorder.substr(head, tail - head);
                head = tail + 1;
                if (node == "#")
                {
                    while (!st.empty() && st.top() == "#")
                    {
                        st.pop();
                        if (st.empty())
                            return false;
                        st.pop();
                    }
                }
                st.push(node);
            }
            tail++;
        }
        return (st.size() == 1 && st.top() == "#");
    }
};

Approach 2:

// O(1) space.
class Solution {
public:
    bool isValidSerialization(string preorder) {
        int head = 0;
        int tail = 1;
        int open = 1;
        while (tail <= preorder.size())
        {
            if (tail == preorder.size() || preorder[tail] == ',')
            {
                string node = preorder.substr(head, tail - head);
                head = tail + 1;
                if (node == "#")
                    open--;
                else
                    open++;
                if (open == 0 && tail < preorder.size())
                    return false;
            }
            tail++;
        }
        return open == 0;
    }
};

Approach 3:

// Time Limit Exceeded.
class Solution {
public:
    bool isValidSerialization(string preorder) {
        // Retrive all nodes from the string.
        vector<string> nodes;
        int head = 0;
        int tail = 1;
        while (tail <= preorder.size())
        {
            if (tail == preorder.size() || preorder[tail] == ',')
            {
                string node = preorder.substr(head, tail - head);
                head = tail + 1;
                nodes.push_back(node);
            }
            tail++;
        }
        int n = nodes.size();
        bool status[n][n];
        for (int i = 0; i < n; ++i)
        {
            status[i][i] = nodes[i] == "#";
        }
        for (int len = 2; len <= n; ++len)
        {
            for (int tail = n-1; tail - len + 1 >= 0; --tail)
            {
                int head = tail - len + 1;
                status[head][tail] = false;
                if (nodes[head] == "#")
                    continue;
                for (int i = head + 1; i < tail; ++i)
                {
                    if (status[head+1][i] && status[i+1][tail])
                    {
                        status[head][tail] = true;
                        break;
                    }
                }
            }
        }
        return status[0][n-1];
    }
};