Lowest Common Ancestor in a Binary Tree Represented by Binary Strings

In this problem, you are given an integer k and a list of k binary strings. Each binary string represents the position of a node in a binary tree where the common prefix of these binary strings corresponds to the path from the root to their lowest common ancestor (LCA). Your task is to find the longest common prefix among the provided binary strings.

Note: If there is no common prefix among the strings, the output should be an empty string.

Example: For k = 3 and positions ["10", "110", "111"], the longest common prefix is "1", which is the LCA.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer k, the number of binary strings.
• The next k lines each contain a binary string that represents a node's position in the binary tree.

outputFormat

Print to stdout a single line containing the longest common prefix among the k binary strings. If there is no common prefix, output an empty string.

3
10
110
111

1