0
votes

Referencing the answer to this question

A balanced binary tree is:

  1. The left and right subtrees' heights differ by at most one, AND
  2. The left subtree is balanced, AND
  3. The right subtree is balanced

Now, using the same example

     A
   /   \
  B     C  
 /     / \  
D     E   F  
     /  
    G  

The tree is rooted at A.

Now, when looking at the definition for height balanced tree, the first point says:

  1. The left and right subtrees' heights differ by at most one

    If I am currently at the node A, to determine the height of the LEFT SUBTREE of A I am confused if I calculate:

    • Height of node A looking at the deepest left child from A (D) OR
    • Height of node B looking at the deepest left child from A (by extension B) (D)

    If I am currently at the node A, to determine the height of the RIGHT SUBTREE of A I am confused if I calculate:

    • Height of node A looking at the deepest right child from A (F) OR
    • Height of node C looking at the deepest right child from A (by extension C) (F)
1

1 Answers

0
votes

'The height of a subtree' is generally translated as 'height of the root of the subtree'. Bumped into this explanation while listening to this MIT OpenCourseWare lecture, at timestamp 13:17.