bst with parent pointer

1#include<iostream>
2#include<queue>
3
4using namespace std;
5
6struct Node {
7      int data;
8      Node *left, *right, *parent;
9};
10
11struct Node *newNode(int data) {
12   Node *temp = new Node;
13   temp->data = data;
14   temp->left = temp->right = temp->parent = NULL;
15   return temp;
16}
17void inorderTraverse(struct Node *root) {
18   if (root != NULL)  {
19    // Traverse left
20    inorderTraverse(root->left);
21
22    // Traverse root
23    printf("%d -> ", root->data);
24
25    // Traverse right
26    inorderTraverse(root->right);
27  }
28}
29
30struct Node* insert(struct Node* node, int key) {
31   if (node == NULL) return newNode(key);
32   if (key < node->data) { //to the left subtree
33      Node *left_child = insert(node->left, key);
34      node->left = left_child;
35      left_child->parent = node;
36   }
37   else if (key > node->data) { // to the right subtree
38      Node *right_child = insert(node->right, key);
39      node->right = right_child;
40      right_child->parent = node;
41   }
42   return node;
43}
44
45/* deletion function */
46
47void deleteNode(Node *root, int data)
48{
49    if(root == NULL){
50        cout << "Tree is empty\n";
51        return;
52    }
53
54    queue<Node*> q;
55    q.push(root);
56
57    while(!q.empty()){
58        Node *temp = q.front();
59        q.pop();
60        if(temp->data == data){
61            Node *current = root;
62            Node *prev;
63            while(current->right != NULL){
64                prev = current;
65                current = current->right;
66            }
67            temp->data = current->data;
68            prev->right = NULL;
69            free(current);
70            cout << "Deleted\n";
71            return;
72        }
73
74        if(temp->left != NULL)
75            q.push(temp->left);
76        if(temp->right != NULL)
77            q.push(temp->right);
78    }
79 }
80
81
82int main() {
83   struct Node *root = NULL;
84   root = insert(root, 100);
85   insert(root, 60);
86   insert(root, 40);
87   insert(root, 80);
88   insert(root, 140);
89   insert(root, 120);
90   insert(root, 160);
91   inorderTraverse(root);  cout << endl;
92   deleteNode(root, 140);
93   deleteNode(root, 60);
94   deleteNode(root, 140);
95   inorderTraverse(root);  cout << endl;
96}