CODEWITHSUNDEEP
c++algorithm
A1122
A1122

Reputation: 1354

Calculate Tree Height at each Node, help me explain this code solution

Here's a code snippet of a solution that calculates height of each node in a binary tree and stores the height in each node. The code traverse the tree recursively, and below is the Node constructor.

class Node {
public:
  int height; // to be set by computeHeight()
  Node *left, *right;
  Node() { height = -1; left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};

Below is the function which computes and stores height at each Node. Where I am confused is how do leftHeight and rightHeight get updated by n->left->height and n->right->height if at construction, height is set to -1?

void computeHeight(Node *n) {

if (n == nullptr) {
    return;
}

computeHeight(n->left);
computeHeight(n->right);

int leftHeight = -1;
int rightHeight = -1;

if (n->left != nullptr) {
    leftHeight = n->left->height;
}

if (n->right != nullptr) {
    rightHeight = n->right->height;
}

n->height = std::max(leftHeight, rightHeight) + 1;

}

Here is the main file that runs the function computeHeight

int main() {
  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();
  n->right->right->right->left = new Node();

  computeHeight(n);

  delete n;
  n = nullptr;

  return 0;

}

Upvotes: 0

Views: 809

Answers (2)

Nikhil Chatterjee
Nikhil Chatterjee

Reputation: 279

We can solve this problem with a basic case of induction. Basically, let's start with the base case, and then assuming any case n works, we have to check if case n+1 works. In the case of calculating the heights of the nodes in a Binary Tree, the base case is when the root node is a leaf node, and for the n+1 case the left/right side nodes are the n cases. You can think of it as n is the height of the current node, and n=0 is the leaf node base case.

When the root node is a leaf, both the left and right side nodes are nullptr the method essentially turns into

void computeHeight(Node *n) {
    int leftHeight = -1;
    int rightHeight = -1;

    n->height = std::max(leftHeight, rightHeight) + 1;
}

in which case n->height becomes 0, which is correct for a leaf node. Now, when the node is a non-leaf node, the statements

computeHeight(n->left);
computeHeight(n->right);

are already called before the calculation. This essentially makes it so that we assume that both the left and right side nodes are already taken care of, and their heights are correct. Then, we can use the left and right nodes' heights to calculate the root node's height, which is calculated through

int leftHeight = -1;
int rightHeight = -1;

if (n->left != nullptr) {
    leftHeight = n->left->height;
}

if (n->right != nullptr) {
    rightHeight = n->right->height;
}

n->height = std::max(leftHeight, rightHeight) + 1;

The trick here is that we already have called computeHeight() on the left and right side nodes so that when we do the calculations on the current node, we can safely assume that the child nodes have been totally taken care of. Also, the child nodes are calculated before the root node, so the program will first trickle all the way down to the leaves before coming back up and calculating the non-leaf nodes.

Upvotes: 1

john
john

Reputation: 87959

Imagine a leaf node (left and right are nullptr). Then n->left != nullptr and n->right != nullptr are false so the calculation effectively becomes

int leftHeight = -1;
int rightHeight = -1;
n->height = std::max(leftHeight, rightHeight) + 1;

which is effectively

n->height = 0;

Now because of the way the recursion is done, each node gets it height calculated after it's children have had their heights calculated. So imagine a node with two children, each of which is a leaf node. We've already seen that leaf nodes get a height of zero. So the calculation for such a node is effectively

int leftHeight = -1;
int rightHeight = -1;
if (n->left != nullptr) {
    leftHeight = 0; // because n->left is a leaf node
}
if (n->right != nullptr) {
    rightHeight = 0; // because n->right is a leaf node
}
n->height = std::max(leftHeight, rightHeight) + 1;

which means that you end up with n->height = 1 for that node.

And so on. These calculations perculate up the tree, starting at the leaves, until finally the root gets it's height set.

Upvotes: 2

Related Questions