CODEWITHSUNDEEP
javaalgorithmtreebinary-search-tree
addybist
addybist

Reputation: 699

In order traversal of a trinary search tree

So, I have the following code to insert an element in a trinary search tree (left tree is less, mid is same and right tree is greater)

public void insert (TrinaryTree<T> root, T data) {
    //if the given tree doesn't exist yet
    if (root == null){
        root = new TrinaryTree<T>(data);
    }
    //if the given value is greater, insert to the right
    else if (root.getData().compareTo(data) > 0){
        insert (root.right, data);
    }
    //if the given value is equal, insert to the mid
    else if (root.getData().compareTo(data) == 0) {
        insert (root.mid, data);
    }
    //if the given value is less, insert to the left
    else {
        insert (root.left, data);
    }
}

I then try to print out my tree (in order traversal to check what I've done is correct or not using this - 

public void inorderTraversal (TrinaryTree<T> root){
    if (root != null){
        inorderTraversal(root.getLeft());
        System.out.println(root.getData());
        inorderTraversal(root.getRight());      
    }
}

Now when I try to run the main class, which is this - 

public static void main (String [] args) {
    TrinaryTree<Integer> tree = new TrinaryTree<Integer>(5);
    tree.insert(tree, 4);
    tree.insert(tree, 9);
    tree.insert(tree, 5);
    tree.insert(tree, 7);
    tree.insert(tree, 2);
    tree.insert(tree, 2);       
    tree.inorderTraversal(tree);
}

I just get the output 5. I figured out because the main tree's left and right subtrees are null. I'm not sure as to why this is happening. My insert function works, because I put a print statement into the insert function, and the statement does get printed. Why are the subtrees still null?

Upvotes: 0

Views: 537

Answers (1)

Bal&#225;zs &#201;des
Bal&#225;zs &#201;des

Reputation: 13807

Look at the code of insert! Once you call it with a null value (you want to put something to the left or right), then most likely everything is null.

  • The root.left and root.right are (probably) null, and your code wont add the freshly created node to the node one level above.
  • The value you call compareTo on is probably null (No NPE?)

The most important thing is, that when you call insert with the uninitialized value (left or right), your code will create a TrinaryTree node, but it wont be able to add it to it's parent (what you probably intended to do), and the freshly created node will garbage collected after the method call.

Upvotes: 1

Related Questions