Learning JavaScript Data Structures and Algorithms - Third Edition

Height of a node and the balancing factor

As we learned at the beginning of this chapter, the height of a node is defined as the maximum number of edges from the node to any of its leaf nodes. The following diagram exemplifies a tree with the height of each node:

The code to calculate the height of a node is as follows:

getNodeHeight(node) {
  if (node == null) {
    return -1;
  }
  return Math.max(    this.getNodeHeight(node.left), this.getNodeHeight(node.right)    ) + 1;
}

In an AVL tree, whenever we insert or remove a node from the tree, we will need to calculate the difference between the height of the right-hand side subtree (hr) and the left-hand side ...