Construct Binary Tree from parent Array

# Node class definition
class Node:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
# function to construct binary tree from parent array
def construct_tree(arr):
    # create dictionary to store child nodes for each parent node
    nodes = {}
    for i, parent in enumerate(arr):
        if parent not in nodes:
            nodes[parent] = []
        nodes[parent].append(i)
    
    # create root node
    root = Node(0)
    
    # traverse tree in level order and create nodes
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node.val in nodes:
            children = nodes[node.val]
            if children:
                node.left = Node(children[0])
                queue.append(node.left)
            if len(children) > 1:
                node.right = Node(children[1])
                queue.append(node.right)
    
    return root
 
# example usage
parent_arr = [-1, 0, 0, 1, 1, 3, 5]
root = construct_tree(parent_arr)
print(root.val)  # output: 0
print(root.left.val, root.right.val)  # output: 1 None
print(root.left.left.val, root.left.right.val)  # output: 3 4
print(root.left.right.left.val, root.left.right.right.val)  # output: 5 None