For this problem, we will say that a binary tree is visually appealing if for ev

Question

For this problem, we will say that a binary tree is visually appealing if for every node in the tree, the differ- ence of the height of the left subtree and the right subtree of that node is at most one. Input. The input consists of multiple lines. The first line contains one integer, n, that indicates the number of nodes in the tree. The next n lines represent the n nodes of the tree. Each of these lines consists of four space-separated tokens. The first token is a string representing the label of the node. The second token is an integer representing the value of the node. The third and the fourth tokens are strings representing respectively the labels of the left and right children of the current node. The string “NONE” is used in place of the third and/or fourth tokens if a node does not have a left and/or a right child. Sample input: 4 A5BD B 3 C NONE C 7 NONE NONE D 1 NONE NONE Output. The output consists of a single line. If the tree is visually appealing, the program should output “The binary tree IS visually appealing.” (without the quotes) on a single line. If the tree is not visually appealing, the program should print “The binary tree IS NOT visually appealing.” (without the quotes) on a single line. Sample output (for the above input): The three IS visually appealing. (a) Design and implement a Java program that reads a binary tree and determines whether that binary is visually appealing.    For this problem, we will say that a binary tree is visually appealing if for every node in the tree, the differ- ence of the height of the left subtree and the right subtree of that node is at most one. Input. The input consists of multiple lines. The first line contains one integer, n, that indicates the number of nodes in the tree. The next n lines represent the n nodes of the tree. Each of these lines consists of four space-separated tokens. The first token is a string representing the label of the node. The second token is an integer representing the value of the node. The third and the fourth tokens are strings representing respectively the labels of the left and right children of the current node. The string “NONE” is used in place of the third and/or fourth tokens if a node does not have a left and/or a right child. Sample input: 4 A5BD B 3 C NONE C 7 NONE NONE D 1 NONE NONE Output. The output consists of a single line. If the tree is visually appealing, the program should output “The binary tree IS visually appealing.” (without the quotes) on a single line. If the tree is not visually appealing, the program should print “The binary tree IS NOT visually appealing.” (without the quotes) on a single line. Sample output (for the above input): The three IS visually appealing. (a) Design and implement a Java program that reads a binary tree and determines whether that binary is visually appealing.    For this problem, we will say that a binary tree is visually appealing if for every node in the tree, the differ- ence of the height of the left subtree and the right subtree of that node is at most one. Input. The input consists of multiple lines. The first line contains one integer, n, that indicates the number of nodes in the tree. The next n lines represent the n nodes of the tree. Each of these lines consists of four space-separated tokens. The first token is a string representing the label of the node. The second token is an integer representing the value of the node. The third and the fourth tokens are strings representing respectively the labels of the left and right children of the current node. The string “NONE” is used in place of the third and/or fourth tokens if a node does not have a left and/or a right child. Sample input: 4 A5BD B 3 C NONE C 7 NONE NONE D 1 NONE NONE Output. The output consists of a single line. If the tree is visually appealing, the program should output “The binary tree IS visually appealing.” (without the quotes) on a single line. If the tree is not visually appealing, the program should print “The binary tree IS NOT visually appealing.” (without the quotes) on a single line. Sample output (for the above input): The three IS visually appealing. (a) Design and implement a Java program that reads a binary tree and determines whether that binary is visually appealing.   

Explanation / Answer

import java.util.*;

class Node
{
String value;
Node left, right;
Node(String d)
{
value = d;
left = right = null;
}
}
  
class BinaryTree
{
Node root;
  
/* Returns true if binary tree with root as root is height-balanced */
boolean isBalanced(Node node)
{
int lh; /* for height of left subtree */
  
int rh; /* for height of right subtree */
  
/* If tree is empty then return true */
if (node == null)
return true;
  
/* Get the height of left and right sub trees */
lh = height(node.left);
rh = height(node.right);
  
if (Math.abs(lh - rh) <= 1
&& isBalanced(node.left)
&& isBalanced(node.right))
return true;
  
else /* If we reach here then tree is not height-balanced */
return false;
}
  
  
// This function is to compute the "height" of the tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.
int height(Node node)
{
/* base case tree is empty */
if (node == null)
return 0;
  
/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + Math.max(height(node.left), height(node.right));
}
  
static void getinput(int i)
{
String val;
Scanner sc= new Scanner(System.in);
BinaryTree tree = new BinaryTree();
  
if(i==0)
{
System.out.println("Enter the root node "+i+ ": ");
val =sc.next();
tree.root = new Node(val);
}  
else if (i==1 || i==2)
{
if(i==1)
{
System.out.println("Enter the root node "+i+ ": ");
val =sc.next();
tree.root.right = new Node(val);
}
if(i==2)
{
System.out.println("Enter the root node "+i+ ": ");
val =sc.next();
tree.root.left = new Node(val);
}
}
else if (i==3)
{
System.out.println("Enter the root node "+i+ ": ");
val =sc.next();
if (val!="NONE")
tree.root.left.left = new Node(val);
else
tree.root.left.left = null;  
}
else if (i==4)
{
System.out.println("Enter the root node "+i+ ": ");
val =sc.next();
if (val!="NONE")
tree.root.left.right = new Node(val);
else
tree.root.left.right = null;  
}
else if (i==5)
{
System.out.println("Enter the root node "+i+ ": ");
val =sc.next();
if (val!="NONE")
tree.root.right.left = new Node(val);
else
tree.root.right.left = null;  
}
else if (i==6)
{
System.out.println("Enter the root node "+i+ ": ");
val =sc.next();
if (val!="NONE")
tree.root.left.left.left = new Node(val);
else
tree.root.left.left.left = null;  
}
else if (i==7)
{
System.out.println("Enter the root node "+i+ ": ");
val =sc.next();
if (val!="NONE")
tree.root.left.left.right = new Node(val);
else
tree.root.left.left.right = null;  
}

}
  
public static void main(String args[])
{
Scanner sc= new Scanner(System.in);
BinaryTree tree = new BinaryTree();
  
int num =7;
System.out.println("Enter the number of nodes: ");
System.out.println("Default number of node is 7 max.. If ok press 1 else any number to continue with less number of nodes");
int chc=sc.nextInt();
if (chc!=1)
num=sc.nextInt(); // accept the number of nodes
  
int i=0;
  
  
while(i<7)
{
getinput(i);
  
i++;
}
if(tree.isBalanced(tree.root))
System.out.println("Tree is visually appealing");
else
System.out.println("Tree is not visually appealing");
}
}

output
----------------------------
Enter the number of nodes:
Default number of node is 7 max.. If ok press 1 else any number to continue with less number of nodes
1
Enter the root node 0:
12
Enter the node 1:
2
Enter the node 2:
34
Enter the node 3:
2
Enter the node 4:
6
Enter the node 5:
NONE
Enter the node 6:
10
Enter the node 7:
NONE

Tree is not visually appealing

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.