In some binary search trees, each node has a left child pointer, a right child p
ID: 3897679 • Letter: I
Question
In some binary search trees, each node has a left child pointer, a right child pointer and a parent pointer. The parent pointer of a node points to its parent (duh!), or is nullptr if the node is the root node. This problem will examine such trees.
Show a C++ structure/class definition for a binary tree node that has both child node pointers and a parent node pointer. Assume the data stored in each node is an int.
Write pseudocode to insert a new node into a binary search tree with parent pointers. (Hint: You can find binary search tree insertion code on pp. 471-473).
Explanation / Answer
********Pseudocode in bold***************
// C++ program to demonstrate insert operation
// in binary search tree with parent pointer
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int key;
struct Node *left, *right, *parent;
};
// A utility function to create a new BST Node
struct Node *newNode(int item)
{
struct Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
temp->parent = NULL;
return temp;
}
// A utility function to do inorder traversal of BST
void inorder(struct Node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("Node : %d, ", root->key);
if (root->parent == NULL)
printf("Parent : NULL ");
else
printf("Parent : %d ", root->parent->key);
inorder(root->right);
}
}
/* A utility function to insert a new Node with
given key in BST
Pseudocode:
1. First check, if the tree is empty, then simply return the newly created Node
2. Otherwise, recusrively percolate down the tree untill you find a suitable node.
a) Set the parent of root of the left subtree if the node to be inserted is less than
current node's value
b) Set the parent of root of the right subtree if the node to be inserted is greater than
current node's value
*/
struct Node* insert(struct Node* node, int key)
{
/* If the tree is empty, return a new Node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
{
Node *lchild = insert(node->left, key);
node->left = lchild;
// Set parent of root of left subtree
lchild->parent = node;
}
else if (key > node->key)
{
Node *rchild = insert(node->right, key);
node->right = rchild;
// Set parent of root of right subtree
rchild->parent = node;
}
/* return the (unchanged) Node pointer */
return node;
}
// Driver Program to test above functions
int main()
{
/* Let us create following BST
50
/
30 70
/ /
20 40 60 80 */
struct Node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
// print iNoder traversal of the BST
inorder(root);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.