writing a proper binary tree height function?

Question

I'm trying to write a function that displays the height of my binary search tree which is displayed below. The problem is I'm supposed to write a function that doesn't have any arguments or parameters. This is really stumping me. I tried declaring root outside the parameter list but that didn't work. Any solutions?

int height (Node root){
if (root == null) {
    return 0;
    }
int hleftsub = height(root.m_left);
int hrightsub = height(root.m_right);
return Math.max(hleftsub, hrightsub) + 1;
    }

the method signature provide by my instructor is

int height ()

EDIT:

my full code

import javax.swing.tree.TreeNode;
import java.util.Scanner;
import java.io.FileNotFoundException;
import java.io.File;
import java.util.ArrayList;

class BinarySearchTree<E extends Comparable<E>> {
    public Node<E> root;
    public int m_size = 0;

    public BinarySearchTree() {

    }

public boolean search(E value) {
    boolean ret = false;
    Node<E> current = root;
    while (current != null && ret != true) {
        if (current.m_value.compareTo(current.m_value) == 0) {
            ret = true;
        } else if (current.m_value.compareTo(current.m_value) > 0) {
            current = current.m_left;
        } else {
            current = current.m_right;
        }
    }
    return false;
}

public boolean insert(E value) {
    if (root == null) {
        root = new Node<>(value);
        m_size++;
    } else {
        Node<E> current = root;
        Node<E> parentNode = null;
        while (current != null)
            if (current.m_value.compareTo(value) > 0) {
                parentNode = current;
                current = current.m_left;
            } else if (current.m_value.compareTo(value) < 0) {
                parentNode = current;
                current = current.m_right;
            } else {
                return false;
            }
        if (current.m_value.compareTo(value) < 0) {
            parentNode.m_left = new Node<>(value);
        } else {
            parentNode.m_right = new Node<>(value);

        }
    }
    m_size++;
    return true;
}

boolean remove(E value) {
    if (!search(value)) {
        return false;
    }
    Node check = root;
    Node parent = null;
    boolean found = false;
    while (!found && check != null) {
        if (value.compareTo((E) check.m_value) == 0) {
            found = true;
        } else if (value.compareTo((E) check.m_value) < 0) {
            parent = check;
            check = check.m_left;
        } else {
            parent = check;
            check = check.m_right;
        }

    }
    if (check == null) {
        return false;
    } else if (check.m_left == null) {
        if (parent == null) {
            root = check.m_right;
        } else if (value.compareTo((E) parent.m_value) < 0) {
            parent.m_left = check.m_right;
        } else {
            parent.m_right = check.m_right;
        }
    } else {
        Node<E> parentofRight = check;
        Node<E> rightMost = check.m_left;
        while (rightMost.m_right != null) {
            parentofRight = rightMost;
            rightMost = rightMost.m_right;
        }
        check.m_value = rightMost.m_value;
        if (parentofRight.m_right == rightMost) {
            rightMost = rightMost.m_left;
        } else {
            parentofRight.m_left = rightMost.m_left;
        }
    }
    m_size--;
    return true;
}

int numberNodes () {
    return m_size;
    }

int height (Node root){
    if (root == null) {
        return 0;
        }
    int hleftsub = height(root.m_left);
    int hrightsub = height(root.m_right);
    return Math.max(hleftsub, hrightsub) + 1;
        }

int numberLeafNodes(Node node){
    if (node == null) {
        return 0;
    }
    else if(node.m_left == null && node.m_right == null){
        return 1;
    }
    else{
        return numberLeafNodes(node.m_left) + numberLeafNodes(node.m_right);
    }
}

void display(String message){
    if(root == null){
        return;
    }
    display(String.valueOf(root.m_left));
    display(String.valueOf(root));
    display(String.valueOf(root.m_right));
}
}

class Node<E> {
    public E m_value;
    public Node<E> m_left;
    public Node<E> m_right;


    public Node(E value) {
        m_value = value;
    }

}

Answer 1

1. If you traverse the tree iteratively, you can get the height without recursion. Anything recursive can be implemented iteratively. It may be more lines of code though. This would be a variation of level order graph / tree traversal.

See: https://www.geeksforgeeks.org/iterative-method-to-find-height-of-binary-tree/

If you use that implementation, delete the parameter, as height() will already have access to root.

This however requires a queue and is O(n) time and O(n) space.

2. height() may be a public method that calls a private method height(Node node) that starts recursion. O(n) time, O(1) space for BST.

3. You can pass height as an extra parameter where recursively inserting into the tree so that you are counting the number of recursive calls (which is directly correlated with the depth / # of levels down in the tree you are). Once a node finds it's place, if the height (# of recursive calls) you were passing exceeds the instance variable height stored by the tree, you update the instance variable to the new height. This will also allow tree.height() to be a constant time function. O(1) time, O(1) space.