Hello,

I am trying to create a method within a binary search tree class to compute the height of a tree. Can you please help me complete the postorder method below that takes no parameters and, when called, returns the height of the root node of the tree? The height of the node is defined as follows:

- A leaf node heas a height of 0 - A node with one child has a height of 1 plus the height of its child - A node with two children has a height of 1 plus the larger of the heights of its children

Thank you in advance!

My current Java BST file looks like so:

package program3;

import stdlib.*;

//More info on the stdlib library can be found here: https://introcs.cs.princeton.edu/java/stdlib/.

import algs13.Queue;

public class P3SimplerBST, V> {

private Node root; // root of BST

private static class Node,V> {

public K key; // sorted by key

public V val; // associated data

public Node left, right; // left and right subtrees

public Node(K key, V val) {

this.key = key;

this.val = val;

}

}

//Needs to be a postorder traversal passing NO parameters in order to return the height of a binary search tree: //My current version of this method doesn't work.

public int height () {

if (root == null) {

return 0;

}

return height(root.left) + height(root.right);

}

/* *********************************************************************

* Search BST for given key, and return associated value if found,

* return null if not found

***********************************************************************/

// does there exist a key-value pair with given key?

public boolean contains(K key) {

return get(key) != null;

}

// return value associated with the given key, or null if no such key exists

public V get(K key) { return get(root, key); }

private V get(Node x, K key) {

if (x == null) return null;

int cmp = key.compareTo(x.key);

if (cmp < 0) return get(x.left, key);

else if (cmp > 0) return get(x.right, key);

else return x.val;

}

/* *********************************************************************

* Insert key-value pair into BST

* If key already exists, update with new value

***********************************************************************/

public void put(K key, V val) {

if (val == null) { delete(key); return; }

root = put(root, key, val);

}

private Node put(Node x, K key, V val) {

if (x == null) return new Node<>(key, val);

int cmp = key.compareTo(x.key);

if (cmp < 0)

x.left = put(x.left, key, val);

else if (cmp > 0)

x.right = put(x.right, key, val);

else

x.val = val;

return x;

}

/* *********************************************************************

* Delete

***********************************************************************/

public void delete(K key) {

root = delete(root, key);

}

private Node delete(Node x, K key) {

if (x == null) return null;

int cmp = key.compareTo(x.key);

if (cmp < 0) x.left = delete(x.left, key);

else if (cmp > 0) x.right = delete(x.right, key);

else {

// x is the node to be deleted.

// The value returned in each of these cases below

// becomes the value of the child reference from

// the parent of x. Returning a null makes that

// reference a null and so cuts x off, causing its

// automatic deletion.

// Determine how many children x has.

if (x.right == null && x.left == null){

// This is a leaf node.

return null;

} else if (x.right == null) {

// One child, to the left.

return x.left;

} else if (x.left == null) {

// One child, to the right.

return x.right;

} else {

// Node x has two children.

// Find the node in x's right subtree with

// the minimum key.

Node rightTreeMinNode = findMin(x.right);

x.key = rightTreeMinNode.key;

x.val = rightTreeMinNode.val;

x.right = delete(x.right, rightTreeMinNode.key);

}

}

return x;

}

private Node findMin(Node x) {

if (x.left == null) return x;

else return findMin(x.left);

}

public Iterable keys() {

Queue q = new Queue<>();

inOrder(root, q);

return q;

}

private void inOrder(Node x, Queue q) {

if (x == null) return;

inOrder(x.left, q);

q.enqueue(x.key);

inOrder(x.right, q);

}