Hi, I am trying to balance an AVL tree. I have the most code done, and the tree is proporly balanced, however, the Height and Balance are wrong when the program run. My program output: 4 (H:2, B:0) L:1 (H:1, B:0) L:0 (H:0, B:0) R:2 (H:0, B:0) R:7 (H:1, B:0) L:6 (H:0, B:0) R:9 (H:0, B:0) The correct output: 4 (H:3, B:0) L:1 (H:2, B:0) L:0 (H:1, B:0) R:2 (H:1, B:0) R:7 (H:2, B:0) L:6 (H:1, B:0) R:9 (H:1, B:0) Can you help me to debug the height? The following are my code. Thank you!  public interface Map { public int size(); public void put(String key, String value); public String get(String key); } 

 public class AVLTreeMap implements Map { class Node { String key; String value; int height; Node left; Node right; private int size; public Node(String key, String value) { this.key = key; this.value = value; this.height = 1; this.left = null; this.right = null; } private int balanceVal; public int balance() { return balanceVal = balanceCheck(root); } } private Node root; public AVLTreeMap() { root = null; } public void put(String key, String value) { root = put(root, key, value); } private Node put(Node node, String key, String value) { if (node == null) { return new Node(key, value); } if (key.compareTo(node.key) < 0) { node.left = put(node.left, key, value); } else if (key.compareTo(node.key) > 0) { node.right = put(node.right, key, value); } else { node.value = value; return node; } node.size = 1 + size(node.left) + size(node.right); node.height = 1 + Math.max(height(node.left), height(node.right)); return balance(node); } public int size() { return size(root); } private int size(Node node) { if (node == null) { return 0; } return node.size; } private int height(Node node) { if (node == null) { return -1; } return node.height; } private int balanceCheck(Node x) { return height(x.left) - height(x.right); } private Node balance(Node node) { if (balanceCheck(node) < -1) { if (balanceCheck(node.right) > 0) { node.right = rotateRight(node.right); } node = rotateLeft(node); } else if (balanceCheck(node) > 1) { if (balanceCheck(node.left) < 0) { node.left = rotateLeft(node.left); } node = rotateRight(node); } return node; } private Node rotateRight(Node x) { Node y = x.left; x.left = y.right; y.right = x; y.size = x.size; x.size = 1 + size(x.left) + size(x.right); x.height = 1 + Math.max(height(x.left), height(x.right)); y.height = 1 + Math.max(height(y.left), height(y.right)); return y; } private Node rotateLeft(Node x) { Node y = x.right; x.right = y.left; y.left = x; y.size = x.size; x.size = 1 + size(x.left) + size(x.right); x.height = 1 + Math.max(height(x.left), height(x.right)); y.height = 1 + Math.max(height(y.left), height(y.right)); return y; } public String get(String key) { Node x = get(root, key); if (x == null) return null; return x.value; } private Node get(Node node, String key) { if (node == null) { return null; } if (key.compareTo(node.key) < 0) { return get(node.left, key); } else if (key.compareTo(node.key) > 0) { return get(node.right, key); } else { return node; } } public void print() { this.print(this.root, "", 0); } private void print(Node node, String prefix, int depth) { if (node == null) { return; } for (int i = 0; i < depth; i++) { System.out.print(" "); } if (!prefix.equals("")) { System.out.print(prefix); System.out.print(":"); } System.out.print(node.key); System.out.print(" ("); System.out.print("H:"); System.out.print(node.height); System.out.print(", B:"); System.out.print(node.balance()); System.out.println(")"); this.print(node.left, "L", depth + 1); this.print(node.right, "R", depth + 1); } public static void main(String[] args) { AVLTreeMap map = new AVLTreeMap(); String[] keys = {"7", "9", "6", "0", "4", "2", "1"}; String[] values = {"seven", "nine", "six", "zero", "four", "two", "one"}; for (int i = 0; i < keys.length; i++) { map.put(keys[i], values[i]); map.print(); System.out.println(); } for (int i = 0; i < keys.length; i++) { System.out.print(keys[i]); System.out.print(" "); System.out.println(map.get(keys[i])); } } }