import json
import traceback
import unittest


def merge_list(l1, l2):
    merged = {}
    for item in l1 + l2:
        if item['id'] in merged:
            for elem in item['children']:
                merged[item['id']]['children'].append(elem)
        else:
            merged[item['id']] = item
    l3 = [val for (_, val) in merged.items()]
    return l3


class Test(unittest.TestCase):

    def setUp(self):
        pass

    def tearDown(self):
        pass

    def test0(self):
        subtree1 = [
            {
                "id": "file",
                "caption": "File",
                "children": []
            },
            {
                "id": "edit",
                "caption": "Edit",
                "children": []
            },
            {
                "id": "tools",
                "caption": "Tools",
                "children": [
                    {
                        "id": "packages",
                        "caption": "Packages",
                        "children": []
                    }
                ]
            },
            {
                "id": "help",
                "caption": "Help",
                "children": []
            },
        ]

        subtree2 = [
            {
                "id": "file",
                "caption": "File",
                "children": [
                    {"caption": "New"},
                    {"caption": "Exit"},
                ]
            }
        ]

        subtree3 = [
            {
                "id": "edit",
                "children": [
                    {"caption": "Copy"},
                    {"caption": "Cut"},
                    {"caption": "Paste"},
                ]
            },
            {
                "id": "help",
                "children": [
                    {"caption": "About"},
                ]
            }
        ]

        subtree4 = [
            {
                "id": "edit",
                "children": [
                    {
                        "id": "text",
                        "caption": "Text",
                        "children": [
                            {"caption": "Insert line before"},
                            {"caption": "Insert line after"}
                        ]
                    }
                ]
            }
        ]

        expected_output = [
            {
                "id": "file",
                "caption": "File",
                "children": [
                    {
                        "caption": "New"
                    },
                    {
                        "caption": "Exit"
                    }
                ]
            },
            {
                "id": "edit",
                "caption": "Edit",
                "children": [
                    {
                        "caption": "Copy"
                    },
                    {
                        "caption": "Cut"
                    },
                    {
                        "caption": "Paste"
                    },
                    {
                        "id": "text",
                        "caption": "Text",
                        "children": [
                            {
                                "caption": "Insert line before"
                            },
                            {
                                "caption": "Insert line after"
                            }
                        ]
                    }
                ]
            },
            {
                "id": "tools",
                "caption": "Tools",
                "children": [
                    {
                        "id": "packages",
                        "caption": "Packages",
                        "children": []
                    }
                ]
            },
            {
                "id": "help",
                "caption": "Help",
                "children": [
                    {
                        "caption": "About"
                    }
                ]
            }
        ]

        output = merge_list(subtree1, subtree2)
        output = merge_list(output, subtree3)
        output = merge_list(output, subtree4)
        self.assertEqual(output, expected_output)


if __name__ == "__main__":
    unittest.main()