Java: binary tree recursion methods

Question

I'm quite new to java and one of our assignments requires me to create a binary tree containing nodes with int values. My professor wants us to use one class containing the main method. I applied two recursive methods, one to insert a node and one to display existing nodes. Whenever I run my code however, the console only displays the most recent node that I entered. Is there something wrong with the methods I used? This is what I have so far:

import java.util.Scanner;
public class node {

private int value;
static node root;
public node leftLink;
public node rightLink;

public node(int v)
{
    this.value = v;
}

public int getValue()
{
    return value;
}

static void traverseShow()
{
    if(root.leftLink != null){
        root = root.leftLink;
        traverseShow();
    }
    System.out.println(root.getValue());
    if(root.rightLink != null)
    {
        root = root.rightLink;
        traverseShow();
    }
    return;
}

static void addNode(node n)
{
    if(root==null)
    {
        root = n;
    }
    else
    {   
        if(root.getValue()>n.getValue())
        {
            root = root.leftLink;
            addNode(n);
        }
        if(root.getValue()<n.getValue())
        {
            root = root.rightLink;
            addNode(n);
        }
    }
    return;
}

public static void main(String[] args) 
{
    int val = 0;
    Scanner sc = new Scanner(System.in);
    boolean loop = true;
    String command = "";

    while(loop==true)
    {
        System.out.println("Please enter a command:");
        System.out.println("A = insert a new value");
        System.out.println("B = display all values");
        System.out.println("C = exit program");
        command = sc.next();
        if(command.equalsIgnoreCase("a"))
        {
            System.out.println("Enter value: ");
            val = sc.nextInt();
            node newNode = new node(val);   
            addNode(newNode);
        }
        else if(command.equalsIgnoreCase("b"))
        {
            traverseShow();
        }
        else if(command.equalsIgnoreCase("c"))
        {
            sc.close();
            System.exit(0);
        }
        else
        {
            System.out.println("Invalid command! Please try again.");
        }
    }   
}
}

jonhopkins · Accepted Answer · 2013-07-21 21:24:12Z

2

You're setting the root to the new node when you're traversing the tree to find where to put the new node. One simple option is to store the current root in a temporary variable and put it back after you insert the node.

static void addNode(node n)
{
    if(root==null)
    {
        root = n;
    }
    else
    {
        node tmp = root; // save the current root
        if(root.getValue()>n.getValue())
        {
            root = root.leftLink;
            addNode(n);
        }
        else if(root.getValue()<n.getValue())
        {
            root = root.rightLink;
            addNode(n);
        }
        root = tmp; // put the root back to its original value
    }
    return;
}

You should do something similar for your traverseShow method as well.

answered Jul 21, 2013 at 21:24

jonhopkins

3,8523 gold badges30 silver badges39 bronze badges

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

1 Comment

user2604960 Over a year ago

I see, so my program sets a new root every time. I will definitely apply the changes you suggested. Thanks for the help!

Collectives™ on Stack Overflow

Java: binary tree recursion methods

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related