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.

searching in binary tree

Searching in Binary Tree in C

Searching in a binary tree involves traversing the tree to find a specific value or node. On this page we discuss two common approaches to searching in a binary tree:

  1. Searching using Level Order Traversal
  2. Searching using recursion

Algorithm Using Level Order Traversal:

  1. Initialize the queue.
  2. Add root to the queue.
  3. Until the queue is empty, add the left child and the right child of the current node.
  4. Pop the node.
  5. Traverse the queue, check whether key is equal to the value of node.
  6. If found return true otherwise false.
Searching In A Binary Tree

Algorithm Using Recursion:

  1. If root is null, return.
  2. Else Recursively check for the left subtree and the right subtree.
  3. Return true if found.
Searching In A Binary Tree 1

C Program For Searching in Binary Tree(Level Order)

Run
#include <stdio.h>
#include <stdlib.h>

struct Node
{
  int val;
  struct Node *left;
  struct Node *right;
};

int searchTree (struct Node *root, int target)
{
  if (root == NULL)
    {
      return 0;			// The target was not found
    }

  // Create a queue for level order traversal
  struct Node **queue = malloc (sizeof (struct TreeNode *) * 1000);
  int front = 0;
  int rear = 0;
  queue[rear++] = root;

  while (front < rear)
    {
      // Dequeue a node from the front of the queue
      struct Node *node = queue[front++];

      // Check if the node matches the target value
      if (node->val == target)
	{
	  free (queue);		// Free the memory allocated for the queue
	  return 1;		// The target was found
	}

      // Enqueue the left and right children of the node if they exist
      if (node->left != NULL)
	{
	  queue[rear++] = node->left;
	}
      if (node->right != NULL)
	{
	  queue[rear++] = node->right;
	}
    }

  free (queue);			// Free the memory allocated for the queue
  return 0;			// The target was not found
}

int main ()
{
  // Create a binary tree
  struct Node *root = malloc (sizeof (struct Node));
  root->val = 1;
  root->left = malloc (sizeof (struct Node));
  root->left->val = 2;
  root->left->left = NULL;
  root->left->right = NULL;
  root->right = malloc (sizeof (struct Node));
  root->right->val = 3;
  root->right->left = malloc (sizeof (struct Node));
  root->right->left->val = 4;
  root->right->left->left = NULL;
  root->right->left->right = NULL;
  root->right->right = malloc (sizeof (struct Node));
  root->right->right->val = 5;
  root->right->right->left = NULL;
  root->right->right->right = NULL;

  // Search for a target value in the binary tree
  int target = 4;
  int result = searchTree (root, target);
  if (result == 1)
    {
      printf ("The target value %d was found in the binary tree\n", target);
    }
  else
    {
      printf ("The target value %d was not found in the binary tree\n",
	      target);
    }

  target = 6;
  result = searchTree (root, target);
  if (result == 1)
    {
      printf ("The target value %d was found in the binary tree\n", target);
    }
  else
    {
      printf ("The target value %d was not found in the binary tree\n",
	      target);
    }

  // Free the memory allocated for the binary tree
  free (root->left);
  free (root->right->left);
  free (root->right->right);
  free (root->right);
  free (root);
  return 0;
}

Output:

The target value 4 was found in the binary tree
The target value 6 was not found in the binary tree

C Program For Searching in Binary Tree(Recursion)

Run
#include <stdio.h>
#include <stdlib.h>

struct Node
{
  int val;
  struct Node *left;
  struct Node *right;
};

int searchTreeRecursive (struct Node *node, int target)
{
  if (node == NULL)
    {
      return 0;			// The target was not found
    }

  if (node->val == target)
    {
      return 1;			// The target was found
    }
  else if (node->val > target)
    {
      return searchTreeRecursive (node->left, target);	// Search the left subtree
    }
  else
    {
      return searchTreeRecursive (node->right, target);	// Search the right subtree
    }
}

int main ()
{
  // Create a binary tree
  struct Node *root = malloc (sizeof (struct Node));
  root->val = 4;
  root->left = malloc (sizeof (struct Node));
  root->left->val = 2;
  root->left->left = malloc (sizeof (struct Node));
  root->left->left->val = 1;
  root->left->left->left = NULL;
  root->left->left->right = NULL;
  root->left->right = malloc (sizeof (struct Node));
  root->left->right->val = 3;
  root->left->right->left = NULL;
  root->left->right->right = NULL;
  root->right = malloc (sizeof (struct Node));
  root->right->val = 6;
  root->right->left = malloc (sizeof (struct Node));
  root->right->left->val = 5;
  root->right->left->left = NULL;
  root->right->left->right = NULL;
  root->right->right = malloc (sizeof (struct Node));
  root->right->right->val = 7;
  root->right->right->left = NULL;
  root->right->right->right = NULL;

  // Search for a target value in the binary tree
  int target = 5;
  int result = searchTreeRecursive (root, target);
  if (result == 1)
    {
      printf ("The target value %d was found in the binary tree\n", target);
    }
  else
    {
      printf ("The target value %d was not found in the binary tree\n",
	      target);
    }

  target = 9;
  result = searchTreeRecursive (root, target);
  if (result == 1)
    {
      printf ("The target value %d was found in the binary tree\n", target);
    }
  else
    {
      printf ("The target value %d was not found in the binary tree\n",
	      target);
    }

  // Free the memory allocated for the binary tree
  free (root->left->left);
  free (root->left->right);
  free (root->right->left);
  free (root->right->right);
  free (root->left);
  free (root->right);
  free (root);
  return 0;
}

Output:

The target value 5 was found in the binary tree
The target value 9 was not found in the binary tree

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion : C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++Java
  • Find size of the Binary tree – C | C++Java
  • Find the height of binary tree – C | C++Java
  • Find maximum in binary tree – C | C++Java
  • Check whether two tree are identical- CC++Java
  • Spiral Order traversal of Tree- CC++Java
  • Level Order Traversal Line by Line – C | C++Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- CC++Java
  • check whether tree is Symmetric – C| C++Java.
  • Check for Children-Sum in Binary Tree- C|C++Java
  • Sum of all nodes in Binary Tree- CC++ | Java
  • Lowest Common Ancestor in Binary Tree- CC++ | Java

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion :  C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++Java
  • Find size of the Binary tree – C | C++Java
  • Find the height of binary tree – C | C++Java
  • Find maximum in binary tree – C | C++Java
  • Check whether two tree are identical- CC++Java
  • Spiral Order traversal of Tree- CC++Java
  • Level Order Traversal LIne by Line – C | C++Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- CC++Java
  • check whether tree is Symmetric  C| C++Java.
  • Check for Children-Sum in Binary Tree- C|C++Java
  • Sum of all nodes in Binary Tree- CC++ | Java
  • Lowest Common Ancestor in Binary Tree. CC++ | Java