- 0
Notifications Mark All Read
- Login
- Get Prime
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 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:
- Searching using Level Order Traversal
- Searching using recursion
Algorithm Using Level Order Traversal:
- Initialize the queue.
- Add root to the queue.
- Until the queue is empty, add the left child and the right child of the current node.
- Pop the node.
- Traverse the queue, check whether key is equal to the value of node.
- If found return true otherwise false.
Algorithm Using Recursion:
- If root is null, return.
- Else Recursively check for the left subtree and the right subtree.
- Return true if found.
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
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
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
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- C| C++| Java
- Spiral Order traversal of Tree- C | C++| 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.- C| C++| 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- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
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
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- C| C++| Java
- Spiral Order traversal of Tree- C | C++| 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.- C| C++| 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- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java
Login/Signup to comment