Java Binary Tree. Printing InOrder traversal

Question

I am having some problems printing an inOrder traversal of my binary tree. Even after inserting many items into the tree it's only printing 3 items.

public class BinaryTree {

    private TreeNode root;
    private int size;

    public BinaryTree(){
        this.size = 0;
    }

    public boolean insert(TreeNode node){

        if( root == null)
            root = node;

        else{
            TreeNode parent = null;
            TreeNode current = root;
            while( current != null){
                if( node.getData().getValue().compareTo(current.getData().getValue()) <0){
                    parent = current;
                    current = current.getLeft();
                }
                else if( node.getData().getValue().compareTo(current.getData().getValue()) >0){
                    parent = current;
                    current = current.getRight();
                }
                else
                    return false;

                if(node.getData().getValue().compareTo(parent.getData().getValue()) < 0)
                    parent.setLeft(node);
                else
                    parent.setRight(node);
                }
            }
            size++;
            return true;
        }


    /**
     * 
     */
    public void inOrder(){
        inOrder(root);
    }

    private void inOrder(TreeNode root){
        if( root.getLeft() !=null)
            this.inOrder(root.getLeft());
        System.out.println(root.getData().getValue());

        if( root.getRight() != null)
            this.inOrder(root.getRight());
    }



}

i guess you can call it hw. i'm having a test on binary trees and inOrder traversal might be one of the questions. i'm just trying to brush up on things. — user69514
– user69514, Commented Apr 24, 2010 at 21:23
I highly suggest you don't have a method that takes in a parameter 'root' when the class also has a field 'root'. This makes things very confusing. — Justin Ardini
– Justin Ardini, Commented Apr 24, 2010 at 21:24
Following Justin's comment, I think you should make inOrder(..) a static method. It has nothing to do with the specific tree instance. Actually the inOrder method body seems fine. You should check your insertions maybe. — Eyal Schneider
– Eyal Schneider, Commented Apr 24, 2010 at 21:28

Péter Török · Accepted Answer · 2010-04-24 21:38:16Z

It seems that you are not traversing the tree properly upon insertion, to find the right place for the new node. Right now you are always inserting at one child of the root, because the insertion code is inside the while loop - it should be after it:

public boolean insert(TreeNode node){

    if( root == null)
        root = node;

    else{
        TreeNode parent = null;
        TreeNode current = root;
        while( current != null){
            if( node.getData().getValue().compareTo(current.getData().getValue()) <0){
                parent = current;
                current = current.getLeft();
            }
            else if( node.getData().getValue().compareTo(current.getData().getValue()) >0){
                parent = current;
                current = current.getRight();
            }
            else
                return false;
        }
        if(node.getData().getValue().compareTo(parent.getData().getValue()) < 0)
            parent.setLeft(node);
        else
            parent.setRight(node);
        }

        size++;
        return true;
    }

FRotthowe · Accepted Answer · 2010-04-24 21:36:44Z

You insert method has a problem. It finds the right parent node to attach the new element to, but on the way it messes up the whole tree. You should move the insertion code out of the while loop:

public boolean insert(TreeNode node){

    if( root == null)
        root = node;

    else{
        TreeNode parent = null;
        TreeNode current = root;
        while( current != null){
            if( node.getData().getValue().compareTo(current.getData().getValue()) <0){
                parent = current;
                current = current.getLeft();
            }
            else if( node.getData().getValue().compareTo(current.getData().getValue()) >0){
                parent = current;
                current = current.getRight();
            }
            else
                return false;
        }

        if(node.getData().getValue().compareTo(parent.getData().getValue()) < 0)
            parent.setLeft(node);
        else
            parent.setRight(node);
        }

        size++;
        return true;
    }
}

Vrajendra Singh Mandloi · Accepted Answer · 2017-03-12 04:27:22Z

0

hey fellows here is one simple one.. try this out.. it works for me well...

public void levelOrderTraversal(Node root){
    Queue<Node> queue = new ArrayDeque<Node>();
    if(root == null) {
        return;
    }
    Node tempNode = root;
    while(tempNode != null) {
        System.out.print(tempNode.data + " ");

        if(tempNode.left != null)   queue.add(tempNode.left);
        if(tempNode.right != null)   queue.add(tempNode.right);

        tempNode = queue.poll();
    }
}

answered Mar 12, 2017 at 4:27

Vrajendra Singh Mandloi

791 silver badge12 bronze badges

Collectives™ on Stack Overflow

Java Binary Tree. Printing InOrder traversal

3 Answers 3

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Related