Searching In A Binary Tree In C

March 20, 2025

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

Insertion in a Binary Tree (Level Order)

Searching in a Binary Search Tree

Depth First Traversals

Level Order Traversal

Construct Tree from given Inorder and Preorder traversals

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