How do I write the left() and right() methods for a BinaryTree class

Question

I am currently taking a Data Structures and Algorithms course. Last class, my Professor put up some code on the board to explain how to write the size(), the height(), and left()/right() methods to teach us two-balance in anticipation for a quiz.

He wrote the code you see below on the board, but he mentioned that while he made an error, to focus on the logic for now and that he would have to run a few tests to understand his error.

public class BT<T> {
    TreeNode<T> root;
    BT<T> myTree;

    //size
    public int size() {
        if(this.isEmpty())
            return 0;
        return (1 + this.left().size() + this.right().size());
    }
    //isEmpty()
    public boolean isEmpty() {
        return (root == null);
    }
    //left
    public BT<T> left() {
        return root.left;
    } 

    public BT<T> right() {
        return root.right;
    }
}

Over the weekend, I tried to figure this out myself, as during my Professor's office hours, he wasn't able to work on the code due to the high volume of students visiting him in regards to the midterm.

What's the way to fix this method?

EDIT:

Here's the TreeNode<T> class

class TreeNode<T> {
    T data;
    TreeNode<T> left;
    TreeNode<T> right;

}

It was inside another class within the same package.

"What's the way to fix this method?" *Which* method? If you're asking about the `left()` and `right()` methods, we can't say without seeing the definition of `TreeNode`. — Andy Turner, Nov 11 '19 at 14:39

Joop Eggen · Answer 1 · 2019-11-11T15:03:09.433

As left and right should not necessarily be exposed, but belong to the internal (non-public) TreeNode move the methods there.

  return root == null ? 0 : root.size();

class TreeNode<T> {
    T data;
    TreeNode<T> left;
    TreeNode<T> right;

    TreeNode<T> left() {
        return left;
    } 

    TreeNode<T> right() {
        return right;
    }

    int size() {
        int n = 1;
        if (left != null) {
            n += left.size();
        } else if (right != null) {
            n += right.size();
        }
        return n;
    }
}

There is no public concept of subtree, the container class BT hold the size and root node.

As such it is more a stylistic matter to have getters such as left() and right().

score 0 · Answer 2 · answered Nov 11 '19 at 15:02

If, as you say, the TreeNode class is inside another class (inner class) you cannot access the inner class without an instance of the outer class.

So if your TreeNode class is defined inside class A you need to create them together:

A.TreeNode node = new A.TreeNode()

instead of only creating a TreeNode inside the BT class.

you can have a look at explain the way to access inner class in java? which in my opinion explains the problem, as well as the solution.

If my assumption of an inner class was wrong, please let me know and I will adapt or delete my answer.

Not quite, It's more like `class TreeNode { T data; TreeNode left; TreeNode right; } public class Traverse { //code body }` — Samuel Viveros, Nov 11 '19 at 15:19

How do I write the left() and right() methods for a BinaryTree class

2 Answers2