Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given a binary tree and a given num­ber x, Write an recur­sive algo­rithm to search the ele­ment in the tree.

This is one of the very basic prob­lems of tree. If you are new to binary trees, this prob­lem might help you to under­stand the tree. First we will see the recur­sive solu­tion then I will show you how to solve it with­out recursion.

Approach:

Recur­sive Approach:

Approach will be very sim­ple, do any of the tree tra­ver­sal(inorder, pre­order, pos­torder, BFS or DFS) and check if given ele­ment is present.

Code:

Out­put:

Does 4 exist in the tree: true

Does 7 exist in the tree: false

Non-Recursive Approach:

  1. If we are not using recur­sion then we need a data struc­ture to store the tree tra­ver­sal, we will use queue here
  2. Add root to the queue
  3. Check if cur­rent node has the ele­ment we are look­ing for if yes then return true else add chil­dren nodes of cur­rent node to the queue
  4. Ff queue gets empty, means we have not found the element

Code:

Out­put:

Does 4 exist in the tree: true

Does 7 exist in the tree: false

 

You may also like...