Inorder predecessor and successor for a given key in BST

SUBMITTED BY: BadduCoder

DATE: March 5, 2020, 5:11 p.m.

FORMAT: C++

SIZE: 2.5 kB

Raw Download

HITS: 528

Report
  1. // C++ program to find predecessor
  2. // and successor in a BST
  3. #include <bits/stdc++.h>
  4. using namespace std;
  6. // BST Node
  7. struct Node {
  8. int key;
  9. struct Node *left, *right;
  10. };
  12. // Function that finds predecessor and successor of key in BST.
  13. void findPreSuc(Node* root, Node*& pre, Node*& suc, int key)
  14. {
  15. if (root == NULL)
  16. return;
  18. // Search for given key in BST.
  19. while (root != NULL) {
  21. // If root is given key.
  22. if (root->key == key) {
  24. // the minimum value in right subtree
  25. // is predecessor.
  26. if (root->right) {
  27. suc = root->right;
  28. while (suc->left)
  29. suc = suc->left;
  30. }
  32. // the maximum value in left subtree
  33. // is successor.
  34. if (root->left) {
  35. pre = root->left;
  36. while (pre->right)
  37. pre = pre->right;
  38. }
  40. return;
  41. }
  43. // If key is greater than root, then
  44. // key lies in right subtree. Root
  45. // could be predecessor if left
  46. // subtree of key is null.
  47. else if (root->key < key) {
  48. pre = root;
  49. root = root->right;
  50. }
  52. // If key is smaller than root, then
  53. // key lies in left subtree. Root
  54. // could be successor if right
  55. // subtree of key is null.
  56. else {
  57. suc = root;
  58. root = root->left;
  59. }
  60. }
  61. }
  63. // A utility function to create a new BST node
  64. Node* newNode(int item)
  65. {
  66. Node* temp = new Node;
  67. temp->key = item;
  68. temp->left = temp->right = NULL;
  69. return temp;
  70. }
  72. // A utility function to insert
  73. // a new node with given key in BST
  74. Node* insert(Node* node, int key)
  75. {
  76. if (node == NULL)
  77. return newNode(key);
  78. if (key < node->key)
  79. node->left = insert(node->left, key);
  80. else
  81. node->right = insert(node->right, key);
  82. return node;
  83. }
  85. // Driver program to test above function
  86. int main()
  87. {
  88. int key = 65; // Key to be searched in BST
  90. /* Let us create following BST
  91. 50
  92. / \
  93. / \
  94. 30 70
  95. / \ / \
  96. / \ / \
  97. 20 40 60 80
  98. */
  99. Node* root = NULL;
  100. root = insert(root, 50);
  101. insert(root, 30);
  102. insert(root, 20);
  103. insert(root, 40);
  104. insert(root, 70);
  105. insert(root, 60);
  106. insert(root, 80);
  108. Node *pre = NULL, *suc = NULL;
  110. findPreSuc(root, pre, suc, key);
  111. if (pre != NULL)
  112. cout << "Predecessor is " << pre->key << endl;
  113. else
  114. cout << "-1";
  116. if (suc != NULL)
  117. cout << "Successor is " << suc->key;
  118. else
  119. cout << "-1";
  120. return 0;
  121. }
comments powered by Disqus