1361. Validate Binary Tree Nodes


Problem Description

You are given a number n, which represents the total number of binary tree nodes. Each node is uniquely numbered from 0 to n-1. Along with this, you are provided two lists, leftChild and rightChild, which represent the indices of the left and right children for each node. If a node does not have a left or right child, its corresponding value in the list will be -1. Your task is to determine if all these nodes can form exactly one valid binary tree.

To qualify as a valid binary tree, there must be exactly one root node (a node without a parent), and each node must have exactly one parent, except for the root. Furthermore, there must be no cycles within the tree structure—no node can be an ancestor of itself.

Intuition

The approach to solve this problem involves using a union-find data structure, which is perfect for checking cycles and connections between nodes. The primary idea behind union-find is to group nodes into sets. Each set is identified by a representative, which is one of the nodes in the set (initially, each node is its own representative).

The solution follows these steps:

  1. Initialization: Create a union-find structure (p) where each node is initially part of its own set, and a visited array (vis) to keep track of whether a node has already been linked as a child to another node.

  2. Iterative Check: Go through each node's children (left and right). If a child node is already visited (vis[j] is true), it means that child has more than one parent, which invalidates the tree structure. If the parent of the node is the same as the parent of its child (find(i) == find(j)), it means that a cycle is detected, which again invalidates the tree.

  3. Union Operations: If a child has not been visited and it doesn't create a cycle, we perform a union operation. This involves setting the parent of the child's root to be the root of the current node, and marking the child as visited.

  4. Validate Tree: Finally, after iterating through all nodes, we check if there is exactly one node left without a parent (one root), which means that n == 1 at the end of the process after decrementing the count when nodes are linked. If n == 1, it indicates that we have exactly one tree and it is valid, so we return true. Any other value indicates an invalid tree.

In summary, the union-find helps efficiently manage the connectivity between nodes while making it easy to check for cycles and multiple parents, ensuring we end up with a valid binary tree if possible.

Learn more about Tree, Depth-First Search, Breadth-First Search, Union Find, Graph and Binary Tree patterns.

Solution Approach

The implementation of the solution revolves around the union-find algorithm, which is a well-known algorithm used in situations where we need to find and manage connected components or sets, especially when the union and find operations are needed frequently and must perform efficiently.

Here is an explanation of each part of the implementation:

  1. Initialization: The lists p and vis are initialized. The list p represents the parent of each node, and it's initialized such that each node is its own parent. The list vis is a boolean array initialized to False, indicating that no nodes have been visited initially.

    1p = list(range(n))
    2vis = [False] * n
  2. Find Function: The find function is a recursive function that traverses the p array to find the root of the set that contains node x. If the current node x is not the root (i.e., p[x] != x), it performs path compression by setting p[x] to the result of a recursive call to find(p[x]). Path compression is a technique that flattens the structure of the sets for faster future lookup.

    1def find(x: int) -> int:
    2    if p[x] != x:
    3        p[x] = find(p[x])
    4    return p[x]
  3. Iterate Over Nodes: We loop over all nodes, and for each node, we loop over its left and right children.

    1for i, (a, b) in enumerate(zip(leftChild, rightChild)):
  4. Check and Union: Inside the loop, we check if child node j is not -1, which means the current node has a child. There are two important conditions to check for here:

    • If vis[j] is True, it means the child node j is already connected to a parent, indicating an invalid tree because a node has more than one parent.
    • If find(i) == find(j), it means the parent of node i is in the same set as child j, indicating a cycle in the tree, which invalidates the binary tree property.

    If neither condition is met, we perform a union operation by setting the parent of j's root to be i's root, marking j as visited, and decrementing n by 1, because we have linked j under a parent.

    1for j in (a, b):
    2    if j != -1:
    3        if vis[j] or find(i) == find(j):
    4            return False
    5        p[find(i)] = find(j)
    6        vis[j] = True
    7        n -= 1
  5. Validate by Single Root: After the loop, the last validation step is to check whether n == 1. This validation ensures that there is exactly one root node left, implying that the remaining unvisited node is the root of the entire binary tree. If this condition holds, it means all nodes have been connected properly and exactly one valid binary tree has been formed.

    1return n == 1

In conclusion, by utilizing the union-find algorithm and taking into account the unique properties of a binary tree, we can determine whether the given nodes can form exactly one valid binary tree.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach provided.

  • Suppose we have n = 4 nodes, which are numbered 0 to 3.
  • Let's say the leftChild list is [1, -1, -1, -1] and the rightChild list is [2, 3, -1, -1]. This implies that:
    • Node 0 has 1 as its left child and 2 as its right child.
    • Node 1 does not have any children, but it is the right child of Node 0.
    • Node 2 is the left child of Node 0 and does not have any children.
    • Node 3 does not have any children but is a right child of Node 1.

Using the solution approach:

  1. Initialization: We initialize parent array p to [0, 1, 2, 3] and visited array vis to [False, False, False, False].

  2. Find Function: The find function will be used later to determine the roots of the nodes and apply path compression.

  3. Iterate Over Nodes:

    • For Node 0, leftChild[0] = 1 and rightChild[0] = 2.
    • For Node 1, leftChild[1] = -1 (no left child) and rightChild[1] = 3.
  4. Check and Union:

    First, iterate for Node 0:

    • For leftChild[0] = 1:
      • vis[1] is False, so Node 1 has no parent yet.
      • find(0) is 0 and find(1) is 1. They are not the same, no cycle here.
      • Perform union: set p[1] to 0 (p[find(1)] = find(0)), mark vis[1] as True, decrement n to 3.
    • For rightChild[0] = 2:
      • vis[2] is False. Node 2 has no parent yet.
      • find(0) is 0 and find(2) is 2. They are not the same, no cycle here.
      • Perform union: set p[2] to 0 (p[find(2)] = find(0)), mark vis[2] as True, decrement n to 2.

Then, iterate for Node 1:

  • For rightChild[1] = 3:
    • vis[3] is False. Node 3 has no parent yet.
    • find(1) is 0 and find(3) is 3. They are not the same, no cycle here.
    • Perform union: set p[3] to 0 (p[find(3)] = find(1)), mark vis[3] as True, decrement n to 1.
  1. Validate by Single Root: After looping through all nodes, we check if n == 1. Since n has been decremented correctly to 1, we have exactly one node left without a parent. This indicates there is exactly one root in the binary tree, and the tree is valid.

If we visualize the final binary tree formed, it looks like this:

1    0
2   / \
3  1   2
4   \
5    3

The tree formed is indeed a valid binary tree with Node 0 as the root, and each node has exactly one parent, fulfilling the requirements of the problem. Therefore, the implemented solution would return True.

Solution Implementation

1from typing import List
2
3class Solution:
4    def validateBinaryTreeNodes(
5        self, node_count: int, left_children: List[int], right_children: List[int]
6    ) -> bool:
7        # Helper function to find the root of the set in which element x is.
8        def find_root(x: int) -> int:
9            if parents[x] != x:
10                # Path compression: Directly attaching x to its root to optimize further queries
11                parents[x] = find_root(parents[x])
12            return parents[x]
13
14        # Initialize each node to be its own parent (self loop).
15        # This also sets up the forest for the union-find algorithm.
16        parents = list(range(node_count))
17
18        # Visited array to keep track if a node has already been assigned a parent.
19        visited = [False] * node_count
20
21        # Iterate over each node and their respective left and right children
22        for i, (left_child, right_child) in enumerate(zip(left_children, right_children)):
23            # Iterate over both children of the current node
24            for child in (left_child, right_child):
25                # If the child is not a placeholder value (-1 indicates no child)
26                if child != -1:
27                    # If the child has been visited, or if parent of current node and child node are the same
28                    # then the tree is not valid.
29                    if visited[child] or find_root(i) == find_root(child):
30                        return False
31                    # Union operation: set the parent of the current node's parent to the child's parent
32                    # effectively linking the trees of the current node and child.
33                    parents[find_root(i)] = find_root(child)
34                    # Mark the child as visited
35                    visited[child] = True
36                    # Decrement the node count, aiming to validate if only one root exists at the end
37                    node_count -= 1
38
39        # The tree is valid if it has exactly one node that is not a child of any other node (hence one root).
40        return node_count == 1
41
1class Solution {
2    // Parents array to keep track of the roots of each node
3    private int[] parents;
4
5    /**
6     * This function checks if the given nodes form a valid binary tree.
7     *
8     * @param n          the number of nodes.
9     * @param leftChild  array containing the indices of left children.
10     * @param rightChild array containing the indices of right children.
11     * @return boolean whether the input forms a valid binary tree.
12     */
13    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
14        // Initialize parents array where each node is its own parent at the start
15        parents = new int[n];
16        for (int i = 0; i < n; i++) {
17            parents[i] = i;
18        }
19
20        // Visited array to check if a node has already been assigned a parent
21        boolean[] visited = new boolean[n];
22
23        // Iterate over all nodes
24        for (int nodeIndex = 0; nodeIndex < n; nodeIndex++) {
25            // Check both children of the current node
26            for (int child : new int[]{leftChild[nodeIndex], rightChild[nodeIndex]}) {
27                if (child != -1) { // If the child is not a null node (-1)
28                    // If either the child has already been visited (has another parent) or the child and parent are part of the same subtree,
29                    // the tree is invalid
30                    if (visited[child] || find(nodeIndex) == find(child)) {
31                        return false;
32                    }
33                    // Union the current node and the child
34                    parents[find(nodeIndex)] = find(child);
35
36                    // Mark the child as visited
37                    visited[child] = true;
38
39                    // Decrement the remaining nodes count
40                    --n;
41                }
42            }
43        }
44
45        // Check if exactly one root is remaining, which implies a valid binary tree
46        return n == 1;
47    }
48
49    /**
50     * Helper method to find the root of the given node using path compression.
51     *
52     * @param node the node to find the root for.
53     * @return the root of the given node.
54     */
55    private int find(int node) {
56        // Recursive path compression: nodes on the path directly point to root
57        if (parents[node] != node) {
58            parents[node] = find(parents[node]);
59        }
60        return parents[node];
61    }
62}
63
1#include <vector>
2#include <numeric>
3#include <cstring>
4#include <functional>
5
6class Solution {
7public:
8    bool validateBinaryTreeNodes(int nodeCount, vector<int>& leftChildren, vector<int>& rightChildren) {
9        // Array 'parents' keeps track of the root of each node's disjoint set
10        int parents[nodeCount];
11        // Initialize each node as its own parent to signify its own set
12        iota(parents, parents + nodeCount, 0);
13      
14        // Array 'visited' indicates whether a node has been added to the tree
15        bool visited[nodeCount];
16        // Initialize all nodes as unvisited
17        memset(visited, 0, sizeof(visited));
18      
19        // Find function using path compression for disjoint set data structure
20        function<int(int)> find = [&](int node) {
21            // Traverse up the tree until the root is found, and compress path
22            return parents[node] == node ? node : parents[node] = find(parents[node]);
23        };
24      
25        // Iterate over the nodes to build the tree and check for cycles
26        for (int i = 0; i < nodeCount; ++i) {
27            for (int child : {leftChildren[i], rightChildren[i]}) {
28                // If the child exists (-1 represents a non-existent child)
29                if (child != -1) {
30                    // If the child has already been visited or is part of the same set, it's not a valid tree
31                    if (visited[child] || find(i) == find(child)) {
32                        return false;
33                    }
34                    // Union: merge the set that contains the current node with the set that contains the child
35                    parents[find(i)] = find(child);
36                    // Mark the child as visited
37                    visited[child] = true;
38                    // Decrease the number of roots by one - as one more node is connected to the tree
39                    --nodeCount;
40                }
41            }
42        }
43        // There should be exactly one root remaining for a valid binary tree
44        return nodeCount == 1;
45    }
46};
47
1function validateBinaryTreeNodes(nodeCount: number, leftChildren: Array<number>, rightChildren: Array<number>): boolean {
2    // Array 'parents' keeps track of the root of each node's disjoint set
3    let parents = Array.from({length: nodeCount}, (_, i) => i);
4  
5    // Array 'visited' indicates whether a node has been added to the tree
6    let visited = new Array<boolean>(nodeCount).fill(false);
7  
8    // Find function using path compression for disjoint set data structure
9    function find(node: number): number {
10        // Traverse up the tree until the root is found, and compress path
11        if (parents[node] !== node) {
12            parents[node] = find(parents[node]);
13        }
14        return parents[node];
15    }
16  
17    // Iterate over the nodes to build the tree and check for cycles
18    for (let i = 0; i < nodeCount; ++i) {
19        [leftChildren[i], rightChildren[i]].forEach(child => {
20            // If the child exists (-1 represents a non-existent child)
21            if (child !== -1) {
22                // If the child has already been visited or is part of the same set, it's not a valid tree
23                if (visited[child] || find(i) === find(child)) {
24                    return false;
25                }
26                // Union: merge the set that contains the current node with the set that contains the child
27                parents[find(i)] = find(child);
28                // Mark the child as visited
29                visited[child] = true;
30                // Decrease the number of roots by one - as one more node is connected to the tree
31                --nodeCount;
32            }
33        });
34
35        // After checking both children, if the return false condition was met, we should terminate early
36        if (nodeCount < 1) {
37            return false;
38        }
39    }
40    // There should be exactly one root remaining for a valid binary tree
41    return nodeCount === 1;
42}
43

Time and Space Complexity

The given code snippet is a Python method designed to validate a binary tree given the number of nodes n and two lists denoting the indices of left and right children. The function utilizes the Union-Find algorithm, also known as the Disjoint Set Union (DSU) algorithm, to determine if the given input constitutes a valid tree structure.

Time Complexity

The time complexity of this algorithm is primarily determined by two factors: the traversals over the leftChild and rightChild lists, and the union-find operations.

  1. Iterating over the leftChild and rightChild lists occurs once for each node in the binary tree. This operation has a linear time complexity of O(n) because each node's children are checked exactly once.

  2. The union-find operations consist of the find function, which includes path compression. While a naïve implementation of union-find has a time complexity approaching O(n) for each find operation, path compression optimizes this to an amortized time complexity of approximately O(α(n)), where α(n) is the inverse Ackermann function. The inverse Ackermann function grows extremely slowly and, for all practical purposes, can be considered almost constant.

Considering these factors, the overall time complexity of the union-find operations is O(n * α(n)). However, due to the extremely slow growth of the α(n) term, the time complexity is effectively O(n). Therefore, the total time complexity of the validateBinaryTreeNodes function is O(n).

Space Complexity

The space complexity is determined by the space required to maintain the p array and the vis array, used to track the parents in the union-find structure and the visited state of nodes, respectively.

  1. The p array is initialized with a size of n, resulting in a space complexity of O(n).

  2. The vis array is also of size n, contributing another O(n) to the space complexity.

These are the only significant sources of space usage in the algorithm. Since they are linear with respect to the number of nodes n, the overall space complexity is also O(n).

In summary, for the provided validateBinaryTreeNodes function:

  • The time complexity is O(n).
  • The space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄