# Leetcode 1361. Validate Binary Tree Nodes (Medium)

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.

# 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;``````

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];
visited[root] = true;

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

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

if (rightChild[current] != -1) {
if (visited[rightChild[current]])
return false;
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.

## 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:

``````        1
/ \
2   3
/ \
4   5``````

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

1. Node 1 is push into the queue, and it’s mark as visit.
2. Node 1 is process and removed from the queue. The left child, node 2, is push into the queue and marked as visit.
3. Node 2 is process and remove from the queue. Its children, nodes 4 and 5, are push into the queue and mark as visit.
4. 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.

## 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! I am Nilesh,3+ years Exp of SEO, content writing, and keyword research. Also rocks it as a software dev with skills in OS, web dev, Flask, Python, C++, data structures, and algorithms. 3 on Leetcode, 5*on Hackerrank more platform.