Jobs

Interviews

Discussions

Validate Binary Tree Nodes

Medium

Asked by:

More companies

61 views

Topics:

TreesGraphs

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.

Example 1:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

Example 2:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false

Example 3:

Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false

Constraints:

n == leftChild.length == rightChild.length
1 <= n <= 10⁴
-1 <= leftChild[i], rightChild[i] <= n - 1

Try coding it in LeetCode

Validate Binary Tree Nodes

Medium

Asked by:

61 views

Topics:

TreesGraphs

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.

Example 1:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

Example 2:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false

Example 3:

Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false

Constraints:

n == leftChild.length == rightChild.length
1 <= n <= 10⁴
-1 <= leftChild[i], rightChild[i] <= n - 1

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of values for the node values (0 to n-1, or other)?
Can a node have more than one parent? Or is it guaranteed to be a tree structure, even if not valid?
If the input represents multiple disjoint trees, should I return `false`?
What should I return if the input `n` is zero or the arrays are empty?
Are there any memory constraints given the size of `n`?

Brute Force Solution

Approach

To validate if the given binary tree structure is a valid tree, we will explore every possible tree configuration. We'll start by checking if the graph formed by the provided parent-child relationships contains any cycles or multiple roots. We will then check if all nodes are reachable from a single root.

Here's how the algorithm would work step-by-step:

First, we need to figure out which node, if any, could be the root of our potential tree. A root is a node that no other node points to as a child.
If we find more than one potential root, then it can't be a valid tree, so we're done.
Next, starting from our potential root, we will explore every node to see if we can reach every other node. This is like tracing every path from the root and checking each node to see that every connection can be established without creating loops or invalid connections.
While exploring, we will mark each node as visited. If we try to visit a node that has already been visited, that means there's a cycle, and it's not a valid tree.
Also, if any node has more than one parent, then it's not a valid tree, and we can stop.
If we reach a point where we cannot find a single root node, it also can't be a valid tree, and we are done.
If we explore the entire structure and find no multiple roots, cycles, or nodes with multiple parents, and every node is reachable from the single identified root, we can conclude it's a valid tree.

Code Implementation

def validate_binary_tree_nodes(number_of_nodes, left_child, right_child):
    parents = [0] * number_of_nodes

    # Find parents for all nodes
    for i in range(number_of_nodes):
        if left_child[i] != -1:
            if parents[left_child[i]] != 0:
                return False
            parents[left_child[i]] = i + 1
        if right_child[i] != -1:
            if parents[right_child[i]] != 0:
                return False
            parents[right_child[i]] = i + 1

    roots = []
    for i in range(number_of_nodes):
        if parents[i] == 0:
            roots.append(i)

    # Check for multiple roots
    if len(roots) != 1:
        return False

    root = roots[0]
    visited = [False] * number_of_nodes
    stack = [root]
    count = 0

    # Use DFS to traverse the tree and check reachability and cycles
    while stack:
        node = stack.pop()
        if visited[node]:
            return False

        visited[node] = True
        count += 1

        if left_child[node] != -1:
            stack.append(left_child[node])
        if right_child[node] != -1:
            stack.append(right_child[node])

    # Verify all nodes were visited
    return count == number_of_nodes

Big(O) Analysis

Time Complexity

O(n) – Finding the root involves iterating through the leftChild and rightChild arrays of size n to identify nodes with no incoming edges, which takes O(n) time. The depth-first search (DFS) traversal visits each node at most once to check reachability and detect cycles. Since there are n nodes, the DFS takes O(n) time. The overall time complexity is dominated by the linear traversal and DFS, resulting in O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm utilizes a visited array to keep track of visited nodes during the traversal, and this array has a size proportional to the number of nodes, N. Furthermore, a queue (implicitly within step 3 when tracing every path from the root) might be used for the breadth-first search or depth-first search, and in the worst-case scenario (e.g., a complete binary tree), the queue could contain a significant portion of the nodes. Therefore, the auxiliary space is determined by the visited array and the potential size of the queue, both of which scale with the number of nodes, N, giving us O(N) space complexity.

Optimal Solution

Approach

To validate a binary tree, we need to ensure two things: that all nodes are reachable from a single root, and that no node has more than one parent. We can efficiently check these conditions by using a technique similar to tracing connections to identify the root and then confirming all nodes are connected in a valid tree structure.

Here's how the algorithm would work step-by-step:

First, identify potential root nodes. A root node is a node that isn't a child of any other node. We can find these by checking which nodes are *not* listed as a left or right child in the given information.
If there are multiple potential root nodes, it means the nodes are disconnected, and we immediately know it's not a valid tree.
Choose one of the valid root nodes and start exploring the tree by following the left and right child connections.
As we explore, keep track of all the nodes we visit. Each node should only be visited once. If we ever visit a node a second time, it means there's a cycle, which makes it invalid.
Also, as we explore, ensure that every node we reach actually exists in the list of available nodes. If we can't find the node, this tree isn't valid.
Once we've explored as far as we can from the root, check if we've visited all the nodes. If there are nodes that we didn't reach, the tree is disconnected and therefore invalid.
If we were able to reach all nodes from a single root without visiting any node more than once, the tree is valid.

Code Implementation

def validate_binary_tree_nodes(number_of_nodes, left_children, right_children):
    children = left_children + right_children
    potential_roots = []
    for node_index in range(number_of_nodes):
        if node_index not in children:
            potential_roots.append(node_index)

    if len(potential_roots) != 1:
        return False

    root_node = potential_roots[0]
    visited_nodes = set()
    nodes_to_visit = [root_node]

    while nodes_to_visit:
        current_node = nodes_to_visit.pop()

        if current_node in visited_nodes:
            return False

        visited_nodes.add(current_node)

        left_child = left_children[current_node]
        if left_child != -1:
            nodes_to_visit.append(left_child)

        right_child = right_children[current_node]
        if right_child != -1:
            nodes_to_visit.append(right_child)

    # Must check if all nodes are reachable
    if len(visited_nodes) != number_of_nodes:
        return False

    return True

Big(O) Analysis

Time Complexity

O(n) – Identifying potential root nodes involves iterating through the leftChild and rightChild arrays, each of size n, to find nodes not referenced as children. This takes O(n) time. The breadth-first search (BFS) explores each node at most once to detect cycles and connectivity, which also takes O(n) time in the worst case, where 'n' is the number of nodes. Checking if all nodes are visited takes O(n) time. Therefore, the overall time complexity is dominated by these linear operations, resulting in O(n).

Space Complexity

O(N) – The algorithm uses a visited set to keep track of all visited nodes during the tree traversal, where N is the number of nodes. In the worst-case scenario, all nodes will be visited, so the visited set can grow up to size N. Additionally, finding potential roots involves iterating through the leftChild and rightChild arrays, which implicitly requires a boolean array of size N. Therefore, the auxiliary space used is proportional to N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input (n = 0)	Return true, as an empty tree is considered valid.
Single node (n = 1)	Return true, as a single node tree is valid.
Multiple roots (more than one node with no parent)	Detect cycles or multiple roots by tracking in-degrees and root count during the validation process, returning false if multiple roots are found.
Cycle in the graph	Use a visited set during traversal to detect cycles, immediately returning false if a cycle is found.
Disconnected graph (forest of trees)	After traversal, check if all nodes have been visited; if not, the graph is disconnected and invalid, returning false.
Self-loop (left or right child points to itself)	During traversal, check if a node points to itself; if so, the tree is invalid, returning false.
Input exceeding maximum constraints (n approaching the limit)	Ensure the algorithm's time and space complexity are within acceptable bounds, and memory usage is carefully monitored.
Integer overflow potential when calculating indegrees or node counts	Use appropriate data types (e.g., long) to prevent integer overflow during calculations.

Empty input (n = 0)

How to Handle:

Return true, as an empty tree is considered valid.

Single node (n = 1)

How to Handle:

Return true, as a single node tree is valid.

Multiple roots (more than one node with no parent)

How to Handle:

Detect cycles or multiple roots by tracking in-degrees and root count during the validation process, returning false if multiple roots are found.

Cycle in the graph

How to Handle:

Use a visited set during traversal to detect cycles, immediately returning false if a cycle is found.

Disconnected graph (forest of trees)

How to Handle:

After traversal, check if all nodes have been visited; if not, the graph is disconnected and invalid, returning false.

Self-loop (left or right child points to itself)

How to Handle:

During traversal, check if a node points to itself; if so, the tree is invalid, returning false.

Input exceeding maximum constraints (n approaching the limit)

How to Handle:

Ensure the algorithm's time and space complexity are within acceptable bounds, and memory usage is carefully monitored.

Integer overflow potential when calculating indegrees or node counts

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow during calculations.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of values for the node values (0 to n-1, or other)?
Can a node have more than one parent? Or is it guaranteed to be a tree structure, even if not valid?
If the input represents multiple disjoint trees, should I return `false`?
What should I return if the input `n` is zero or the arrays are empty?
Are there any memory constraints given the size of `n`?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, we need to figure out which node, if any, could be the root of our potential tree. A root is a node that no other node points to as a child.
If we find more than one potential root, then it can't be a valid tree, so we're done.
Next, starting from our potential root, we will explore every node to see if we can reach every other node. This is like tracing every path from the root and checking each node to see that every connection can be established without creating loops or invalid connections.
While exploring, we will mark each node as visited. If we try to visit a node that has already been visited, that means there's a cycle, and it's not a valid tree.
Also, if any node has more than one parent, then it's not a valid tree, and we can stop.
If we reach a point where we cannot find a single root node, it also can't be a valid tree, and we are done.
If we explore the entire structure and find no multiple roots, cycles, or nodes with multiple parents, and every node is reachable from the single identified root, we can conclude it's a valid tree.

Code Implementation

def validate_binary_tree_nodes(number_of_nodes, left_child, right_child):
    parents = [0] * number_of_nodes

    # Find parents for all nodes
    for i in range(number_of_nodes):
        if left_child[i] != -1:
            if parents[left_child[i]] != 0:
                return False
            parents[left_child[i]] = i + 1
        if right_child[i] != -1:
            if parents[right_child[i]] != 0:
                return False
            parents[right_child[i]] = i + 1

    roots = []
    for i in range(number_of_nodes):
        if parents[i] == 0:
            roots.append(i)

    # Check for multiple roots
    if len(roots) != 1:
        return False

    root = roots[0]
    visited = [False] * number_of_nodes
    stack = [root]
    count = 0

    # Use DFS to traverse the tree and check reachability and cycles
    while stack:
        node = stack.pop()
        if visited[node]:
            return False

        visited[node] = True
        count += 1

        if left_child[node] != -1:
            stack.append(left_child[node])
        if right_child[node] != -1:
            stack.append(right_child[node])

    # Verify all nodes were visited
    return count == number_of_nodes

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, identify potential root nodes. A root node is a node that isn't a child of any other node. We can find these by checking which nodes are *not* listed as a left or right child in the given information.
If there are multiple potential root nodes, it means the nodes are disconnected, and we immediately know it's not a valid tree.
Choose one of the valid root nodes and start exploring the tree by following the left and right child connections.
As we explore, keep track of all the nodes we visit. Each node should only be visited once. If we ever visit a node a second time, it means there's a cycle, which makes it invalid.
Also, as we explore, ensure that every node we reach actually exists in the list of available nodes. If we can't find the node, this tree isn't valid.
Once we've explored as far as we can from the root, check if we've visited all the nodes. If there are nodes that we didn't reach, the tree is disconnected and therefore invalid.
If we were able to reach all nodes from a single root without visiting any node more than once, the tree is valid.

Code Implementation

def validate_binary_tree_nodes(number_of_nodes, left_children, right_children):
    children = left_children + right_children
    potential_roots = []
    for node_index in range(number_of_nodes):
        if node_index not in children:
            potential_roots.append(node_index)

    if len(potential_roots) != 1:
        return False

    root_node = potential_roots[0]
    visited_nodes = set()
    nodes_to_visit = [root_node]

    while nodes_to_visit:
        current_node = nodes_to_visit.pop()

        if current_node in visited_nodes:
            return False

        visited_nodes.add(current_node)

        left_child = left_children[current_node]
        if left_child != -1:
            nodes_to_visit.append(left_child)

        right_child = right_children[current_node]
        if right_child != -1:
            nodes_to_visit.append(right_child)

    # Must check if all nodes are reachable
    if len(visited_nodes) != number_of_nodes:
        return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input (n = 0)	Return true, as an empty tree is considered valid.
Single node (n = 1)	Return true, as a single node tree is valid.
Multiple roots (more than one node with no parent)	Detect cycles or multiple roots by tracking in-degrees and root count during the validation process, returning false if multiple roots are found.
Cycle in the graph	Use a visited set during traversal to detect cycles, immediately returning false if a cycle is found.
Disconnected graph (forest of trees)	After traversal, check if all nodes have been visited; if not, the graph is disconnected and invalid, returning false.
Self-loop (left or right child points to itself)	During traversal, check if a node points to itself; if so, the tree is invalid, returning false.
Input exceeding maximum constraints (n approaching the limit)	Ensure the algorithm's time and space complexity are within acceptable bounds, and memory usage is carefully monitored.
Integer overflow potential when calculating indegrees or node counts	Use appropriate data types (e.g., long) to prevent integer overflow during calculations.

Empty input (n = 0)

How to Handle:

Return true, as an empty tree is considered valid.

Single node (n = 1)

How to Handle:

Return true, as a single node tree is valid.

Multiple roots (more than one node with no parent)

How to Handle:

Detect cycles or multiple roots by tracking in-degrees and root count during the validation process, returning false if multiple roots are found.

Cycle in the graph

How to Handle:

Use a visited set during traversal to detect cycles, immediately returning false if a cycle is found.

Disconnected graph (forest of trees)

How to Handle:

After traversal, check if all nodes have been visited; if not, the graph is disconnected and invalid, returning false.

Self-loop (left or right child points to itself)

How to Handle:

During traversal, check if a node points to itself; if so, the tree is invalid, returning false.

Input exceeding maximum constraints (n approaching the limit)

How to Handle:

Ensure the algorithm's time and space complexity are within acceptable bounds, and memory usage is carefully monitored.

Integer overflow potential when calculating indegrees or node counts

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow during calculations.