We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Validate Binary Tree Nodes

Number: 1275

Difficulty: Medium

Paid? No

Companies: Microsoft, Amazon, Google, Meta

Problem Description

Given n nodes labeled from 0 to n-1 and two arrays that represent the left and right children of each node (with -1 indicating no child), determine if these nodes form exactly one valid binary tree. This involves ensuring that there is exactly one root (a node that is not any other node's child), every node except the root has exactly one parent, and all nodes are connected (i.e. reachable from the unique root).

Key Insights

  • Each node (except the root) must have exactly one parent.
  • There should be exactly one node that is not referenced as a child in any of the arrays (this node is the root).
  • A traversal from the root (using DFS or BFS) should visit all nodes exactly once.
  • If any node is encountered more than once or not at all, the structure is invalid.
  • Avoid cycles and disconnected components, which would violate binary tree properties.

Space and Time Complexity

Time Complexity: O(n) - We process each node and each child pointer at most once. Space Complexity: O(n) - Extra space is used for tracking parent counts and for the traversal (visited set or queue).

Solution

We solve this problem by first identifying the root by counting how many times each node appears as a child. There must be exactly one node that does not appear as any child. Then, use a traversal algorithm (either DFS or BFS) starting from the root to ensure that all nodes are reached exactly once. If some node is revisited or unreachable, the binary tree is not valid. The key challenge is to ensure that each child has one and only one parent and that the graph is fully connected and acyclic.

Code Solutions

# Function to validate binary tree nodes using DFS
def validateBinaryTreeNodes(n, leftChild, rightChild):
    # Step 1: Calculate indegree for each node
    indegree = [0] * n
    for i in range(n):
        if leftChild[i] != -1:
            indegree[leftChild[i]] += 1
            # If any node has more than one parent, return False early
            if indegree[leftChild[i]] > 1:
                return False
        if rightChild[i] != -1:
            indegree[rightChild[i]] += 1
            if indegree[rightChild[i]] > 1:
                return False
    # Step 2: Find the root (node with indegree 0)
    root = -1
    for i in range(n):
        if indegree[i] == 0:
            if root == -1:
                root = i
            else:
                # More than one root candidate found
                return False
    # Must find exactly one root
    if root == -1:
        return False

    # Step 3: DFS traversal to check connectivity and cycle detection
    seen = set()
    def dfs(node):
        if node == -1:
            return
        # If node is already visited, cycle exists or duplicate traversal, invalid
        if node in seen:
            return
        seen.add(node)
        dfs(leftChild[node])
        dfs(rightChild[node])
    
    dfs(root)
    # All nodes must be visited exactly once
    return len(seen) == n

# Example usage:
#print(validateBinaryTreeNodes(4, [1, -1, 3, -1], [2, -1, -1, -1]))
← Back to All Questions