Given a BST, write an efficient function to search a given key in it. The algorithm should return the parent node of the key and print if the key is left or right node of the parent node. If the key is not present in the BST, the algorithm should be able to determine that.

Searching a binary search tree for a specific key can be programmed recursively or iteratively.

We begin by examining the root node. If the tree is null, the key we are searching for does not exist in the tree. Otherwise, if the key equals that of the root, the search is successful and we return the node. If the key is less than that of the root, we search the left subtree. Similarly, if the key is greater than that of the root, we search the right subtree. This process is repeated until the key is found or the remaining subtree is null. If the searched key is not found after a null subtree is reached, then the key is not present in the tree. This is easily expressed as a recursive algorithm.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include <iostream> using namespace std; // Data structure to store a Binary Search Tree node struct Node { int data; Node *left, *right; }; // Function to create a new binary tree node having given key Node* newNode(int key) { Node* node = new Node; node->data = key; node->left = node->right = nullptr; return node; } // Recursive function to insert an key into BST Node* insert(Node* root, int key) { // if the root is null, create a new node an return it if (root == nullptr) return newNode(key); // if given key is less than the root node, recuse for left subtree if (key < root->data) root->left = insert(root->left, key); // if given key is more than the root node, recuse for right subtree else root->right = insert(root->right, key); return root; } // Recursive function to search in given BST void search(Node* root, int key, Node* parent) { // if key is not present in the key if (root == nullptr) { cout << "Key Not found"; return; } // if key is found if (root->data == key) { if (parent == nullptr) cout << "The node with key " << key << " is root node"; else if (key < parent->data) cout << "Given key is left node of node with key " << parent->data; else cout << "Given key is right node of node with key " << parent->data; return; } // if given key is less than the root node, recuse for left subtree // else recuse for right subtree if (key < root->data) return search(root->left, key, root); return search(root->right, key, root); } // Search given key in BST int main() { Node* root = nullptr; int keys[] = { 15, 10, 20, 8, 12, 16, 25 }; for (int key : keys) root = insert(root, key); search(root, 25, nullptr); return 0; } |

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

The same algorithm can be implemented iteratively.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
// Iterative function to search in given BST void searchIterative(Node* root, int key) { // start with root node Node *curr = root; // pointer to store parent node of current node Node* parent = nullptr; // traverse the tree and search for the key while (curr != nullptr && curr->data != key) { // update parent node as current node parent = curr; // if given key is less than the current node, go to left subtree // else go to right subtree if (key < curr->data) curr = curr->left; else curr = curr->right; } // if key is not present in the key if (curr == nullptr) { cout << "Key Not found"; return; } if (parent == nullptr) cout << "The node with key " << key << " is root node"; else if (key < parent->data) cout << "Given key is left node of node with key " << parent->data; else cout << "Given key is right node of node with key " << parent->data; } |

In the worst case this algorithm must search from the root of the tree to the leaf farthest from the root, the search operation takes time proportional to the tree’s height. On average, binary search trees with n nodes have O(log n) height. However, in the worst case, binary search trees can have O(n) height (for skewed trees where all the nodes except leaf have one and only one child), when the unbalanced tree resembles a linked list.

**See Also:**

**References:** https://en.wikipedia.org/wiki/Binary_search_tree

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

The iterative implementation is wrong. It prints every node as root node.

Thanks Abhishek for bringing this to our notice. The conditional statement is wrong. We have corrected the code.