The third paragraph of wikipedia's article on AVL trees says: "Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications." So, shouldn't T...

I am working on a project that rewards people base on referrals (MLM) I have been able to count the total number of child nodes on both left and right side but now I need to be able to update the ...

What is the time complexity of applying the next() and prev() function on an multiset<int>::iterator type object where the corresponding multiset contains the N elements? I understand that i...

I have implemented a binary search tree in c++. Instead of using bare pointers to point to a nodes children I used the std::shared_ptr. The nodes of the tree are implemented as follows struct tree...

Given an array of integers arr = [5, 6, 1]. When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child. Now if our input is c...

I know this is a common question and I saw a few threads in Stack Overflow but still couldn't get it. Here is an accepted answer from Stack overflow: " Disk seeks are expensive. B-Tree structu...

I'm implementing an algorithm to do directory matching. So I'm given a set of valid paths that can include wildcards (denoted by "X"). Then when I pass in an input I need to know if that input matc...

I have a homework assignment that reads as follows (don't flame/worry, I am not asking you to do my homework): Write a program that sorts a set of numbers by using the Quick Sort method using a bi...

I need to define a binary search tree where each node has access to the parent: enum Tree<'a> { Leaf, Node { left: Box<Tree<'a>>, right: Box<Tree<'a>>, par...

I am very confused by a number of articles at different sites regarding constructing a Binary Search Tree from any one traversal (pre,post or in-order), or a combination of any two of them. For exa...

For each of these operations would a balanced binary search tree complete the task in a faster big oh time than a balanced binary tree? Finding the smallest item in the tree. I think balanced B...

I use the following method to traverse* a binary tree of 300 000 levels: Node* find(int v){ if(value==v) return this; else if(right && value<v) return right->find(v); else if(l...

class BinaryNode: def __init__(self, value): self.data = value self.left = None self.right = None def contains(root, value): if root is None: return False if value == root.data: return Tr...

I'm learning about B+ trees in a class about databases and I was wondering what concrete advantages B+ trees would give over Binary Search Trees? It seems like they both have O(logN) average comp...

I'm prepearing for tech interview, so basically learning algorithms from very beginning :) we are given a BST. I need to find the max length of a desc path in it, which always goes left or right In...

If each node in a binary search tree stores its weight (number of nodes in its subtree), what would be an efficient method to compute a rank of a given node (its index in the sorted list) as I sear...

I have got a question, and it says "calculate the tight time complexity for the process of inserting n numbers into a binary search tree". It does not denote whether this is a balanced tree or not....

Given a binary search tree (BST) of height h, it would take O(k+h) time to apply the BST InOrder Successor algorithm k times in succession, starting in any node, applying each next call on the node...

I recently finished implementing a Binary search tree for a project I was working on. It went well and I learned a lot. However, now I need to implement a regular Binary Tree... which for some reas...

Consider the deletion procedure on a BST, when the node to delete has two children. Let's say i always replace it with the node holding the minimum key in its right subtree. The question is: is th...

I'm currently implementing an algorithm in which I need to know how many numbers, from the ones that have already been read, are smaller than the one that's currently being processed. A way to do ...

I am not good at programmatically implementing a heuristic search algorithm / Dijkstra's algorithm/ A* search algorithm mentioned. However, while solving a problem mentioned in one of my post (Matr...

I would like to calculate the summation of the depths of each node of a Binary Search Tree. The individual depths of the elements are not already stored.

Why is the average case time complexity of tree sort O(n log n)? From Wikipedia: Adding one item to a binary search tree is on average an O(log n) process (in big O notation), so adding n item...

Grid Walking (Score 50 points): You are situated in an N dimensional grid at position (x_1,x2,...,x_N). The dimensions of the grid are (D_1,D_2,...D_N). In one step, you can walk one step ahead or ...