CSES - Tree recognition

You are given a grid that contains a description of a tree. Your task is to reconstruct the described tree.

The grid can contain the following symbols:

  • .: an empty square
  • 19: a node of the tree
  • /: a connection down and left
  • |: a connection straight down
  • \: a connection down and right

Each node has at most three children. Between a node and its child are one or more connection symbols. The connections are straight lines without bends.

If a node has one child, it is straight down. If a node has two children, they are down and left and down and right. If a node has three children, they are down and left, straight down, and down and right.

In a file findtree.py, implement the function find_tree whose parameter is a description of the grid as a list of strings. The function returns the structure of the depicted tree using the class Node.

You may assume that the size of the grid is at most 20×2020 \times 20 and that the grid depicts a tree with at least one node.

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children if children else []

    def __repr__(self):
        if self.children == []:
            return f"Node({self.value})"
        else:
            return f"Node({self.value}, {self.children})"

def find_tree(grid):
    # TODO

if __name__ == "__main__":
    grid = [r"...........",
            r"...........",
            r"......5....",
            r"...../.\...",
            r"....3...\..",
            r"....|....1.",
            r"....2......"]
    tree = find_tree(grid)
    print(tree)
    # Node(5, [Node(3, [Node(2)]), Node(1)])

    grid = [r"....1.....",
            r".../.\....",
            r"..2...\...",
            r"..|....3..",
            r"..7.../|\.",
            r"./.\.4.5.6",
            r"8...9....."]
    tree = find_tree(grid)
    print(tree)
    # Node(1, [Node(2, [Node(7, [Node(8), Node(9)])]), Node(3, [Node(4), Node(5), Node(6)])])

Here r"" denotes a string in which the character \ is not treated as an escape character but as a regular character.