class TreeNode:
    def __init__(self, val):
        self.val = val
        self.counter = 1
        self.children = []

class Solution:
    # @param A : list of strings
    # @return a list of strings
    def prefix(self, A):
        head = TreeNode('')
        head.counter = 0

        for s in A:
            n = head
            for i in range(len(s)):
                found = False
                for child in n.children:
                    if child.val == s[:i+1]:
                        found = True
                        n = child
                        n.counter += 1
                        break
                if not found:
                    newChild = TreeNode(s[:i+1])
                    n.children.append(newChild)
                    n = newChild

        stack = [head]
        result = []
        while stack:
            node = stack.pop()
            if node.counter == 1:
                result.append(node.val)
            else:
                for child in node.children:
                    stack.append(child)

        return result