In the world of competitive programming, Leetcode stands as a ubiquitous platform where aspiring developers and programmers sharpen their skills. It offers a wide array of problems that challenge your ability to think critically and come up with innovative solutions. One such problem is Leetcode 1361 – “Validate Binary Tree Nodes.” This problem not only tests your coding prowess but also your understanding of data structures and algorithms. In this blog post, we’re going to explore a Breadth-First Search (BFS) approach to validate binary tree nodes in the context of Leetcode, providing a clear, step-by-step explanation.

What is Leetcode 1361?

Leetcode 1361 is a problem that belongs to the realm of binary trees, a fundamental concept in computer science. The problem statement revolves around the validation of a binary tree formed by a given set of nodes. The challenge is to determine whether the nodes, along with their parent-child relationships, form a valid binary tree.

1361. Validate Binary Tree Nodes — **Validate Binary Tree Nodes**

BFS Approach

The Code Solution

We’ll dissect this code, explain the algorithm step-by-step, and discuss its efficiency. Full code is present at bottom in C++ , Python ,Java , javascript ,(Other language coming soon and if you have solution the comment solution )

The “isBinaryTreeValid” Function

The isBinaryTreeValid function is the heart of this solution. It employs Breadth-First Search (BFS) to traverse the binary tree efficiently. The code begins by initializing a few essential data structures:

visited: A boolean vector that tracks visited nodes to avoid revisiting them.
nodeQueue: A queue use for BFS traversal.

bool isBinaryTreeValid(int root, vector<int>& leftChild, vector<int>& rightChild) {
    vector<bool> visited(leftChild.size(), false);
    queue<int> nodeQueue;
    nodeQueue.push(root);
    visited[root] = true;

Breadth-First Search

The BFS algorithm starts with the root node, and while there are nodes in the queue, it explores their left and right children. The key points to consider during traversal are:

Checking for cycles: The code ensures that it does not form any cycle during traversal. If a node has already been visit, it returns false as a binary tree does not allow cycles.

// Check left child
if (leftChild[current] != -1) {
    if (visited[leftChild[current]])
        return false;
    nodeQueue.push(leftChild[current]);
    visited[leftChild[current]] = true;
}

// Check right child
if (rightChild[current] != -1) {
    if (visited[rightChild[current]])
        return false;
    nodeQueue.push(rightChild[current]);
    visited[rightChild[current]] = true;
}

After traversal, the code checks if there are not visit components in the tree.. If any node remains unvisited, it means there are multiple components, and the tree is invalid.

for(int i = 0 ; i < visited.size() ; i ++)
    if(!visited[i])
        return false;

If none of the above conditions are meet, the function returns true, indicating that the nodes form a valid binary tree

The “validateBinaryTreeNodes” Function

The validateBinaryTreeNodes function plays a pivotal role in checking the overall validity of the binary tree. It analyzes the parent-child relationships, ensuring that there are no duplicate parents and identifies the root node. Here’s how it works:

childCount: A vector that keeps track of the number of children each node has.

Parent-Child Relationship Analysis

The function first examines the left children and then the right children, updating the childCount vector accordingly. If it detects a node with multiple parents, it immediately returns false, as this violates the binary tree property.

for (auto child : leftChild) {
    if (child != -1)
        childCount[child] = true;
}

for (auto child : rightChild) {
    if (child != -1) {
        if (childCount[child])
            return false;
        childCount[child] = true;
    }
}

Identifying the Root Node

The code also identifies the root node. A valid binary tree should have only one root node. If more than one root is Dedicate , the function returns false.

int root = -1; // Root node
for (int i = 0; i < n; ++i) {
    if (!childCount[i]) {
        if (root == -1)
            root = i; // Set root node if not assign
        else
            return false; // Multiple roots found, not a valid binary tree
    }
}

if (root == -1)
    return false; // No root found, not a valid binary tree

Finally, the function calls isBinaryTreeValid to validate the binary tree using the BFS approach.

Efficiency and Completeness

This code solution effectively addresses Leetcode 1361’s requirements. It efficiently checks for cycles, validates parent-child relationships, and ensures the existence of a single root node. The BFS approach allows it to do so with a time complexity of O(N), where N is the number of nodes in the tree.

Codes :-

Here’s the code without comments in C++, Java, Python, and JavaScript:

C++: BFS appraoch 1361. Validate Binary Tree Nodes

class Solution {
public:
    bool isBinaryTreeValid(int root, vector<int>& leftChild, vector<int>& rightChild) {
        vector<bool> visited(leftChild.size(), false);
        queue<int> nodeQueue;
        nodeQueue.push(root);
        visited[root] = true;

        while (!nodeQueue.empty()) {
            int current = nodeQueue.front();
            nodeQueue.pop();

            if (leftChild[current] != -1) {
                if (visited[leftChild[current]])
                    return false;
                nodeQueue.push(leftChild[current]);
                visited[leftChild[current]] = true;
            }

            if (rightChild[current] != -1) {
                if (visited[rightChild[current]])
                    return false;
                nodeQueue.push(rightChild[current]);
                visited[rightChild[current]] = true;
            }
        }

        for (int i = 0; i < visited.size(); i++)
            if (!visited[i])
                return false;

        return true;
    }

    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        vector<bool> childCount(n, false);

        for (auto child : leftChild) {
            if (child != -1)
                childCount[child] = true;
        }

        for (auto child : rightChild) {
            if (child != -1) {
                if (childCount[child])
                    return false;
                childCount[child] = true;
            }
        }

        int root = -1;
        for (int i = 0; i < n; ++i) {
            if (!childCount[i]) {
                if (root == -1)
                    root = i;
                else
                    return false;
            }
        }

        if (root == -1)
            return false;

        return isBinaryTreeValid(root, leftChild, rightChild);
    }
};

Java:BFS appraoch 1361. Validate Binary Tree Nodes

class Solution {
    public boolean isBinaryTreeValid(int root, int[] leftChild, int[] rightChild) {
        boolean[] visited = new boolean[leftChild.length];
        Queue<Integer> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);
        visited[root] = true;

        while (!nodeQueue.isEmpty()) {
            int current = nodeQueue.poll();

            if (leftChild[current] != -1) {
                if (visited[leftChild[current]])
                    return false;
                nodeQueue.add(leftChild[current]);
                visited[leftChild[current]] = true;
            }

            if (rightChild[current] != -1) {
                if (visited[rightChild[current]])
                    return false;
                nodeQueue.add(rightChild[current]);
                visited[rightChild[current]] = true;
            }
        }

        for (int i = 0; i < visited.length; i++)
            if (!visited[i])
                return false;

        return true;
    }

    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        boolean[] childCount = new boolean[n];

        for (int child : leftChild) {
            if (child != -1)
                childCount[child] = true;
        }

        for (int child : rightChild) {
            if (child != -1) {
                if (childCount[child])
                    return false;
                childCount[child] = true;
            }
        }

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (!childCount[i]) {
                if (root == -1)
                    root = i;
                else
                    return false;
            }
        }

        if (root == -1)
            return false;

        return isBinaryTreeValid(root, leftChild, rightChild);
    }
}

Python:BFS appraoch 1361. Validate Binary Tree Nodes

from collections import deque

class Solution:
    def isBinaryTreeValid(self, root, leftChild, rightChild):
        visited = [False] * len(leftChild)
        nodeQueue = deque()
        nodeQueue.append(root)
        visited[root] = True

        while nodeQueue:
            current = nodeQueue.popleft()

            if leftChild[current] != -1:
                if visited[leftChild[current]]:
                    return False
                nodeQueue.append(leftChild[current])
                visited[leftChild[current]] = True

            if rightChild[current] != -1:
                if visited[rightChild[current]]:
                    return False
                nodeQueue.append(rightChild[current])
                visited[rightChild[current]] = True

        for i in range(len(visited)):
            if not visited[i]:
                return False

        return True

    def validateBinaryTreeNodes(self, n, leftChild, rightChild):
        childCount = [False] * n

        for child in leftChild:
            if child != -1:
                childCount[child] = True

        for child in rightChild:
            if child != -1:
                if childCount[child]:
                    return False
                childCount[child] = True

        root = -1
        for i in range(n):
            if not childCount[i]:
                if root == -1:
                    root = i
                else:
                    return False

        if root == -1:
            return False

        return self.isBinaryTreeValid(root, leftChild, rightChild)

JavaScript:BFS appraoch 1361. Validate Binary Tree Nodes

const validateBinaryTreeNodes = function(n, leftChild, rightChild) {
    const isBinaryTreeValid = (root, leftChild, rightChild) => {
        const visited = new Array(leftChild.length).fill(false);
        const nodeQueue = [root];
        visited[root] = true;

        while (nodeQueue.length > 0) {
            const current = nodeQueue.shift();

            if (leftChild[current] !== -1) {
                if (visited[leftChild[current]]) {
                    return false;
                }
                nodeQueue.push(leftChild[current]);
                visited[leftChild[current]] = true;
            }

            if (rightChild[current] !== -1) {
                if (visited[rightChild[current]]) {
                    return false;
                }
                nodeQueue.push(rightChild[current]);
                visited[rightChild[current]] = true;
            }
        }

        for (let i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                return false;
            }
        }

        return true;
    };

    const childCount = new Array(n).fill(false);

    leftChild.forEach(child => {
        if (child !== -1) {
            childCount[child] = true;
        }
    });

    rightChild.forEach(child => {
        if (child !== -1) {
            if (childCount[child]) {
                return false;
            }
            childCount[child] = true;
        }
    });

    let root = -1;
    for (let i = 0; i < n; i++) {
        if (!childCount[i]) {
            if (root === -1) {
                root = i;
            } else {
                return false;
            }
        }
    }

    if (root === -1) {
        return false;
    }

    return isBinaryTreeValid(root, leftChild, rightChild);
};

Leetcode Easy Solution

Leetcode 1361 may appear complex at first glance, but with the provide solution, it becomes an easily solvable problem. We have broken down the code step by step, explaining its working, and highlighted the key components that make it a successful and efficient solution.

By grasping the logic behind this solution, you can tackle similar problems on Leetcode with confidence. Binary tree validation is an important concept in computer science and software development, and mastering it is a valuable skill.

Leetcode Explanation in Hindi

Leetcode problems are a valuable resource for programmers of all skill levels. To ensure the content reaches a wider audience, it’s essential to provide explanations in various languages. For Hindi-speaking developers, here’s a brief explanation of the code and problem:

Leetcode 1361: BFS द्वारा बाइनरी ट्री की प्रमाणिकता

आपकी प्रोग्रामिंग क्षमता की जांच और नवाचारी समाधानों के लिए एक महत्वपूर्ण मंच के रूप में, लीटकोड दुनियाभर में स्थित है, जहां उम्मीदवार डेवलपर्स और प्रोग्रामर्स अपनी कौशलता को तेज करते हैं। यह उनकी क्षमता को सोचने और नवाचारी समाध

ान निकालने की क्षमता की जांच करता है। ऐसी ही एक समस्या लीटकोड 1361 है – “बाइनरी ट्री नोड्स की प्रमाणित करें।” यह समस्या आपकी कोडिंग क्षमता को ही ही और डेटा संरचनन और एल्गोरिदम्स की समझ को जांचने में नहीं बल्कि आपके यथार्थ में देखने के लिए आती है। इस ब्लॉग पोस्ट में, हम एक चौड़ाई-पूरी चरणों वाली स्पष्ट व्याख्या प्रदान करके लीटकोड के संदर्भ में बाइनरी ट्री नोड्स की पुष्टि करने के लिए एक ब्रेड्थ-फर्स्ट सर्च (BFS) द्वारा दर्शन करेंगे।

Explaining the Code Step-by-Step

Let’s explore the code and the problem in detail.

Code Snippet	Explanation
`class Solution {`	The code defines a C++ class called “Solution” that encapsulates the solution to the problem.
`public:`	This keyword signifies that the subsequent functions and variables are accessible from outside the class.
`bool isBinaryTreeValid(int root, vector<int>& leftChild, vector<int>& rightChild) {`	This function is responsible for validating whether the given nodes form a valid binary tree. It takes the root node and the left and right child vectors as inputs. The function returns a boolean value indicating the validity of the binary tree.
`vector<bool> visited(leftChild.size(), false);`	A vector of booleans is created to keep track of visited nodes. It has the same size as the “leftChild” vector and is initialized with “false” values.
`queue<int> nodeQueue;`	A queue is used to perform BFS traversal.
`nodeQueue.push(root);`	The root node is pushed into the queue to start the traversal from the root.
`visited[root] = true;`	The “visited” vector is updated to mark the root node as visited.
`while (!nodeQueue.empty()) {`	A while loop begins, which continues as long as there are nodes in the queue. This loop is the core of the BFS traversal.
`int current = nodeQueue.front();`	The front element of the queue is assigned to the variable “current.”
`nodeQueue.pop();`	The front node is removed from the queue as it is being processed.
`if (leftChild[current] != -1) {`	This condition checks if the current node has a left child. If it does, the code proceeds to validate it.
`if (visited[leftChild[current]])`	This condition checks if the left child has been visited before. If it has, it indicates a cycle in the tree, and the function returns “false.”
`nodeQueue.push(leftChild[current]);`	The left child is pushed into the queue for further traversal.
`visited[leftChild[current]] = true;`	The “visited” vector is updated to mark the left child as visited.
`if (rightChild[current] != -1) {`	This condition checks if the current node has a right child. If it does, the code proceeds to validate it.
`if (visited[rightChild[current]])`	Similar to the left child, this condition checks if the right child has been visited before. If it has, it indicates a cycle in the tree, and the function returns “false.”
`nodeQueue.push(rightChild[current]);`	The right child is pushed into the queue for further traversal.
`visited[rightChild[current]] = true;`	The “visited” vector is updated to mark the right child as visited.
`for(int i = 0 ; i < visited.size() ; i ++)`	After the BFS traversal, the code checks if there are unvisited nodes in the tree.
`if(!visited[i])`	If any node remains unvisited, it indicates the presence of multiple components in the tree, which is not allowed in a binary tree, and the function returns “false.”
`return true;`	If none of the above conditions are met, the function returns “true,” indicating that the given nodes form a valid binary tree.
`}`	The “isBinaryTreeValid” function ends here.

Visualizing the BFS Approach

To better understand the code and the BFS approach, let’s visualize how BFS traverses a binary tree. Consider the following binary tree:

Here, we’ll start the BFS traversal from the root node, which is node 1. The process unfolds as follows:

Node 1 is push into the queue, and it’s mark as visit.
Node 1 is process and removed from the queue. The left child, node 2, is push into the queue and marked as visit.

Node 2 is process and remove from the queue. Its children, nodes 4 and 5, are push into the queue and mark as visit.
Nodes 3, 4, and 5 are process in order. At this point, all nodes have been visit, and the traversal is complete.

This visualization helps you understand how BFS explores a binary tree level by level and ensures that no cycles are present.

Validating Parent-Child Relationships

The validateBinaryTreeNodes function is responsible for validating the parent-child relationships and ensuring that the tree has a single root. It uses the childCount vector to keep track of the number of children each node has.

Code Snippet	Explanation
`vector<bool> childCount(n, false);`	A vector of booleans is created to keep track of the number of children each node has. It has the same size as the number of nodes in the tree and is initialized with “false” values.
`for (auto child : leftChild) {`	The code first examines the left children.
`if (child != -1)`	It checks if a node has a left child.
`childCount[child] = true;`	If a node has a left child, it marks the left child as having a parent by setting the corresponding value in the “childCount” vector to “true.”
`for (auto child : rightChild) {`	Similarly, the code examines the right children.
`if (child != -1)`	It checks if a node has a right child.
`if (childCount[child])`	If a node has a right child and the right child already has a parent (as indicated by the “childCount” vector), it returns “false” as this violates the binary tree property.
`int root = -1;`	A variable “root” is initialized to -1, indicating that the root node hasn’t been assigned yet.
`for (int i = 0; i < n; ++i) {`	The code iterates through all nodes in the tree.
`if (!childCount[i]) {`	If a node has no children (i.e., no parents as per the “childCount” vector), it is considered a potential root.
`if (root == -1)`	If the “root” variable is still -1, it means that no root has been assigned yet.
`root = i;`	In this case, the current node is assigned as the root.
`else`	If the “root” variable is not -1, it means that a root has already been assigned.
`return false;`	In this scenario, the function returns “false” because multiple roots violate the binary tree property.
`}`	The loop ends, and the code checks whether a root has been assigned.
`if (root == -1)`	If the “root” variable is still -1, it means that no root has been assigned.
`return false;`	In this case, the function returns “false” because a valid binary tree must have a root.
`return isBinaryTreeValid(root, leftChild, rightChild);`	Finally, if a root has been assigned, the function calls the “isBinaryTreeValid” function to check the validity of the binary tree using the BFS approach.

Efficiencies and Completeness

The code efficiently addresses the requirements of Leetcode 1361. It checks for cycles, validates parent-child relationships, and ensures the existence of a single root. The BFS approach allows it to do so with a time complexity of O(N), where N is the number of nodes in the tree.

Conclusion

Leetcode 1361, often seen as a challenging problem, becomes manageable with the provided solution. We’ve meticulously explained the code, step by step, clarifying its inner workings and highlighting the crucial components that make it a successful and efficient solution.

By grasping the logic behind this solution, you can confidently tackle similar problems on Leetcode. Mastering the art of binary tree validation is not just an achievement; it’s a valuable skill that will serve you well in your programming journey.

Incorporating efficient algorithms and data structures, such as BFS, is essential for solving complex problems in competitive programming and real-world scenarios. So, keep coding, keep exploring, and keep growing as a programmer. Happy coding!

Leetcode 1361. Validate Binary Tree Nodes (Medium)