# Tagged Questions

a tree in which each node has no more than two children

24 views

### Delete a range of keys in a binary search tree in better than $O(n\lg n)$?

Obviously, the brute force method of: ...
19 views

### Average redundancy in Huffman or Hu-Tucker codes on random symbol probabilities

Huffman and Hu-Tucker codes are well-known compression schemes, which both come close to the entropy lower bound. It is known that if $L_1$ and $L_2$ are the lengths of a Huffman resp. Hu-Tucker code, ...
52 views

### Help with proof involving weighted full binary tree

Given a full binary tree, $T$ (each node is either a leaf or possesses exactly two children), with $n$ leaf nodes: $v_1,v_2,...,v_n$, and weights associated with the leaf nodes: $w_1,w_2,...,w_n$, the ...
11 views

### How to Apply Binary Transformations?

One of the steps in Binary Index Tree algorithm is to find a node's parent which is done by un-setting the rightmost SET bit. For example: if a node has index 1010 than it's parent is 1000. To apply ...
24 views

### Sum of heights in a complete binary tree (induction)

I need to prove the following statement using induction on the number of nodes in the tree: The sum of heights of a complete binary tree is $\theta(n)$. Note: I've tried proving this using ...
28 views

### Example of height-balanced tree that is not weight-balanced

Following this question : Two definitions of balanced binary trees I am having a hard time making sense of the proofs provided and I'm looking for an example of a simple binary tree that is ...
51 views

### Huffman Code VS Hu–Tucker Code

Before I'll ask my question, let me start with my understanding of the definitions, to prevent myself with further confusion, as well as giving some background. Huffman Code is the binary-code ...
44 views

### Red Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root

I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest et al), and have been studying the deletion algorithm for red black trees. However, I am confounded at the ...
31 views

### Proof that there are same number rotation moves in any binary tree with both children compulsory

I am working on this project where I am required to find the theoretical proof for following. I have a particular type of binary trees, where 1) each internal node will definitely have two children. ...
57 views

### Optimal Binary Search Trees Knuth

Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289 Please have a look at this paper, specifically page 18 in which he tries to prove his ...
104 views

### AVL Trees Height-Balance Property

An AVL tree is one that satisfies the height-balance property which states that: For every position p of T, the heights of the children of p differ by at most 1. Below is an example AVL tree. ...
127 views

### augmenting bst - is there exist pair (a,b) of numbers such that |b-a| = d?

How to check if exist pair $(a,b)$ of numbers in BST such that $|a-b| = d$, where $d$ is given. Example: contain of tree: $1, 4, 5, 3, 8, 45, 532$ $d=5$, answer: $yes$, there is pair $(5,8)$ $d=52$ ...
35 views

### Finding the number of $L\leq j\leq R$ such that $a[j] \leq a[i]$

I have recently encountered the following problem which I heard can be solved by using BIT (binary indexed trees) but I am not sure how: Given an array $a[1, 2, \ldots, n]$ and $Q$ queries of the ...
38 views

### Binary tree algorithm asymptotic analysis problem

Assume we have a perfectly balanced Binary tree. We have the following algorithm: For each passed node, traverse through all its ancestors and then do the same algorithm for the left and right child ...
30 views

### Bounds on the number of rotations in the insertion operation of a Red Black Tree

I am having some trouble understanding why people say that contrary to what happens with AVL trees, there is a bound on the number of rotations occurring in an insertion with a Red Black Tree. From ...
44 views

### How to find a symmetric predecessor / successor [closed]

Lets say we have a binary tree $T$ and we want to insert key $k$. Now, assuming $k\not\in T$, how do we find the symmetric predecessor/successor of $k$? Does this relate to (pre/in/post)-order ...
181 views

### How do binary trees use memory to store its data?

So I know that arrays use a block on contiguous memory addresses to store data to memory, and lists (not linked lists) make use of static arrays and when data is appended to the list, if there is no ...
138 views

### Why aren't tries generally used?

To store say integers (positive), we prefer to use red black BSTs. I have never seen a explicit use of a trie anywhere to store numbers. I believe we can convert numbers to string and store them in ...
27 views

### What is the order of this traversal method?

Please see below pseudo-code for finding the max-height of a b-tree ...
200 views

### Finding median weights in all paths of an AVL tree with weighted nodes

I need some help with proving the complexity of the following problem (I'm new here, so please excuse my "newbie-ness") Given: an AVL tree with keys: $1,2,..,n$, such that each node $i$ in the tree ...
61 views

### Binary tree node value maximization

Given a binary tree, construct the set of nodes whose sum is maximum subject to the restriction: if a node is included, its parent and children must be excluded, but grandchildren, etc. may be ...
341 views

### What are the main ideas used in a Fenwick tree? [duplicate]

While I was solving a programming competition question, I came across a technique advertised as suitable for the solution. A so called Fenwick tree (a.k.a binary indexed tree) was at the heart of this ...
32 views

### Worst case bisection of binary tree

My algorithm book states that any n-vertex binary tree T can be partitioned by just removing a single edge into two disconnected trees A and B where neither of them has more than 3/4 of the vertices. ...
90 views

### How to represent an improper binary tree by means of proper binary tree

By definition: a binary tree needs to fulfill 3 requirements: 1) Each node must have at most 2 children. 2) Each node must have a left and right child 3) Left children is written before the right ...
45 views

### Are there any theorems/formulas that apply to the height of comparison trees?

I have been drawing some binary comparison trees, which correspond to compares made to sort an array, and I was wondering if there is any formula to determine the height of a comparison tree for an ...
31 views

### Two flavors of red-black trees with different performance

I've implemented two red-black trees (using the pseudo-code in CLRS) with slightly different flavors: 1) In the first tree, all the data is stored in the leaves. 2) In the second tree, the data is ...
45 views

### What does every root is at the same level mean

My textbook says a "complete binary tree" is a "full binary tree" where every root is at the same level. My conceptual understanding: All this time, I was led by my textbook to believe a root is ...
216 views

### Optimize binary search on Segment Tree by storing past result

Goal Let $A[n]$ be an arbitrary array of integers of length $n$. Let $S$ be a segment tree, represented by an array of records: each record containing the left and right bounds ($[l,r]$) of the ...
318 views

### How to solve a Simple Linear Equation using a binary tree data structure

i am currently working on a school project that takes in a simple linear equation and has to return the value of x, the code i have transforms x + 3 = 3x - 2 into a binary tree format like so: ...
51 views

### What do you mean by minimum height of a Binary Search Tree? [duplicate]

I came across the term "minimum height of a Binary Search Tree" (in Java) in class, but I don't fully understand. Could someone please elaborate on: (a) What it is ? (b) How to ...
101 views

### Failing to understand the pseudo code of the inorder traversal

Edit: Solved, see comments I don't understand how the inorder traversal traverses through the whole tree. According to wikipedia, the pseudo code for the inorder traversal is: ...
97 views

### Can nodes in red-black trees have one nil child and one non-nil child?

I don't recall hearing that nodes in red-black trees can't have one nil child and one non-nil child. However, I did hear that red-black trees have a worst-case height of $2log_2(n + 1)$, where n is ...
125 views

### Why isn't the time complexity of constructing a Fenwick tree tighter than $O(n\lg n)$?

Intuition: Suppose I have an array of nonzero integer values $A[n]$ and a partially constructed Fenwick tree of this array: $F[k], n>k$. I can see why inserting the next element would be worst ...
102 views

### Rearranging linear tree with right rotates [closed]

I ran into a fun interview question, yesterday. Can anyone help me? Suppose a binary tree with six nodes is given, such that each node has only a left child. With how many "right rotate" ...
59 views

### Efficient deletion in Fenwick tree

Suppose there is an array of nonzero integer values A[n], which has a Fenwick tree representation F[n]. The most simplistic way ...
96 views

### Algorithm to determine two binary expression trees will give the same result based on associative and commutative properties of some operators

Given n different numbers, I would like to find out whether there exists an algebraic expression using all the n numbers, with n−1 binary operators and unlimited number of parentheses, that ...
77 views

### The number of Binary Search Tree that exist with same Postorder and Inorder

how many BST exist with same postorder and inorder traversal? I know that in binary tree (Not BST), it is one. but i have a book from that said for BST it is CATALAN number. i become confused.
458 views

### Is there a way to find path length to a node from root in a binary tree?

I went through the algorithm’s for finding the LCA of two nodes in a binary tree (let’s say the values are random – not a binary search tree) and I chose the method where the path to root is stored in ...
31 views

### What is the name of this size method calculating the size of a node?

My confusion is that if the recursive call calls the left nodes, and then adds with the right nodes, how are the nodes that are to to right of the left nodes and vice versa being called? ...
510 views

### Size of decision tree and depth of decision tree

I'm doing some classification experiments with decision trees ( specifically rpart package in R). By setting the depth of a decision tree to 10 I expect to get a small tree but it is in fact quite ...
61 views

### Red Black Tree clarification

I am quite new to Red-Black trees, and therefore I am having a bit of difficult time trying to understand them. One of the properties of the Red-Black tree is that every red vertex must have two ...
648 views

### Data Structure for Representing a Math Expression

I'm looking to improve my object-oriented design skills and I came across a problem which asked to design classes to represent a mathematical expression such as (a + b) * ( c - d / e) in memory so ...
125 views

### BIT: Unable to understand update operation in Binary index Tree

I have just read this answer and was very satisfied and it is indeed a fantastic answer. It taught me the working of BIT. But at the end, the second last paragraph is where I am struggling. It says, ...
98 views

### How to write recurrence relation for the following scenario?

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function $g(x)$ for each node x. If the cost of computing $g(x)$ is min{no. of leaf-nodes in ...
175 views

### What is the advantage of Day-Stout-Warren algorithm for balancing BST?

While reading about Day–Stout–Warren algorithm for balancing BST which takes any BST and transforms it into a balanced BST in O(n) time. In my opinion I can ...
34 views

### A BST can be broken by accessing one of its nodes, how can I always make sure this happens? [closed]

I have an assignment that asks for this. So I am not looking for the answer itself but a hint on how to find a value that will always break the BST condition by myself. If I have access to any node N ...
40 views

### How to reconstruct Binary Tree from path encoding?

Suppose I have inputs of the following form: (11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) () whereby the second field indicates the path from the root node, and empty field ...
234 views

### Infix to prefix

According to this algorithm: http://en.wikipedia.org/wiki/Shunting-yard_algorithm when a left parenthesis is found, it is inserted into the stack, and when a right parenthesis is found, we pop all ...
Suppose that I have a binary tree with $N = 2^h - 1$ nodes, initially all nodes are unmarked Over time via this process nodes became marked. Suppose that nodes have unique identifiers in range of ...