Given an Unbalanced binary search tree (BST) of M nodes. The task is to find the N elements in the Unbalanced Binary Search Tree in O(N*logM) time.
Examples:
Input: search[] = {6, 2, 7, 5, 4, 1, 3}. Consider the below tree
BST
Output:
Found
Not Found
Found
Found
Found
Found
Not Found
Naive Approach:
For each element, we will try to search for that element in the BST.
Time Complexity: O(N * M) as the tree is not balanced the height may become M. In that case, the overall complexity of searching will become O(N * M)
Auxiliary Space: O(1)
Efficient Approach: The operations can be performed efficiently by following the below idea:
First store the In-Order Traversals in an array and using binary search for searching the elements in that array because the inorder traversal of the BST will always give a sorted array.
Follow the below steps to solve the problem:
- Do a inorder traversal of the BST. i.e. O(M) time.
- Store the in-order traversal in the array.
- The array is sorted. As the inorder traversal of BST is in a sorted fashion.
- As it is Left Root Right. All Left elements are smaller than the root, all right elements are larger than root.
- Now simply use the binary search in the array.
- Return the answer.
Below is the Implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// BST nodestruct TreeNode { int val; struct TreeNode *left, *right;};// Build a new nodeTreeNode* newNode(int data){ TreeNode* temp = new TreeNode; temp->val = data; temp->left = NULL; temp->right = NULL; return temp;}// Function to insert a new nodeTreeNode* insert(TreeNode* root, int val){ TreeNode* newnode = newNode(val); TreeNode* x = root; TreeNode* y = NULL; while (x != NULL) { y = x; if (val < x->val) x = x->left; else x = x->right; } if (y == NULL) y = newnode; else if (val < y->val) y->left = newnode; else y->right = newnode; return y;}// Function for performing inorder traversal of BSTvoid inorder(vector<int>& inord, TreeNode* root){ if (root == NULL) { return; } inorder(inord, root->left); inord.push_back(root->val); inorder(inord, root->right);}// Function to search a element in the BSTbool BSTSearch(vector<int>& inord, int target){ return binary_search(inord.begin(), inord.end(), target);}void printArr(int N, vector<int>& targets, vector<int>& inorder){ for (int i = 0; i < N; i++) { if (BSTSearch(inorder, targets[i])) cout << "Found" << "\n"; else cout << "Not Found" << "\n"; }}// Driver codeint main(){ TreeNode* root = NULL; root = insert(root, 8); insert(root, 15); insert(root, 4); insert(root, 7); insert(root, 1); insert(root, 6); insert(root, 5); // BST Inorder - sorted array vector<int> inor; inorder(inor, root); vector<int> targets = { 6, 2, 7, 4, 5, 1, 3 }; int N = targets.size(); printArr(N, targets, inor); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;// BST nodeclass TreeNode { int val; TreeNode left, right;}class GFG { // Build a new node static TreeNode newNode(int data) { TreeNode temp = new TreeNode(); temp.val = data; temp.left = null; temp.right = null; return temp; } // Function to insert a new node static TreeNode insert(TreeNode root, int val) { TreeNode newnode = newNode(val); TreeNode x = root; TreeNode y = null; while (x != null) { y = x; if (val < x.val) { x = x.left; } else { x = x.right; } } if (y == null) { y = newnode; } else if (val < y.val) { y.left = newnode; } else { y.right = newnode; } return y; } // Function for performing inorder traversal of BST static void inorder(List<Integer> inord, TreeNode root) { if (root == null) { return; } inorder(inord, root.left); inord.add(root.val); inorder(inord, root.right); } // Function to search a element in the BST static boolean BSTSearch(List<Integer> inord, int target) { return inord.contains(target); } static void printArr(int N, int[] targets, List<Integer> inorder) { for (int i = 0; i < N; i++) { if (BSTSearch(inorder, targets[i])) { System.out.println("Found"); } else { System.out.println("Not Found"); } } } public static void main(String[] args) { TreeNode root = null; root = insert(root, 8); insert(root, 15); insert(root, 4); insert(root, 7); insert(root, 1); insert(root, 6); insert(root, 5); // BST Inorder - sorted array List<Integer> inor = new ArrayList<>(); inorder(inor, root); int[] targets = { 6, 2, 7, 4, 5, 1, 3 }; int N = targets.length; printArr(N, targets, inor); }}// This code is contributed by lokeshmvs21. |
Python3
# Python code to implement the approach# Binary tree nodeclass TreeNode: # Constructor to create a new node def __init__(self, val): self.val = val self.left = None self.right = None# Function to insert a new nodedef insert(root, val): newnode = TreeNode(val) x = root y = None while x != None: y = x if val < x.val: x = x.left else: x = x.right if y == None: y = newnode elif val < y.val: y.left = newnode else: y.right = newnode return y# Function for performing inorder traversal of BSTdef inorder(inord, root): if root == None: return inorder(inord, root.left) inord.append(root.val) inorder(inord, root.right)# Function to search an element in the BSTdef BSTSearch(inord, target): return target in inorddef printArr(N, targets, inorder): for i in range(N): if BSTSearch(inorder, targets[i]): print("Found") else: print("Not Found")# Driver coderoot = Noneroot = insert(root, 8)insert(root, 15)insert(root, 4)insert(root, 7)insert(root, 1)insert(root, 6)insert(root, 5)# BST Inorder - sorted arrayinor = []inorder(inor, root)targets = [6, 2, 7, 4, 5, 1, 3]N = len(targets)printArr(N, targets, inor)# This code os contributed by ksam24000 |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;// BST nodeclass TreeNode { public int val; public TreeNode left, right;}class GFG { // Build a new node static TreeNode NewNode(int data) { TreeNode temp = new TreeNode(); temp.val = data; temp.left = null; temp.right = null; return temp; } // Function to insert a new node static TreeNode Insert(TreeNode root, int val) { TreeNode newnode = NewNode(val); TreeNode x = root; TreeNode y = null; while (x != null) { y = x; if (val < x.val) { x = x.left; } else { x = x.right; } } if (y == null) { y = newnode; } else if (val < y.val) { y.left = newnode; } else { y.right = newnode; } return y; } // Function for performing inorder traversal of BST static void Inorder(List<int> inord, TreeNode root) { if (root == null) { return; } Inorder(inord, root.left); inord.Add(root.val); Inorder(inord, root.right); } // Function to search a element in the BST static bool BSTSearch(List<int> inord, int target) { return inord.Contains(target); } static void PrintArr(int N, int[] targets, List<int> inorder) { for (int i = 0; i < N; i++) { if (BSTSearch(inorder, targets[i])) { Console.WriteLine("Found"); } else { Console.WriteLine("Not Found"); } } } static void Main(string[] args) { TreeNode root = null; root = Insert(root, 8); Insert(root, 15); Insert(root, 4); Insert(root, 7); Insert(root, 1); Insert(root, 6); Insert(root, 5); // BST Inorder - sorted array List<int> inor = new List<int>(); Inorder(inor, root); int[] targets = { 6, 2, 7, 4, 5, 1, 3 }; int N = targets.Length; PrintArr(N, targets, inor); }}// This code is contributed by lokesh. |
Javascript
// JavaScript code implementationclass TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}function newNode(data) { const temp = new TreeNode(data); return temp;}function insert(root, val) { const newnode = newNode(val); let x = root; let y = null; while (x !== null) { y = x; if (val < x.val) x = x.left; else x = x.right; } if (y === null) y = newnode; else if (val < y.val) y.left = newnode; else y.right = newnode; return y;}function inorder(inord, root) { if (root === null) return; inorder(inord, root.left); inord.push(root.val); inorder(inord, root.right);}function BSTSearch(inord, target) { return inord.includes(target);}function printArr(N, targets, inorder) { for (let i = 0; i < N; i++) { if (BSTSearch(inorder, targets[i])) console.log('Found'); else console.log('Not Found'); }}const root = new TreeNode(null);insert(root, 8);insert(root, 15);insert(root, 4);insert(root, 7);insert(root, 1);insert(root, 6);insert(root, 5);const inor = [];inorder(inor, root);const targets = [6, 2, 7, 4, 5, 1, 3];const N = targets.length;printArr(N, targets, inor);// This code is contributed by ksam24000 |
Output
Found Not Found Found Found Found Found Not Found
Time Complexity : O(M + N * log M)
- In-order traversal takes O(M) for once
- BST Search is now optimized to O(log M) always irrespective of the height of BST.
Auxiliary Space: O(M), The In-order traversal needs to be stored in arrays.
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
