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

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

This is one of the very basic problems of tree. 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:

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

Code:


Output:

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 queue here
  2. Add root to the queue
  3. Check if current node has the element we are looking for if yes then return true else add children nodes of current node to the queue
  4. Ff queue gets empty, means we have not found the element

Code:


Output:

Does 4 exist in the tree: true

Does 7 exist in the tree: false

 

2 Responses

  1. Ali Haider says:

    very well explained…Search Element in Binary Search Tree is also explained with very easy demonstration here:
    https://youtu.be/7v-6447o5Q8

  2. lipsa patel says:

    Non Recursive approach can be done using stack.

    private static boolean nonRecursiveSearchElementInBinaryTree(BinaryTreeNode root, int data) {
    if (root != null) {

    Stack stack1 = new Stack();

    //Push root node
    stack1.push(root);

    while(!stack1.isEmpty()) {
    BinaryTreeNode poppedNode = stack1.pop();

    if (poppedNode.data == data) {
    return true;
    }

    if (poppedNode.left != null) {
    stack1.push(poppedNode.left);
    }

    if(poppedNode.right != null) {
    stack1.push(poppedNode.right);
    }
    }
    }
    return false;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: