Valid binary tree from array of string

Question

I am having an array of strings.Each character in a string can be r or l only. I have to check if it is valid or not as

1. {rlr,l,r,lr, rl}

           *
         /   \
       l       r
        \      /
          r  l
              \
                r
A valid tree as all nodes are present.




2. {ll, r, rl, rr}
         *
        /  \
        -   r
       /    /\
       l    l r

Invalid tree as there is no l node.

From a give input I have to determine if it is creating a valid tree or not. I have come up with two solutions.

1.Using trie to store input and marking each node as valid or not while insertion.

2.Sort the input array according to the length. So for the first case it will be { l, r, lr, rl, rlr}
And I will create a set of strings to put all input. If a string is having length more then 1(for rlr :: r, rl) I will consider all its prefix from index 0 and check in set.if any of the prefix in not present in set then I will return false.
I am wondering if there is a more optimal solution or any modification in the above methods.

Answer 1

Another possible solution is actually building the tree (or trie) and maintain a set of nodes that are incomplete yet.
If you finish iterating over the list and you still have incomplete nodes then the tree isn't valid.
If the set is empty then the tree is valid.

For example, in the second tree you gave, for node ll you will create also node l but you will add it to the incomplete set. If one of the later nodes is l then you will erase it from the set. If not, you will end the iteration with a non empty set that contains you missing nodes.