Searching In A Binary Search Tree In C++
Searching In A Binary Search Tree
A binary search tree is a tree in which the data in left subtree is less than the root and the data in right subtree is greater than the root.Given a Binary Search tree and a key, check whether the key is present in the tree or not.
Algorithm Using Level Order Traversal:
- Initialize the queue.
- Add root to the queue.
- Until the queue is empty, add the left child and the right child of the current node.
- Pop the node.
- Traverse the queue, check whether key is equal to the value of node.
- If found return true otherwise false.
Algorithm Using Recursion:
- If tree is empty return.
- Check whether key is greater or smaller than root.
- If greater, move to the right subtree. Otherwise move to the left subtree.
- If Key is found return true.
Code (Using Level Order):
Time Complexity For Searching Element In A Binary Search Tree
O(n) Queue and Recursion
O(1) Queue and Recursion