Search the Element in a binary tree - With and Without Recursion

Objective: Given a binary tree and a given number x, Write a recursive algorithm to search the element in the tree.

This is one of the very basic problems of trees. If you are new to binary trees, this problem might help you to understand the tree. First, we will see the recursive solution then I will show you how to solve it without recursion.

Approach:

Recursive Approach:

The approach will be very simple, do any of the tree traversal(inorder, preorder, postorder, BFS or DFS) and check if the given element is present.

Run This Code

Code:

Does 4 exist in the tree: true

Does 7 exist in the tree: false

Non-Recursive Approach:

1. If we are not using recursion then we need a data structure to store the tree traversal, we will use a queue here
2. Add root to the queue
3. Check if the current node has the element we are looking for if yes then return true else add children nodes of the current node to the queue
4. If queue gets empty, which means we have not found the element

Run This Code

Code:

Output:

Does 4 exist in the tree: true

Does 7 exist in the tree: false

Also Read:

- Check if Two BST's are Identical Beginner
- Backtracking - Rat In A Maze Puzzle Hard
- Merge Sort - Updated - Most Efficient ways to Implement Medium
- Construct a Binary Tree from Given Inorder and Depth-First-Search. Hard
- Binary Tree-Postorder Traversal - Non Recursive Approach Beginner
- Reverse a Stack using recursion - In Place (Without using extra memory) Hard
- Make a Binary Tree from Given Inorder and Preorder Traveral. Hard
- Print All The Full Nodes in a Binary Tree Beginner