Searching In A Binary Tree In C++
Searching In A Binary Tree
Given a tree and the number, we need to find to check whether the number is present in the binary tree or not. There can be different ways to approach this problem. In this articles, two ways are discussed, level order and recursion.
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 root is null, return.
- Else Recursively check for the left subtree and the right subtree.
- Return true if found.
Code (Level Order):
Time Complexity For Searching Element In A Tree
O(n) Queue and Recursion
O(1) Queue and Recursion