Binary Search Tree implementation problem-CodePudding

I've got this BST I've built and trying to follow java code conventions I decided to fix around some of the access modifiers and add some getters and setters but now my entire code is giving me lots of problems in the execution and I cannot figure out why.

This is my Node class.

/**
 * A class that implements a binary tree's node. It contains the data inside each node of the tree.
 */
public class Node {
  private int data;
  private Node left;
  private Node right;

  /**
   * Constructor initializing the data of the node.
   *
   * @param data The numeric value of each node as an Integer.
   */
  public Node(int data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  public int getData() {
    return data;
  }

  public void setData(int data) {
    this.data = data;
  }

  public Node getLeft() {
    return left;
  }

  public void setLeft(Node left) {
    this.left = left;
  }

  public Node getRight() {
    return right;
  }

  public void setRight(Node right) {
    this.right = right;
  }
}

This is the tree class.

import java.util.ArrayList;
import java.util.List;

/** Class implementation of a binary tree , containing helper classes and methods. */
public class BinaryTree {
  private Node root;
  private List<Integer> nodes = new ArrayList<>();
  /** Constructor initializing the root node of the tree. */
  public BinaryTree() {
    root = null;
  }

  public Node getRoot() {
    return root;
  }

  private Node insertNode(Node node, int dataBeingInserted) {
    if (node == null) {
      node = new Node(dataBeingInserted);
      return node;
    }
    if (node.getData() > dataBeingInserted) {
      insertNode(node.getLeft(), dataBeingInserted);
    } else if (node.getData() < dataBeingInserted) {
      insertNode(node.getRight(), dataBeingInserted);
    }
    return node;
  }

  /**
   * Method that inserts nodes into the binary tree. If the tree is empty , a new root node is
   * initialized.
   *
   * @param dataBeingInserted The number to be inserted as an integer.
   */
  public void insertNode(int dataBeingInserted) {
    root = insertNode(root, dataBeingInserted);
  }

  private Node searchTree(Node node, int dataBeingSearched) {
    if (node == null || node.getData() == dataBeingSearched) {
      return node;
    }
    if (node.getData() > dataBeingSearched) {
      return searchTree(node.getLeft(), dataBeingSearched);
    }
    return searchTree(node.getRight(), dataBeingSearched);
  }
  /**
   * Method that recursively searches for our element through the tree. If the value is present in
   * the root node , or there aren't any nodes in the tree , the method returns the root node. If
   * the value we're looking for is smaller than the root node's value , we search for our value in
   * the left subtree , otherwise we search for it in the right subtree.
   *
   * @param dataBeingSearched User's value.
   * @return Recursive call of the method.
   */
  public Node searchTree(int dataBeingSearched) {
    return searchTree(root, dataBeingSearched);
  }

  private String inorderTraversal(Node node) {
    if (node == null) {
      return "";
    }
    inorderTraversal(node.getLeft());
    nodes.add(node.getData());
    inorderTraversal(node.getRight());
    return nodes.toString();
  }

  /**
   * An implementation of the In-order traversal. First the left subtree is visited and printed
   * accordingly, then we visit and print the root and after that we visit and print the right
   * subtree.
   */
  public String inorderTraversal() {
    return inorderTraversal(root);
  }
}

And those are some tests I wrote just to try some stuff.

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNotNull;

/** Binary tree operations tests. */
class BinaryTreeTests {
  /** Testing whether the answer is correct if we search for the root value of the tree. */
  @Test
  void isSearchWorking() {
    BinaryTree tree = new BinaryTree();
    tree.insertNode(10);
    tree.insertNode(30);
    tree.insertNode(35);
    tree.insertNode(29);
    assertEquals(tree.getRoot(), tree.searchTree(20));
  }

  /** Testing whether the root changes it's value from null after a single insertion. */
  @Test
  void isInsertWorking() {
    BinaryTree tree = new BinaryTree();
    assertNotNull(tree.getRoot());
  }

  @Test
  void inOrderTraversalPrint() {
    BinaryTree tree = new BinaryTree();
    tree.insertNode(10);
    tree.insertNode(30);
    tree.insertNode(35);
    tree.insertNode(29);
    assertEquals("[10, 20, 29, 30, 35]", tree.inorderTraversal());
  }

  @Test
  void inOrderTraversalSameElement() {
    BinaryTree tree = new BinaryTree();
    tree.insertNode(1);
    tree.insertNode(1);
    tree.insertNode(1);
    tree.insertNode(1);
    tree.insertNode(1);
    tree.insertNode(1);
    assertEquals("[1]", tree.inorderTraversal());
  }

}

So before I set the data , left and right variables in the Node class to public , everything was working just fine , now that they are private , only the last test passes for some reason.

isInsertWorking() is giving me expected not

inOrderTraversalPrint() is giving me just [10] instead of [10, 20, 29, 30, 35]

isSearchWorking() says expected node got null.

I currently do not know how to handle these things , I think my recursions might be incorrect but I cannot think of a way to fix them.

CodePudding user response：

The main problem was in insertNode() function which I have fixed. There was a bug in searchTree() function and also I cleared the list nodes whenever inorderTraversal() is called since the tree can be modified between two inorderTraversal() calls.

import java.util.ArrayList;
import java.util.List;
/**
 * A class that implements a binary tree's node. It contains the data inside each node of the tree.
 */
class Node {
    private int data;
    private Node left;
    private Node right;

    /**
     * Constructor initializing the data of the node.
     *
     * @param data The numeric value of each node as an Integer.
     */
    public Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

/** Class implementation of a binary tree , containing helper classes and methods. */
class BinaryTree {
    private Node root;
    private List<Integer> nodes = new ArrayList<>();
    /** Constructor initializing the root node of the tree. */
    public BinaryTree() {
        root = null;
    }

    public Node getRoot() {
        return root;
    }

    private Node insertNode(Node node, int dataBeingInserted) {
        if (node == null)
            return new Node(dataBeingInserted);

        if (node.getData() == dataBeingInserted)
            return root;

        if (node.getData() < dataBeingInserted) {
            if (node.getRight() != null)
                return insertNode(node.getRight(), dataBeingInserted);
            else
                node.setRight(new Node(dataBeingInserted));
        } else if (node.getData() > dataBeingInserted) {
            if (node.getLeft() != null)
                return insertNode(node.getLeft(), dataBeingInserted);
            else
                node.setLeft(new Node(dataBeingInserted));
        }
        return root;
    }

    /**
     * Method that inserts nodes into the binary tree. If the tree is empty , a new root node is
     * initialized.
     *
     * @param dataBeingInserted The number to be inserted as an integer.
     */
    public void insertNode(int dataBeingInserted) {
        root = insertNode(root, dataBeingInserted);
    }

    private Node searchTree(Node node, int dataBeingSearched) {
        if (node == null || node.getData() == dataBeingSearched) {
            return node;
        }
        if (node.getData() > dataBeingSearched) {
            return searchTree(node.getLeft(), dataBeingSearched);
        } else {
            return searchTree(node.getRight(), dataBeingSearched);
        }
    }
    /**
     * Method that recursively searches for our element through the tree. If the value is present in
     * the root node , or there aren't any nodes in the tree , the method returns the root node. If
     * the value we're looking for is smaller than the root node's value , we search for our value in
     * the left subtree , otherwise we search for it in the right subtree.
     *
     * @param dataBeingSearched User's value.
     * @return Recursive call of the method.
     */
    public Node searchTree(int dataBeingSearched) {
        return searchTree(root, dataBeingSearched);
    }

    private String inorderTraversal(Node node) {
        if (node == null) {
            return "";
        }
        inorderTraversal(node.getLeft());
        nodes.add(node.getData());
        inorderTraversal(node.getRight());
        return nodes.toString();
    }

    /**
     * An implementation of the In-order traversal. First the left subtree is visited and printed
     * accordingly, then we visit and print the root and after that we visit and print the right
     * subtree.
     */
    public String inorderTraversal() {
        nodes.clear();  // clear the previous state
        return inorderTraversal(root);
    }
}