Leetcode 1361. Validate Binary Tree Nodes

1361. Validate Binary Tree Nodes

You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree. If node i has no left child then leftChild[i] will equal -1, similarly for the right child. Note that the nodes have no values and that we only use the node numbers in this problem.

Approach 1: Depth First Search (DFS)


class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int root = findRoot(n, leftChild, rightChild);
        if (root == -1) {
            return false;
        }
        
        Set seen = new HashSet<>();
        Stack stack = new Stack<>();
        seen.add(root);
        stack.push(root);
        
        while (!stack.isEmpty()) {
            int node = stack.pop();
            int[] children = {leftChild[node], rightChild[node]};
            
            for (int child : children) {
                if (child != -1) {
                    if (seen.contains(child)) {
                        return false;
                    }
                    
                    stack.push(child);
                    seen.add(child);
                }
            }
            
        }
        
        return seen.size() == n;
    }
    
    public int findRoot(int n, int[] left, int[] right) {
        Set children = new HashSet<>();
        for (int node : left) {
            children.add(node);
        }
        
        for (int node : right) {
            children.add(node);
        }
        
        for (int i = 0; i < n; i++) {
            if (!children.contains(i)) {
                return i;
            }
        }
        
        return -1;
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

Introduction

The "Validate Binary Tree Nodes" problem is a well-known algorithmic challenge that tests your understanding of trees and graph traversal algorithms. In this problem, you are given a set of binary tree nodes and the task is to validate if the binary tree is well-formed based on certain constraints.

Specifically, given a collection of nodes in a binary tree, you are tasked to ensure the tree follows the following rules:

No node has more than one parent.
The tree should consist of exactly one connected component.
Every node should be referenced by its parent node, except for the root node.

Problem Statement

You are given the following inputs:

n (the number of nodes in the tree)
left (an array of integers representing the left child of each node)
right (an array of integers representing the right child of each node)

Your task is to validate if the binary tree defined by these inputs is a valid binary tree. A valid binary tree must satisfy these conditions:

Each node can have at most one parent.
The tree must have exactly one root node.
All nodes must be connected in a way that forms a single tree structure.

Approach

The solution to this problem requires understanding the structure of binary trees and the nature of tree traversal. To validate the binary tree, you can follow these steps:

Mark parents: Create a set to track which nodes are being used as parents. As you traverse the left and right child arrays, mark each node as a parent.
Identify the root: A valid tree should have exactly one root. The root is the only node that is not a child of any other node. Therefore, you can check for a node that does not appear in the parent set.
Check for a single root: Ensure there is only one node that does not have a parent. If there are multiple nodes without parents or no node without a parent, the structure is invalid.
Ensure no cycles: Perform a traversal (e.g., depth-first search or breadth-first search) to check that all nodes are reachable and there are no cycles in the tree.

Algorithm

The algorithm can be broken down into the following steps:

Initialize a set to track parents of nodes.
Loop through the left and right arrays to mark parents.
Find the root by checking for a node that is not marked as a parent.
If there is more than one root or no root, return false as the tree is invalid.
Perform a DFS or BFS to ensure all nodes are connected and there are no cycles.
If all checks pass, return true, meaning the tree is valid.

Example

Let's consider an example to walk through the solution:

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

In this case:

Node 0 has a left child (1) and a right child (2).
Node 1 has no children (both left and right are -1).
Node 2 has a left child (3) and no right child.
Node 3 has no children.

The tree looks like this:

The tree is valid because there is exactly one root (node 0), all nodes are connected, and there are no cycles.

Code Implementation

Below is a Python implementation of the approach described:

def validateBinaryTreeNodes(n, left, right):
    parent = set()
    
    # Loop through the left and right arrays to track parents
    for i in range(n):
        if left[i] != -1:
            if left[i] in parent:
                return False
            parent.add(left[i])
        if right[i] != -1:
            if right[i] in parent:
                return False
            parent.add(right[i])
    
    # Find the root node
    root = -1
    for i in range(n):
        if i not in parent:
            if root == -1:
                root = i
            else:
                return False  # Multiple roots found
    
    # Check connectivity (DFS or BFS can be used here)
    visited = [False] * n
    def dfs(node):
        if visited[node]:
            return
        visited[node] = True
        if left[node] != -1:
            dfs(left[node])
        if right[node] != -1:
            dfs(right[node])
    
    # Start DFS from root
    dfs(root)
    
    # Check if all nodes are visited
    if all(visited):
        return True
    return False

In this code, we first mark the parent nodes and check for any repeated parent nodes. Then, we look for the root node and ensure there is only one. Finally, we perform a DFS to ensure the tree is connected and has no cycles.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes. This is because we make a single pass over the left and right arrays, and the DFS traversal also takes O(n) time.

Conclusion

The "Validate Binary Tree Nodes" problem is a great exercise for practicing tree traversal algorithms and understanding the structure of trees. By using simple techniques like marking parent nodes, identifying the root, and performing a depth-first search, you can efficiently validate whether a given set of nodes forms a valid binary tree.