Example - Binary Tree Data-structure
I have solved 1 problem in online coding competition.
Problem in short - print number of leaf nodes.
inputs -
1. N = number of nodes in binary tree (this is not BST).
2. A = array of integers representing values for each node in tree.
3. X = position in A, node at position X having value A[x] should be deleted along with its subtree from tree.
conditions -
1<=N<=100
-1<=A[i]<=N-1
0<=X<=N-1
all values in A will be duplicate ones except -1. -1 in A will always represent root value.
keep filling binary tree as - node then node.left then node.right then node.left.left then node.left.right then node.right.left and so on.
sample -
when input =
5
-1 0 0 1 1
2
output should be = 2
when input =
11
0 0 -1 2 2 2 2 3 3 3 3
4
output should be = 4 enter image description here my correctly working code =
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Techgig_BinaryTree {
private Queue<Node> leafs;
private Node root;
private int height; //etc properties
public Techgig_BinaryTree() {
leafs = new LinkedList<Node>();
root = null;
height = 0;
}
public Techgig_BinaryTree(Node root) {
this.root = root;
leafs = new LinkedList<Node>();
leafs.add(root);
}
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
public Queue<Node> getLeafs() {
return leafs;
}
public int getHeight() {
return height;
}
public static void main(String[] args) {
System.out.println("provide number of nodes(N)"
+ " then provide elements of tree(A[])"
+ " then position of node to delete along with subtree(X)");
try {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int A[] = new int[N];
for(int i=0;i < N; i++)
A[i] = in.nextInt();
int X = in.nextInt();
in.close();
System.out.println("received arr");
for(int i=0;i < N; i++)
System.out.println(A[i]);
//1<=N<=100
//-1<=A[i]<=N-1
//0<=X<=N-1
boolean isRightInput = false;
if(N>=1 && N<=100) {
isRightInput = true;
for(int val : A) {
if(val>=-1 && val<=N-1) {}
else isRightInput = false;
}
if(isRightInput==true && X>=0 && X<(N-1)) {}
}
if(isRightInput) {
Techgig_BinaryTree bt = new Techgig_BinaryTree().createBT(A);
bt.deleteNodeAndSubtree(A, X);
System.out.println(bt.calculateLeafNodes());
}
} catch (Exception e) {
// TODO: handle exception : no details provided about handling yet.
e.printStackTrace();
}
}
//get leaf nodes
public int calculateLeafNodes() {
int leafCount =0;
for (Node node : leafs) {
if(node.left==null && node.right==null)
leafCount++;
}
return leafCount;
}
//create binary tree
public Techgig_BinaryTree createBT(int A[]) {
Techgig_BinaryTree bt = new Techgig_BinaryTree();
int rootPos=-1;
//set root. root is always -1 so loop till get -1.
//when A[] has all unique values then we can directly start adding. No need of position in Node.
for(int i=0; i<A.length; i++)
if(A[i]==-1) {
bt.root = new Node(i, A[i]);
bt.leafs.add(bt.root);
rootPos = i;
break;
}
//set other tree now skipping rootPos in array.
for(int i=0; i<A.length; i++) {
if(i==rootPos) continue;
System.out.println("i="+i+" possible-leafs="+ bt.leafs.toString());
Node newNode = new Node(i, A[i]);
bt.addNode(newNode);
}
return bt;
}
//private sub-method to create bin tree
private boolean addNode(Node newNode) {
boolean isSuccess = false;
while(!isSuccess) {
Iterator<Node> i = this.leafs.iterator();
if(i.hasNext()) {
Node n = i.next();
if(n.left==null) {
n.left = newNode;
isSuccess = true;
}
else if(n.right==null) {
n.right = newNode;
isSuccess = true;
}
}
if(isSuccess) {
this.leafs.add(newNode);
System.out.println("new node added. leaf-"+leafs);
break;
}
else
this.leafs.remove();
System.out.println("removed. leaf-"+ leafs);
}
return isSuccess;
}
public Techgig_BinaryTree deleteNodeAndSubtree(int arr[], int D) {
Node node = new Node(D, arr[D]);
if (deleteNode(this.root, node))
updateLeafNodes();
return this;
}
public boolean updateLeafNodes() {
boolean isSucecss = false;
LinkedList<Node> list = new LinkedList<Node>();
list.add(root);
int tracer = 0;
while(tracer!=list.size()) {
if(list.get(tracer).left!=null && list.get(tracer).right!=null) {
list.add(list.get(tracer).left);
list.add(list.get(tracer).right);
list.remove(tracer);
} else if (list.get(tracer).left!=null && list.get(tracer).right==null) {
list.add(list.get(tracer).left);
tracer++;
} else if (list.get(tracer).right!=null && list.get(tracer).left==null) {
list.add(list.get(tracer).right);
tracer++;
} else {
tracer++;
}
}
if(tracer==list.size()) {
this.leafs = list;
isSucecss= true;
}
return isSucecss;
}
//search node in this tree
public boolean searchNode(Node treeNode, Node node) {
boolean isFound = false;
if(treeNode!=null && treeNode.position==node.position && treeNode.val==node.val) {
isFound = true;
System.err.println("found="+treeNode);
}
else {
if(treeNode.left!=null)
isFound = searchNode(treeNode.left, node);
if (!isFound && treeNode.right!=null) {
isFound = searchNode(treeNode.right, node);
}
}
return isFound;
}
private boolean deleteNode(Node treeNode, Node node) {
boolean isDelete = false;
//leaf node found. still node not found.
if(treeNode.getLeft()==null && treeNode.right == null) return isDelete;
//node to be deleted is left child of treeNode
if(treeNode.getLeft()!=null && treeNode.getLeft().position==node.position && treeNode.getLeft().val==node.val) {
treeNode.setLeft(null);
if(!searchNode(this.root, node))
isDelete = true;
}
//node to be deleted is left child of treeNode
else if(treeNode.getRight()!=null && treeNode.getRight().position==node.position && treeNode.getLeft().val==node.val) {
treeNode.setRight(null);
if(!searchNode(this.root, node))
isDelete = true;
}
//go further level
if(!isDelete && treeNode.left!=null)
isDelete = deleteNode(treeNode.left, node);
if(!isDelete && treeNode.right!=null)
isDelete = deleteNode(treeNode.right, node);
return isDelete;
}
//data-structure for node of tree
class Node{
private int position, val; //taking position as val are repeating in my BT
Node left, right;
//create simple node
public Node(int position, int val) {
this.position = position;
this.val = val;
this.left = null;
this.right = null;
}
public Node(int position, int val, Node left, Node right) {
this.position = position;
this.val = val;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return "[("
+position+","+val
+")-(isLeft-"+(left!=null)+",isRight-"+(right!=null)
+")]";
}
public int getPosition() {
return position;
}
public int getVal() {
return val;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right) {
this.right = right;
}
}
}
Problem =
Code works fine for given inputs as well as customized inputs. But this code scored only 40/100 in the competition. The code score remains same ie. 40 with and without try-catch, constructors, setters-getters.
score chart shows some test-cases failed. however, test-case details are not given.
How to improve code score in java coding competition ?
Aucun commentaire:
Enregistrer un commentaire