Links That Form a Single Tree

Medium

There are n nodes numbered 0 to n - 1. For each node i you know its left child left[i] and its right child right[i]; -1 means there is no child on that side. The nodes carry no values, only their numbers matter. Return True if these links form exactly one valid binary tree containing all n nodes, and False otherwise.

Example 1

n=5, left=[3, 2, -1, -1, -1], right=[1, 4, -1, -1, -1] → True

Node 0 is the root with children 3 and 1, and node 1 has children 2 and 4. All five nodes are in one tree.

Example 2

n=3, left=[1, -1, -1], right=[-1, -1, -1] → False

Node 2 is not linked to anything, so there are two trees instead of one.

Example 3

n=3, left=[1, 2, -1], right=[2, -1, -1] → False

Node 2 has two parents, 0 and 1, which cannot happen in a tree.

Constraints

1 ≤ n ≤ 10⁴
len(left) == len(right) == n
-1 ≤ left[i], right[i] ≤ n - 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Union Find Graph Binary Tree

Similar problems

Rooms Open from the Hall Medium The Tree Seen From the Right Medium Do the Links Form a Tree Medium Tree Columns, Top Down Medium Isolated Groups in a Network Medium

Input

n=5, left=[3, 2, -1, -1, -1], right=[1, 4, -1, -1, -1]

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 140 tests on the server, hidden ones included.