二分探索木の中間順の次節点

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};

Node* insert(Node* root, int key) {
  if (root == NULL) {
    return new Node(key);
  }
  if (key < root->data) {
    root->left = insert(root->left, key);
  } else {
    root->right = insert(root->right, key);
  }
  return root;
}

Node* getNextleft(Node* root) {
  while (root->left) {
    root = root->left;
  }

  return root;
}

void inorderSuccessor(Node* root, Node*& succ, int key) {
  if (root == NULL) {
    succ = NULL;
    return;
  }

  if (root->data == key) {
    if (root->right) {
      succ = getNextleft(root->right);
    }
  }

  else if (key < root->data) {
    succ = root;
    inorderSuccessor(root->left, succ, key);
  } else {
    inorderSuccessor(root->right, succ, key);
  }
}

int main() {
  int keys[] = {1, 5, 8, 2, 6, 3, 7, 4};
  Node* root = NULL;
  for (int key : keys) {
    root = insert(root, key);
  }
  for (int key : keys) {
    Node* prec = NULL;
    inorderSuccessor(root, prec, key);
    if (prec) {
      cout << "Inorder successor of node " << key << " is " << prec->data;
    } else {
      cout << "No inorder Successor of node " << key;
    }

    cout << '\n';
  }

  return 0;
}