Given N nodes numbered from 0 to n-1, also given the E number of directed edges, determine whether the given nodes all together form a single binary tree or not.
Examples:
Input: N = 4, edges[][] = [[0 1], [0 2], [2 3]]
Output: true
Explanation: Form a single binary tree with a unique root node.Input: N = 4, edges[][] = [[0 1], [0 2], [1 3], [2 3]]
Output: false
Explanation: Not form a single binary tree because they contain a cycle.
Approach: To solve the problem follow the below idea:
To determine if the given nodes form a single binary tree, you can use a Depth-First Search (DFS) algorithm to traverse the graph and check for the following conditions:
- The Graph should be connected
- There should be exactly one node with an in-degree of 0, which will be the root of the binary tree.
- Every other node should have an in-degree of 1 , except for the root node, which should have an in-degree of 0.
- Also for each node the number of childrens should be less than equal to 2.
Steps to Solve the problem:
- In a binary tree, every node (except the root) should have one parent.
- We can use an unordered_map called inDegree to store the in-degree of each node.
- If any node has an in-degree greater than 1, it means it has more than one parent, which violates the binary tree condition rule.
- Similarly, for each parent node, we need to count the number of children it has.
- If any node has more than two children, it also violates the binary tree condition. We use another unordered_map called childrenCount to keep track of this.
- A binary tree should have exactly one root node. We count the number of nodes with an in-degree of 0.
- If there is more than one such node, it means there is more than one root, which is not allowed in a binary tree.
Below is the implementation of the above idea:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;bool isBinaryTree(int N, vector<vector<int> >& edges){ if (N == 0) { return false; } unordered_map<int, int> inDegree; unordered_map<int, int> childrenCount; for (vector<int>& edge : edges) { int from = edge[0]; int to = edge[1]; inDegree[to]++; childrenCount[from]++; if (inDegree[to] > 1 || childrenCount[from] > 2) { // More than two children or more // than one parent, not a binary // tree. return false; } } int rootCount = 0; for (int i = 0; i < N; i++) { if (inDegree[i] == 0) { rootCount++; if (rootCount > 1) { // More than one root, not a // binary tree. return false; } } } return rootCount == 1;}// Drivers codeint main(){ int N = 4; vector<vector<int> > edges = { { 0, 1 }, { 0, 2 }, { 0, 3 } }; // Function Call if (isBinaryTree(N, edges)) cout << "true" << endl; else cout << "false" << endl; return 0;} |
Java
// Java code for the above approach:import java.util.*;class GFG { static boolean isBinaryTree(int N, int[][] edges) { if (N == 0) { return false; } Map<Integer, Integer> inDegree = new HashMap<>(); Map<Integer, Integer> childrenCount = new HashMap<>(); for (int[] edge : edges) { int from = edge[0]; int to = edge[1]; inDegree.put(to, inDegree.getOrDefault(to, 0) + 1); childrenCount.put( from, childrenCount.getOrDefault(from, 0) + 1); if (inDegree.get(to) > 1 || childrenCount.get(from) > 2) { // More than two children or more // than one parent, not a binary // tree. return false; } } int rootCount = 0; for (int i = 0; i < N; i++) { if (inDegree.getOrDefault(i, 0) == 0) { rootCount++; if (rootCount > 1) { // More than one root, not a // binary tree. return false; } } } return rootCount == 1; } // Drivers code public static void main(String[] args) { int N = 4; int[][] edges = { { 0, 1 }, { 0, 2 }, { 0, 3 } }; // Function Call if (isBinaryTree(N, edges)) { System.out.println("true"); } else { System.out.println("false"); } }}// This code is contributed by ragul21 |
Python3
from collections import defaultdictdef is_binary_tree(N, edges): if N == 0: return False in_degree = defaultdict(int) children_count = defaultdict(int) for edge in edges: from_node, to_node = edge in_degree[to_node] += 1 children_count[from_node] += 1 if in_degree[to_node] > 1 or children_count[from_node] > 2: # More than two children or more than one parent, not a binary tree. return False root_count = 0 for i in range(N): if in_degree[i] == 0: root_count += 1 if root_count > 1: # More than one root, not a binary tree. return False return root_count == 1# Driver codeif __name__ == "__main__": N = 4 edges = [[0, 1], [0, 2], [0, 3]] # Function Call if is_binary_tree(N, edges): print("true") else: print("false") # This code is contributed by shivamgupta0987654321 |
C#
// C# Implementationusing System;using System.Collections.Generic;class Program{ static bool IsBinaryTree(int N, int[][] edges) { if (N == 0) { return false; } Dictionary<int, int> inDegree = new Dictionary<int, int>(); Dictionary<int, int> childrenCount = new Dictionary<int, int>(); foreach (int[] edge in edges) { int from = edge[0]; int to = edge[1]; if (!inDegree.ContainsKey(to)) { inDegree[to] = 0; } inDegree[to]++; if (!childrenCount.ContainsKey(from)) { childrenCount[from] = 0; } childrenCount[from]++; if (inDegree[to] > 1 || childrenCount[from] > 2) { // More than two children or more than one parent, not a binary tree. return false; } } int rootCount = 0; for (int i = 0; i < N; i++) { if (!inDegree.ContainsKey(i) || inDegree[i] == 0) { rootCount++; if (rootCount > 1) { // More than one root, not a binary tree. return false; } } } return rootCount == 1; } static void Main(string[] args) { int N = 4; int[][] edges = { new int[] { 0, 1 }, new int[] { 0, 2 }, new int[] { 0, 3 } }; // Function Call if (IsBinaryTree(N, edges)) { Console.WriteLine("true"); } else { Console.WriteLine("false"); } }}// This code is contributed by Sakshi |
Javascript
function GFG(N, edges) { if (N === 0) { return false; } const inDegree = new Map(); const childrenCount = new Map(); for (const edge of edges) { const from = edge[0]; const to = edge[1]; inDegree.set(to, (inDegree.get(to) || 0) + 1); childrenCount.set(from, (childrenCount.get(from) || 0) + 1); if (inDegree.get(to) > 1 || childrenCount.get(from) > 2) { // More than two children or more than one parent // not a binary tree. return false; } } let rootCount = 0; for (let i = 0; i < N; i++) { if (!inDegree.has(i)) { rootCount++; if (rootCount > 1) { // More than one root, not a binary tree. return false; } } } return rootCount === 1;}// Drivers codeconst N = 4;const edges = [ [0, 1], [0, 2], [0, 3]];// Function Callif (GFG(N, edges)) { console.log("true");} else { console.log("false");} |
Output
false
Time complexity: O(N + E), where N is the number of nodes and E is the number of edges.
Auxiliar Space: O(N + E), where N is the number of nodes and E is the number of edges.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
