Binary Tree in Java - why do i have an "empty" node (with a blank String) in my Tree?

Question

Basically, my problem with my code is that somewhere in its implementation it creates a blank node which is then inserted into my binary tree. This node exists, as my sizeOfTree method counts it as such. The code works just fine, the only problem is the node. OK, so here I have defined the TreeNode based on which the Binary Tree is constructed:

    package hr.fer.oop.lab1.prob6;

    public class TreeNode {
    TreeNode left=null;
    TreeNode right=null;
    String data;
    public TreeNode(String data) {
    this.data=data;
    }
    }

And here is the rest of it:

package hr.fer.oop.lab1.prob6;
import hr.fer.oop.lab1.prob6.TreeNode;
public class BinaryTree {
TreeNode root;
public BinaryTree() {
TreeNode node = new TreeNode("");
root=node;
}
public void insert (String data) {
    if (this.root==null) {
        this.root=new TreeNode(data);
        return;
    }
    else {
    TreeNode node = this.root;
    TreeNode parent = new TreeNode("");
    while(node!=null) {
        parent = node;
        if (node.data.compareTo(data)<=0) {
            node=node.left;
        }
        else{
            node=node.right;
        }
    }
        if (parent.data.compareTo(data)<=0) {
            parent.left=new TreeNode(data);
        }
        else {
            parent.right=new TreeNode(data);
        }
    }
    return;
}

private boolean subTreeContainsData(TreeNode node, String data) {
    if ((node.data).compareTo(data)<1E-15) return true;
    TreeNode temp=new TreeNode("");
    temp=node;
    if((temp.left.data).equals("")&&(temp.right.data).equals("")) return false;
    return (subTreeContainsData(temp.left, data)||subTreeContainsData(temp.right, data));
}
private boolean containsData(String data) {
    return subTreeContainsData(root, data);
}
private int sizeOfSubTree(TreeNode node) {
    if (node==null) return 0; 
    return 1 + sizeOfSubTree(node.left) + sizeOfSubTree(node.right);
}
public int sizeOfTree() {
    return sizeOfSubTree(root);
}
private void writeSubTree(TreeNode node) {
    if (node!=null) {
    writeSubTree(node.left);
    System.out.println(node.data);
    writeSubTree(node.right);
    }
    return;
}
public void writeTree() {
    writeSubTree(root);
}
private void reverseSubTreeOrder(TreeNode node) {
    if (node==null) return;
    TreeNode helpNode;
    helpNode=node.left;
    node.left=node.right;
    node.right=helpNode;
    reverseSubTreeOrder(node.left);
    reverseSubTreeOrder(node.right);
}
public void reverseTreeOrder() {
    reverseSubTreeOrder(root);
}
public static void main (String[] args) {
    BinaryTree tree = new BinaryTree();
    tree.insert("Jasna");
    tree.insert("Ana");
    tree.insert("Ivana");
    tree.insert("Anamarija");
    tree.insert("Vesna");
    tree.insert("Kristina");

    System.out.println("Writing tree inorder:");
    tree.writeTree();
    tree.reverseTreeOrder();
    System.out.println("Writing reversed tree inorder:");
    tree.writeTree();
    int size=tree.sizeOfTree();
    System.out.println("Number of nodes in tree is "+size+".");
    boolean found = tree.containsData("Ivana");
    System.out.println("Searched element is found: "+found);
}
}

Much appreciate any help provided.

Eran · Accepted Answer · 2018-10-15 09:35:02Z

2

You create an empty TreeNode in your constructor and make it the root of the tree:

public BinaryTree() {
    TreeNode node = new TreeNode("");
    root=node;
}

Later, in your insert method, your if (this.root==null) condition is always false, so you don't assign the first inserted node to the root.

Just remove it:

public BinaryTree() {
}

answered Oct 15, 2018 at 9:35

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Anonymous Over a year ago

IMHO ought to set root explicitly to null either in the declaration or in the constructor so the reader clearly sees that it can be null (if in the declaration, the entire constructor may be removed is desired).

Collectives™ on Stack Overflow

Binary Tree in Java - why do i have an "empty" node (with a blank String) in my Tree?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related