Binary Tree Intersection And Union

source: University of Aizu Programming Contest 2005

raw_problem:
Binary Tree Intersection And Union

Given two binary trees, we consider the “intersection” and “union” of them.
Here, we distinguish the left and right child of a node when it has only one
child. The definitions of them are very simple. First of all, draw a complete
binary tree (a tree whose nodes have either 0 or 2 children and leaves have
the same depth) with sufficiently large depth. Then, starting from its root,
write on it a number, say, 1 for each position of first tree, and draw different
number, say, 2 for second tree. The “intersection” of two trees is a tree with
nodes numbered both 1 and 2, and the “union” is a tree with nodes numbered
either 1 or 2, or both. For example, the intersection of trees in Figures 1 and
2 is a tree in Figure 3, and the union of them is a tree in Figure 4.

A node of a tree is expressed by a sequence of characters, “(,)“. If a node
has a left child, the expression of the child is inserted between ’(’ and ’,’.
The expression of a right child is inserted between ’,’ and ’)’. For exam-
ple, the expression of trees in Figures 1 and 2 are “((,),(,))“ and “((,(,)),)“,
respectively.

Input

Each line of the input contains an operation. An operation starts with a
character which specifies the type of operation, either ’i’ or ’u’: ’i’ means
intersection, and ’u’ means union. Following the character and a space,
two tree expressions are given, separated by a space. It is assumed that
1 <= #nodes in a tree <= 100, and no tree expression contains spaces and
syntax errors. Input is terminated by EOF.

Output

For each line of the input, output a tree expression, without any space, for
the result of the operation.

Sample Input

i ((,),(,)) ((,(,)),)
u ((,),(,)) ((,(,)),)

Output for the Sample Input

((,),)
((,(,)),(,))

solutions: ["# AOJ 1001: Binary Tree Intersection And Union\n# Python3 2018.7.5 bal4u\n\ndef parse(p, i):\n\tglobal sz\n\tnode[i][2] += 1\n\tdel p[0]\n\tif p[0] != ',':\n\t\tif node[i][0] == 0:\n\t\t\tnode[i][0] = sz\n\t\t\tsz += 1\n\t\tparse(p, node[i][0])\n\tdel p[0]\n\tif p[0] != ')':\n\t\tif node[i][1] == 0:\n\t\t\tnode[i][1] = sz\n\t\t\tsz += 1\n\t\tparse(p, node[i][1])\n\tdel p[0]\n\ndef act(i, k):\n\tglobal ans\n\tif node[i][2] < k: return\n\tans += '('\n\tif node[i][0] > 0: act(node[i][0], k)\n\tans += ','\n\tif node[i][1] > 0: act(node[i][1], k)\n\tans += ')'\n\nwhile True:\n\ttry: op, a, b = input().split()\n\texcept: break\n\tsz = 1\n\tnode = [[0 for j in range(3)] for i in range(210)]\n\tparse(list(a), 0)\n\tparse(list(b), 0)\n\tans = ''\n\tact(0, 2 if op== 'i' else 1)\n\tprint(ans)\n", "#!/usr/bin/env python3\n# -*- coding: utf-8 -*-\n\nimport sys\n\ndef tree_left(node, it):\n    c = next(it)\n\n    if c == \"(\":\n        node[0] = [None, None]\n        tree_left(node[0], it)\n        c = next(it)\n\n    if c == \",\":\n        tree_right(node, it)\n    else:\n        assert False\n\ndef tree_right(node, it):\n    c = next(it)\n\n    if c == \"(\":\n        node[1] = [None, None]\n        tree_left(node[1], it)\n        c = next(it)\n\n    if c == \")\":\n        pass\n    else:\n        assert False\n\ndef tree_parse(s):\n    root = [None, None]\n\n    s = s[1:]\n    it = iter(s)\n    tree_left(root, it)\n\n    return root\n\ndef tree_dump(node):\n    s = \"\"\n\n    s += \"(\"\n    if node[0]:\n        s += tree_dump(node[0])\n    s += \",\"\n    if node[1]:\n        s += tree_dump(node[1])\n    s += \")\"\n\n    return s\n\ndef intersection(t1, t2):\n    if t1 is None or t2 is None:\n        return None\n\n    node = [None, None]\n    node[0] = intersection(t1[0], t2[0])\n    node[1] = intersection(t1[1], t2[1])\n    return node\n\ndef union(t1, t2):\n    if t1 is None and t2 is None:\n        return None\n    elif t1 is None:\n        return t2\n    elif t2 is None:\n        return t1\n\n    node = [None, None]\n    node[0] = union(t1[0], t2[0])\n    node[1] = union(t1[1], t2[1])\n    return node\n\ndef main():\n    for line in sys.stdin:\n        op, s1, s2 = line.split()\n        tree1 = tree_parse(s1)\n        tree2 = tree_parse(s2)\n        #print(tree_dump(tree1))\n        #print(tree_dump(tree2))\n        if op == \"i\":\n            ans = intersection(tree1, tree2)\n            print(tree_dump(ans))\n        elif op == \"u\":\n            ans = union(tree1, tree2)\n            print(tree_dump(ans))\n\nif __name__ == \"__main__\": main()\n", "class Node:\n    def __init__(self, left, right):\n        self.left = left\n        self.right = right\n        self.val = ''\n    \n    @classmethod\n    def fromString(cls, s):\n        pos = 1\n        if s[pos] == '(':\n            e = getEnd(s, 1)\n            left = cls.fromString(s[1:e+1])\n            pos = e + 2\n        else:\n            left = None\n            pos += 1\n\n        if s[pos] == '(':\n            e = getEnd(s, pos)\n            right = Node.fromString(s[pos:e+1])\n        else:\n            right = None\n\n        return cls(left, right)\n\n    def __str__(self):\n        lstr = \"\" if self.left == None else str(self.left)\n        rstr = \"\" if self.right == None else str(self.right)\n        return \"({},{})\".format(lstr, rstr)\n\ndef getEnd(s, pos):\n    count = 0\n    while True:\n        if s[pos] == '(':\n            count += 1\n        elif s[pos] == ')':\n            count -= 1\n        if count == 0:\n            break\n        pos += 1\n    return pos\n\ndef intersection(root1, root2):\n    if root1.left == None or root2.left == None:\n        root1.left = None\n    else:\n        intersection(root1.left, root2.left)\n    \n    if root1.right == None or root2.right == None:\n        root1.right = None\n    else:\n        intersection(root1.right, root2.right)\n\ndef union(root1, root2):\n    if root1.left == None and root2.left == None:\n        pass\n    elif root1.left != None and root2.left == None:\n        pass\n    elif root1.left == None and root2.left != None:\n        root1.left = root2.left\n    else:\n        union(root1.left, root2.left)\n    \n    if root1.right == None and root2.right == None:\n        pass\n    elif root1.right != None and root2.right == None:\n        pass\n    elif root1.right == None and root2.right != None:\n        root1.right = root2.right\n    else:\n        union(root1.right, root2.right)\n\nif __name__ == '__main__':\n    try:\n        while True:\n            line = input().strip().split()\n            c = line[0]\n            a = Node.fromString(line[1])\n            b = Node.fromString(line[2])\n\n            if c == 'i':\n                intersection(a, b)\n            else:\n                union(a, b)\n\n            print(a)\n\n    except EOFError:\n        pass\n", "import re\n\nclass bintree():\n    def __init__(self, str1):\n        self.str1 = str1\n        if self.str1[1] != \",\":\n            c = 0\n            counter = 0\n            for s in str1[1:]:\n                counter += 1\n                if s == \"(\":\n                    c += 1\n                elif s == \")\":\n                    c -= 1\n                if c == 0:\n                    break\n            self.left = bintree(str1[1:counter+1])\n                \n            #match1 = re.search(\"\\((\\(.*\\)),.*\\)\",str1)\n            #if match1 != None:\n            #    self.left = bintree(str(match1.group(1)))\n        else:\n            self.left = \"\"\n        if self.str1[-2] != \",\":\n            str1 = str1[0]+str1[1+len(str(self.left)):]\n            match2 = re.search(\"\\(,(\\(.*\\))\\)\",str1)\n            if match2 != None:\n                self.right = bintree(str(str1[2:-1]))\n        else:\n            self.right = \"\"\n    def __str__(self):\n        return self.str1\n        \ndef inter(bin1, bin2):\n    if bin1.left != \"\" and bin2.left != \"\":\n        strleft = inter(bin1.left, bin2.left)\n    else:\n        strleft = \"\"\n    if bin1.right != \"\" and bin2.right != \"\":\n        strright = inter(bin1.right, bin2.right)\n    else:\n        strright = \"\"\n    return \"(\" + strleft + \",\" + strright + \")\"\n\ndef union(bin1, bin2):\n    if bin1.left != \"\" or bin2.left != \"\":\n        if bin1.left == \"\":\n            strleft = str(bin2.left)\n        elif bin2.left == \"\":\n            strleft = str(bin1.left)\n        else:\n            strleft = union(bin1.left, bin2.left)\n    else:\n        strleft = \"\"\n    if bin1.right != \"\" or bin2.right != \"\":\n        if bin1.right == \"\":\n            strright = str(bin2.right)\n        elif bin2.right == \"\":\n            strright = str(bin1.right)\n        else:\n            strright = union(bin1.right, bin2.right)\n    else:\n        strright = \"\"\n        #print(\"(\" + strleft + \",\" + strright + \")\")\n    return \"(\" + strleft + \",\" + strright + \")\"\n\n\n\nwhile True:\n    \n    try:\n        inputs = map(str,input().split())\n        order = next(inputs)\n        if order == \"i\":\n            t1 = bintree(next(inputs))\n            t2 = bintree(next(inputs))\n            #print(t1.left,t1.right)\n            print(inter(t1, t2))#  == \"((((((,),),),),),)\")\n            \n        elif order == \"u\":\n            t1 = bintree(next(inputs))\n            t2 = bintree(next(inputs)) \n            #print(t1.left,t1.right)\n            #print(t1.left,t1.right)\n            print(union(t1,t2))# == \"((((,),(,)),((,),(,))),(((,),(,)),((,),(,))))\")\n    except EOFError as exception:\n        break\n"]

source: aizu

question:
Binary Tree Intersection And Union

Given two binary trees, we consider the “intersection” and “union” of them.
Here, we distinguish the left and right child of a node when it has only one
child. The definitions of them are very simple. First of all, draw a complete
binary tree (a tree whose nodes have either 0 or 2 children and leaves have
the same depth) with sufficiently large depth. Then, starting from its root,
write on it a number, say, 1 for each position of first tree, and draw different
number, say, 2 for second tree. The “intersection” of two trees is a tree with
nodes numbered both 1 and 2, and the “union” is a tree with nodes numbered
either 1 or 2, or both. For example, the intersection of trees in Figures 1 and
2 is a tree in Figure 3, and the union of them is a tree in Figure 4.

![image](1.png)

A node of a tree is expressed by a sequence of characters, “(,)“. If a node
has a left child, the expression of the child is inserted between ’(’ and ’,’.
The expression of a right child is inserted between ’,’ and ’)’. For exam-
ple, the expression of trees in Figures 1 and 2 are “((,),(,))“ and “((,(,)),)“,
respectively.

Input

Each line of the input contains an operation. An operation starts with a
character which specifies the type of operation, either ’i’ or ’u’: ’i’ means
intersection, and ’u’ means union. Following the character and a space,
two tree expressions are given, separated by a space. It is assumed that
1 <= #nodes in a tree <= 100, and no tree expression contains spaces and
syntax errors. Input is terminated by EOF.

Output

For each line of the input, output a tree expression, without any space, for
the result of the operation.

Sample Input

i ((,),(,)) ((,(,)),)
u ((,),(,)) ((,(,)),)

Output for the Sample Input

((,),)
((,(,)),(,))

data_split: test