I have a code that is supposed to output whether a tree is balanced or unbalanced. The input format is id w id_l d_l id_r d_r. I have to store the root of the tree in a variable. import java.util.*; import java.io.*; public class Solution { static class Node { int id; int weight; Node leftChild; Node rightChild; int leftDistance = -1; int rightDistance = -1; public Node(int id, int weight) { this.id = id; this.weight = weight; this.leftDistance = leftDistance; this.rightDistance = rightDistance; } } // Method to read input and create tree public static Node createTree() { Scanner sc = new Scanner(System.in); Map map = new HashMap<>(); Node root = null; // check all nodes while (sc.hasNextInt()) { int id = sc.nextInt(); int w = sc.nextInt(); // weight int id_l = sc.nextInt(); // id of the node's left child int d_l = sc.nextInt(); // distance of the node's left subtree from the pivot point int id_r = sc.nextInt(); // id of the node's right child int d_r = sc.nextInt(); // distance of the node's right subtree from the pivot point Node node = map.get(id); if (node == null) { node = new Node(id, w); map.put(id, node); } else { node.weight = w; } // leftChild input doesn't equal -1 if (id_l != -1) { Node leftChild = map.get(id_l); if (leftChild == null) { leftChild = new Node(id_l, w); map.put(id_l, leftChild); } node.leftChild = leftChild; node.leftDistance = d_l; } // rightChild input doesn't equal -1 if (id_r != -1) { Node rightChild = map.get(id_r); if (rightChild == null) { rightChild = new Node(id_r, w); map.put(id_r, rightChild); } node.rightChild = rightChild; node.rightDistance = d_r; } if (root == null) { root = node; } } // return root of tree return root; } // Recursive method to determine if tree is balanced public static int isBalanced(Node node) { if (node.leftChild == null && node.rightChild == null) { return node.weight; } int leftWeight = 0; int rightWeight = 0; int Weight = 0; if (node.leftChild != null) { leftWeight = isBalanced(node.leftChild); } if (node.rightChild != null) { rightWeight = isBalanced(node.rightChild); } // Calculate torques int leftTorque = leftWeight * node.leftDistance; int rightTorque = rightWeight * node.rightDistance; if (leftTorque == rightTorque) { Weight = leftWeight + rightWeight + node.weight; // Weight of balanced tree } else { Weight = -1; // Unbalanced tree } return Weight; } public static void main(String[] args) { Node root = createTree(); int result = isBalanced(root); if (result == -1) { System.out.println("Unbalanced"); } else { System.out.println("Balanced"); } } } It's not working correctly, for example the input given below is supposed to output unbalanced meaning isBalanced needs to return -1. My code keeps saying that it is balanced. I wanted ask why my code is incorrect and how to fix it to work correctly. The constraints is that I have to use a TreeMap or hashMap to consctruct the tree and use a recursive method that takes one pass through the tree to determine if it is balanced. 9 3 -1 -1 -1 -1 12 14 23 15 94 5 23 1 -1 -1 -1 -1 35 1 56 10 9 20 41 5 12 10 35 20 56 2 77 1 88 1 77 2 -1 -1 -1 -1 88 2 -1 -1 -1 -1 94 3 -1 -1 -1 -1
I have a code that is supposed to output whether a tree is balanced or unbalanced. The input format is id w id_l d_l id_r d_r. I have to store the root of the tree in a variable.
import java.util.*;
import java.io.*;
public class Solution {
static class Node {
int id;
int weight;
Node leftChild;
Node rightChild;
int leftDistance = -1;
int rightDistance = -1;
public Node(int id, int weight) {
this.id = id;
this.weight = weight;
this.leftDistance = leftDistance;
this.rightDistance = rightDistance;
}
}
// Method to read input and create tree
public static Node createTree() {
Scanner sc = new Scanner(System.in);
Map<Integer, Node> map = new HashMap<>();
Node root = null;
// check all nodes
while (sc.hasNextInt()) {
int id = sc.nextInt();
int w = sc.nextInt(); // weight
int id_l = sc.nextInt(); // id of the node's left child
int d_l = sc.nextInt(); // distance of the node's left subtree from the pivot point
int id_r = sc.nextInt(); // id of the node's right child
int d_r = sc.nextInt(); // distance of the node's right subtree from the pivot point
Node node = map.get(id);
if (node == null) {
node = new Node(id, w);
map.put(id, node);
} else {
node.weight = w;
}
// leftChild input doesn't equal -1
if (id_l != -1) {
Node leftChild = map.get(id_l);
if (leftChild == null) {
leftChild = new Node(id_l, w);
map.put(id_l, leftChild);
}
node.leftChild = leftChild;
node.leftDistance = d_l;
}
// rightChild input doesn't equal -1
if (id_r != -1) {
Node rightChild = map.get(id_r);
if (rightChild == null) {
rightChild = new Node(id_r, w);
map.put(id_r, rightChild);
}
node.rightChild = rightChild;
node.rightDistance = d_r;
}
if (root == null) {
root = node;
}
}
// return root of tree
return root;
}
// Recursive method to determine if tree is balanced
public static int isBalanced(Node node) {
if (node.leftChild == null && node.rightChild == null) {
return node.weight;
}
int leftWeight = 0;
int rightWeight = 0;
int Weight = 0;
if (node.leftChild != null) {
leftWeight = isBalanced(node.leftChild);
}
if (node.rightChild != null) {
rightWeight = isBalanced(node.rightChild);
}
// Calculate torques
int leftTorque = leftWeight * node.leftDistance;
int rightTorque = rightWeight * node.rightDistance;
if (leftTorque == rightTorque) {
Weight = leftWeight + rightWeight + node.weight; // Weight of balanced tree
}
else {
Weight = -1; // Unbalanced tree
}
return Weight;
}
public static void main(String[] args) {
Node root = createTree();
int result = isBalanced(root);
if (result == -1) {
System.out.println("Unbalanced");
} else {
System.out.println("Balanced");
}
}
}
It's not working correctly, for example the input given below is supposed to output unbalanced meaning isBalanced needs to return -1. My code keeps saying that it is balanced. I wanted ask why my code is incorrect and how to fix it to work correctly. The constraints is that I have to use a TreeMap or hashMap to consctruct the tree and use a recursive method that takes one pass through the tree to determine if it is balanced.
9 3 -1 -1 -1 -1
12 14 23 15 94 5
23 1 -1 -1 -1 -1
35 1 56 10 9 20
41 5 12 10 35 20
56 2 77 1 88 1
77 2 -1 -1 -1 -1
88 2 -1 -1 -1 -1
94 3 -1 -1 -1 -1
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
