Implementing a recursive Void function (Finding height of Binary Search Tree)

Question

I need to implement a void function that computes the height of each node in a binary tree and stores it in each node. I've found a few solutions online that are recursive in nature but they return int. Examples include (https://www.geeksforgeeks.org/write-a-c-program-to-find-the-maximum-depth-or-height-of-a-tree/). The difference between the model answer, besides that it is not a void function, is that it also does not store the height in each node.

This is my attempt at the solution, but I can't seem to get the code to work, nor refit the model answer to recursively apply in a void function. When I run my code in the helper code to test, it doesn't even show any output.

void computeHeight(Node *n) {
  Node* ltraverser = n;
  Node* rtraverser = n;
  int lheight = 0;
  int rheight =0;

  if (n == NULL) {
   n->height = 0;
  }

  while (ltraverser->left != NULL) {
   ltraverser = ltraverser->left;
   lheight += 1;
  }

  while (rtraverser->right != NULL) {
   rtraverser = rtraverser->right;
   lheight += 1;
  }

  if (lheight > rheight) {
    n->height = lheight;
  }

  else {
    n->height = rheight;
  }

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

For reference:

The starter code below defines a class called "Node" that has two child pointers ("left" , "right") and an integer "height" member variable. There is also a constructor Node() that initializes the children to nullptr and the height to -1.

/*
The height of a node is the number of edges in
its longest chain of descendants.

Implement computeHeight to compute the height
of the subtree rooted at the node n. Note that
this function does not return a value. You should
store the calculated height in that node's own
height member variable. Your function should also
do the same for EVERY node in the subtree rooted
at the current node. (This naturally lends itself
to a recursive solution!)

Assume that the following includes have already been
provided. You should not need any other includes
than these.

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>

You have also the following class Node already defined.
You cannot change this class definition, so it is
shown here in a comment for your reference only:

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;
  }
};
*/

For testing the code

// This function prints the tree in a nested linear format.
void printTree(const Node *n) {
  if (!n) return;
  std::cout << n->height << "(";
  printTree(n->left);
  std::cout << ")(";
  printTree(n->right);
  std::cout << ")";
}

  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();

  computeHeight(n);

  printTree(n);
  std::cout << std::endl << std::endl;
  printTreeVertical(n);

  delete n;
  n = nullptr;

  return 0;
}

Answer 1

Instead of returning node height just recurisvely call computeHeight on left and right nodes, then store maximum height in node structure.

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>

class Node {
public:
  int height;
  Node *left, *right;
  Node() { height = -1; left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};

void computeHeight(Node *node) {

    if (node == nullptr) {
        return;
    }

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

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

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

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

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

void printNode(Node *n, int level = 0) {
    if (n == nullptr) {
        return;
    }

    std::cout << std::string(level * 2, ' ') << "Height = " << n->height << "\n";

    printNode(n->left,  level + 1);
    printNode(n->right, level + 1);
}


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();


  computeHeight(n);
  printNode(n);
}