# Questions tagged [binary-search]

2398 questions

1

votes

2

answer

386

Views

### Smallest element in tree that is bigger than x

If I want to find the smallest element in a tree that is bigger than an element x, would this be a correct way to do it?
class Node {
int data;
Node left, right;
}
Node root;
public Integer successorOf(int x) {
return successorOf(x, root);
}
private Integer successorOf(int x, Node n) {
if (n == nul...

1

votes

1

answer

18

Views

### Designing data structure which can decrease range in lgn

I was asked in an exercise to design a data structure which can handle the following methods in logarithmic time complexity (lgn):
Insert(x): Inserts x to the data structure
Find(x): Finds if x exists in the data structre
Decrease(x, y): Adds negative value y (y

1

votes

1

answer

275

Views

### convert non balanced binary search tree to red black tree

Is it possible to convert a non balanced BST (the size of the tree is n and the height is h) to RBT in time complexirty of O(n) and space complexity of O(h)?

1

votes

0

answer

24

Views

### in given number x , can i check if x exist in the array with time complexity of log(n)+log(m)?

Given a two-dimensional array sorted in size of NxM so that:
The rows are sorted from left to right - from large to small.
The cols are sorted from up to down - from large to small.
in given number x , can i check if x exist in the array with time complexity of
log(n)+log(m)
?

1

votes

2

answer

52

Views

### Finding kthSmallestElement in the BST

I am trying to solve the following question from LeetCode:
https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/
The aim is, given a BST, we have to find out the Kth-smallest element in it and return its value.
I could come up with a O(n) time and space solution myself. But anoth...

1

votes

0

answer

64

Views

### My binary search on java doesn't count or print the right index values after the search

I am programming a class that when called upon, would search for a specific number using binary search. The program would also print the number of times it searched for a said number, and return the index value. Unfortunately, the index value always returns me a -1, which is the number I set it as w...

1

votes

2

answer

52

Views

### Binary search with process output

Expected output :
If the key is below the mid point
Data : [1, 4, 6, 13, 14, 23, 30, 45, 58, 67, 76, 89, 99]
Input key : 6
Binary Search :
1 step index - 0 : 1, not found !
2 step index - 1 : 4, not found !
3 step index - 2 : 6, founded !!
If the key is greater than mid point
Data : [1, 4, 6, 13, 14...

1

votes

1

answer

27

Views

### Java BST program crashes when I call self implemented search method

I have been trying to figure out why my program keeps crashing. When I compile in eclipse everything runs smoothly until I select the 'search' option in my menu driven BST. I keep getting the error java.lang.NullPointerExcpetion. Part of me feels as if my add method is not working properly when crea...

1

votes

1

answer

425

Views

### Print a binary search tree as a single string

There's a practice problem that I've been working on that's been confusing me.
Define a function treeLevelOrder which satisfies the following claim:
If Q is a binary search tree of integers, then treeLevelOrder(Q) is the String representation of the contents of Q according to their level in the tree...

1

votes

0

answer

70

Views

### Binary Search Output Issue in Inventory Program c++

I am having issues with binary search function within my homework (I am completely done with it except for this one issue).
The program allows a user to manage the inventory of a small store that sells various products of any type. It will first read the inventory from a text file named “inventory...

1

votes

2

answer

20

Views

### Java BNST toString

So I'm working on a school project of an implementation a binary search tree. I have to create a toString method that returns all nodes as string. I was able to do it as a void but I'm having a hard time figuring out how to return a String of all the nodes.
Heres my working void toString function....

1

votes

1

answer

176

Views

### Binary search not working for all test cases

I'm trying to implement a recursive binary search in Java, however, it it not working for all test cases. I am doing a Hacker rank challenge, and it is not showing me the test cases I've missed. When I test it with my own cases, it always tests successfully. I don't know what I'm missing.
import jav...

1

votes

1

answer

403

Views

### Iterative binary search with only two comparisons?

Adjust the iterative binary search code so that it uses only two comparisons instead of three (in
the main while loop). *Note: The three comparisons are in the while loop, and two if statements
within the loop.
#include
int ItBinarySearch(int arr[], int len, int target) {
int first = 0;
int last =...

1

votes

1

answer

77

Views

### Tricky Segmentation faults with BST recursion in C

I'm trying to add strings to a Binary Search Tree using a recursive insert method (the usual for BSTs, IIRC) so I can later print them out using recursion as well.
Trouble is, I've been getting a segmentation faults I don't really understand. Related code follows (this block of code is from my main...

1

votes

0

answer

112

Views

### C - printing to a file results in garbage characters but printing to stdout doesn't?

I made this thread a few hours ago:
Tricky Segmentation faults with BST recursion in C
Managed to figure it out after hours of trying. I've run into another snag, however. It's a weird one. Relevant code for perspective:
extern char *optarg;
extern int optind;
int c, err = 0;
char currentLine[STRING...

1

votes

0

answer

233

Views

### C++ BST remove: deleted a whole sub-tree when removing a node with 2 children

I'm implementing a C++ binary search tree and is trying to write a function that removes a certain node. The code works well for a leaf node (no children) and node with one child, but every time when it tries to delete a node with 2 children it will delete a whole sub-tree.
struct Node {
string key...

1

votes

1

answer

317

Views

### Binary search to solve 'Kth Smallest Element in a Sorted Matrix'. How can one ensure the correctness of the algorithm,

I'm referring to the leetcode question: Kth Smallest Element in a Sorted Matrix
There are two well-known solutions to the problem. One using Heap/PriorityQueue and other is using Binary Search. The Binary Search solution goes like this (top post):
public class Solution {
public int kthSmallest(int[]...

1

votes

1

answer

110

Views

### delete subtree from bst and balance the tree in logn time

Is it possible that we could perform m insert and delete operations on a balanced binary search tree such that delete operation deletes a node and the whole subtree below it and after that balance it? The whole process being in done in amortized O(log n) time per step?

1

votes

0

answer

57

Views

### Should a kd tree be balanced like a binary search tree?

I tried coding a kd tree and a binary search tree. I'm wondering why the bst gives me stack overflow error when inserting unbalanced data while the kd tree does not.
code for the binary search tree:
void insert(node *&_node, int _val) { //bst insert function, will change raw pointers to smart pointe...

1

votes

1

answer

39

Views

### returning result from binary search tree

I'm trying to determine if a value is found in the binary search tree.
If it's found, the value is printed. If not, a message is printed saying it wasn't found.
My problem is that even when the value is found, the message is printed saying that it wasn't found.
My result seems to reset even after...

1

votes

1

answer

141

Views

### What is the utility of treap data structure?

I am currently studying advanced data structures and I came across a weird data structure called Treap. I understand what Treap is but I can't seem to find it's utility in a valid use case scenario.
Why should you use such a data structure and in what type of problems/conditions treaps are best used...

1

votes

1

answer

91

Views

### Recursive Removal in Binary Search tree

I am working on a binary search tree and I have gotten a little stuck in my recursive remove method. Everything seems to work except when I try to remove from the very top root. When I want to remove from the root I am to replace it with the smallest value to the right of the root. It works for ever...

1

votes

1

answer

40

Views

### Binary Search on Generic Array returning first two Index or Stackoverflow Exception

Homework Question! We are using Binary Searches with Generic Arrays and Comparator. The assignment requires we have Integer / Double / String type arrays and that we can search each of them with a Binary Search. I have successfully used Binary Searching on non-Generic arrays before, this is a bit mo...

1

votes

1

answer

92

Views

### How to change my function into a constructor?

I need to make a parametrized constructor that creates a perfectly balanced binary search tree given a sorted array. I know how to make a function that creates the BST but how can I make the BST from a constructor?
This is my function:
node * sortedArrayBST(double * arr, int start, int end)
{
int m...

1

votes

1

answer

177

Views

### Creating a Red-Black tree from BST tree - the fastest way?

I have to create and describe an algorithm for my university course that gets a BST tree T and creates new BST tree T' that satifies properties (and is as fast as possible):
1) T' has the same exact key values as T
2) T' is a Red-Black tree
So far I've had only one idea: randomize 0 or 1. In case...

1

votes

1

answer

47

Views

### Induced height imbalance in AVL tree

If a node is inserted in an AVL tree, it might happen that one of the nodes in the path to the new_node would lose height balance. But my question is if that node is fixed, can other nodes above it (the ancestors till the root) would still retain height imbalance (in case they lost the balance earli...

1

votes

1

answer

33

Views

### insert function keeps recreating root node

I'm trying to create a non-recursive insert() function. The only example I have in the book is a recursive one and I'm trying to convert it. Just so you have an idea of what I'm trying to accomplish and why I'll include the instructions.
Write a class for implementing a simple binary search tree cap...

1

votes

1

answer

132

Views

### Binary Search Tree searching a string by letter [closed]

Hi I am a novice programmer trying to figure out how to search for a string in a binary search tree using only the first letter it starts with, for example if a just search for the letter 'L' it should bring up all names starting with that letter. Below is the method on how we search for the full na...

1

votes

1

answer

41

Views

### Why is my Binary Search Tree Delete not working?

Binary Search Tree can require a big program, so I decided not to post the rest of the code. I'm getting some null pointer exceptions, because I think I'm not understanding where to put a curly brace within my delete function. Can anyone help me find the problem and explain why? I/O at the bottom:
/...

1

votes

1

answer

465

Views

### best time complexity to check if binary tree is avl tree (height balanced)

So I was asked in an interview, if its possible that checking if tree is avl tree, could be :
T(n) = O(log(n))
and didn't know the answer, after searching in google, the best algorithms I saw was O(n) ('https://www.geeksforgeeks.org/how-to-determine-if-a-binary-tree-is-balanced/')
is it to make alg...

1

votes

1

answer

23

Views

### BST delete method doesn't delete the first node inserted

I can't figure this out... I can insert and sort items with no issue, I can delete nodes past the first insert, but on the special case that I'm trying to delete the first node inserted to start the tree, it doesn't do anything.
I'm not understanding why this issue is happening, any help to figure o...

1

votes

0

answer

37

Views

### Inequality Subsetting in data.table - Binary Searching

I'm having an issue getting a subset in data.table to run quickly. Suppose we have a data set with a column 'keyCol', and we want the sub-set where keyCol == 2. As I understand it, typically, the most efficient subset is something along the lines of:
setkey(dt, keyCol)
dt[.(2)]
This is the keyed bin...

1

votes

4

answer

452

Views

### Find all objects in an ArrayList that satisfy a list of criteria in Java

For a concrete example, I have a class City that looks like this:
public class City {
private String name;
private int total; // total population
private int men; // male population
private int women; // female population
// constructor and getters...
}
I want to write a method that can take a lis...

1

votes

1

answer

77

Views

### Binary search recursive number of calls?

So I was wondering, in my book, recursive binary search is implemented as follows:
private static int bin(int[] arr, int low, int high, int target){
counter++; //ignore this, it was to count how many calls this function invocated
if(low > high) return -1;
else{
int mid = (low+high) / 2;
if(target ==...

1

votes

0

answer

64

Views

### Create and Search BST from a txt file

I am currently in an intro data structures class and am really struggling with one of our problems about Binary Search Trees. This is the first time I have implemented this data structure and am doing my best to learn it.
Problem:
The program is supposed to create and search a BST of name and occur...

1

votes

0

answer

59

Views

### Data structure for finding lines in between two heights

I am implementing a simple application, where I have a bunch of lineHeights stored like so:
lineHeights = [2, 4, 5, 7, 2, 4, 5, /* ... */]
Now given two heights, a and b I need to find the range of lines in between a and b
For example, if the heights are [2, 2, 4, 5, 2], then the range of lines in b...

1

votes

0

answer

39

Views

### analyzed BST height balanced

I was looking at the code for checking if a BST is height balanced and have a question in understanding the following code.
def is_balanced(cur_node) :
if (not cur_node) :
height = 0
return True, height
is_left_balanced, left_height = TreeNode.is_balanced(cur_node.left)
is_right_balanced, right_heig...

1

votes

0

answer

105

Views

### Level Order Traversal BST Code

I was wondering if someone can review my code for level order traversal in a BST. I am suppose to have [[3],[9,20],[15,7]] but instead I get [[3],[9],[20],[15],[7]] I know I need an outer while loop but, not sure how to construct it.
# Definition for a binary tree node.
# class TreeNode:
# def _...

1

votes

1

answer

85

Views

### Idiomatic Kotlin for Level Order Traversal of BST

Following is my implementation of Level Order Traversal of a BST:
fun levelOrder(): Iterable {
class InternalNode(val node: Node, val level: Int)
val yetToVisit = emptyQueue()
val visited = emptyQueue()
root?.also { yetToVisit.enqueue(InternalNode(it, 1)) }
while (!yetToVisit.isEmpty) {
do {
val nod...

1

votes

2

answer

56

Views

### Binary Search Tree (Python) not showing result

I'm somewhat new to Python and need help with an issue I'm facing. I'm trying to make a binary search tree. I've written a code and it works, but won't show any result (printed values). I can't figure out what the issue might be. Here is the entire code:
class Node:
def __init__(self, value):
self.v...