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

learn more… | top users | synonyms

0
votes
1answer
66 views

What are the main ideas used in a Fenwick tree?

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 ...
2
votes
2answers
14 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. ...
0
votes
0answers
12 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 ...
1
vote
1answer
31 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 ...
2
votes
0answers
25 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 ...
0
votes
1answer
36 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 ...
6
votes
1answer
155 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 ...
2
votes
1answer
137 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: ...
-1
votes
1answer
34 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 ...
0
votes
0answers
70 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: ...
1
vote
1answer
48 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 ...
4
votes
1answer
69 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 ...
-4
votes
2answers
56 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" ...
3
votes
0answers
38 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 ...
0
votes
1answer
50 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 ...
0
votes
1answer
56 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.
0
votes
2answers
151 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 ...
0
votes
1answer
21 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? ...
1
vote
1answer
42 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 ...
1
vote
2answers
40 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 ...
4
votes
2answers
390 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 ...
1
vote
2answers
66 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, ...
1
vote
1answer
70 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 ...
0
votes
1answer
64 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 ...
0
votes
1answer
30 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 ...
0
votes
0answers
26 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 ...
0
votes
1answer
153 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 ...
2
votes
0answers
86 views

Marking nodes of a complete binary tree

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 ...
1
vote
0answers
93 views

binary search trees: node trees vs. leaf trees

In the book "Advanced Data Structures", Chapter 2 ("Search Trees"), the author, Peter Braß, mentions two versions of binary trees (emphases in the quoted text are mine): "...two different models ...
0
votes
1answer
34 views

Need clear explanation to Range updates and Range queries in Binary Indexed trees?

I have gone through few tutorials about how to perform range updates and range queries using Binary indexed tree. I have even gone through Range update + range query with binary indexed trees . I'm ...
1
vote
1answer
47 views

Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists?

My best attempt at a specific case of the problem where $n =$ 256: For a specific case that a RB tree has 256 nodes, we can use the RB tree theorem to deduce that the height of the tree $h \leq ...
3
votes
3answers
108 views

When inserting into a binary tree, is there a universal agreed upon place to insert then new node to minimize complexity?

Do programmers (in real life), always insert at the top node or somewhere else? Because in my text book CLRS it is not made very clear, so the insertion process can take a best case of O(1), if you ...
1
vote
0answers
101 views

Running time analysis of a segment tree

Can someone provide an analysis of the update and query operations of a segment tree? I thought of a way which goes like this - At every node, we make at most two recursive calls on the left and ...
-2
votes
1answer
45 views

How do I interpret a binary tree generated using Huffman coding algorithm?

In the lecture note here, a binary tree was generated from the huffman algorithm. However it did not explain what this graph mean. From this binary tree, what can we say about the encoding for the ...
3
votes
0answers
132 views

Range bit inversions and range set bit queries with a binary indexed tree

I am trying to solve this problem using a binary indexed tree. The problem can be summarized as follows: You are given a series of commands that operate on an array initially all zeroes. ...
1
vote
1answer
47 views

Finding Triples that satisfy modulo equation in $O(n\log n)$ time

Given $n$, I am trying to count the number of values $(a,b,c)$ that satisfy the following equation in $O(n\log n)$ time. I do not need the values themselves only the number of total values that ...
5
votes
1answer
445 views

Range update + range query with binary indexed trees

I am trying to understand how binary indexed trees (fenwick trees) can be modified to handle both range queries and range updates. I found the following sources: ...
1
vote
2answers
232 views

Dynamic programming to find the least possible balance of a full binary tree

I am given $n$ positive integers $x_1,x_2,\cdots,x_n$ as input. These are the weights of the leaves in a full binary tree, $x_1$ being the leftmost leaf and $x_n$ the rightmost leaf. The weight of an ...
3
votes
2answers
311 views

Binary Indexed Trees: Why does i & -i work?

I already read this related question on the intuition behind binary indexed trees, and while the answer explains how the tree structure works, it does not really explain how this correlates back to ...
2
votes
1answer
46 views

Proof that a node N balanced binary search tree has $2^i - 1$ children where $i$ is the position of the first 1-bit in N, starting from 0

I was binary indexed trees and I came across this article. One part of the justification was the following: Given that the (binary search tree) tree is perfectly balanced, a node N will have ...
0
votes
1answer
102 views

What if traversal order of two of pre-order, in-order and post-order is same?

Supposing a tree T has the identical: Pre-order traversal and in-order traversal Pre-order traversal and post-order traversal In-order traversal and post-order traversal How does T look like? ...
8
votes
1answer
546 views

Does a graph always have a minimum spanning tree that is binary?

I have a graph and I need to find a minimum spanning tree to a given graph. What is to be done so that the output obtained is a binary tree?
0
votes
1answer
16 views

Estimate the running time of counting nodes in a binary tree

I am asked to write an efficient method that computes the number of nodes in T, and here is what I did: ...
2
votes
0answers
31 views

How to find number of occurences of specific distances in binary (search) trees?

I want to calculate the amount of tree structures that have a given maximal distance between two nodes given an amount n of nodes (or keys). E.g. with ...
0
votes
2answers
103 views

Is randomly building a BST different from random sampling whole trees?

What is the difference between a randomly built binary search tree (using n keys )and choosing a binary search tree (of n key) from a random distribution
-1
votes
1answer
67 views

Max heap conversion

In the binary tree shown below, which of the following trees is created after conversion into a (max) heap? There are 4 anwsers to choose : By definition, a max heap is a complete binary tree ...
0
votes
2answers
47 views

Elements in a less than a value in a subarray

Let A be an fixed array of size n. Q(i,j,k) is number of elements from A[i] to A[j] which are less than k. Currently I am using segment tree with each node containing sorted array of leaf elements. ...
0
votes
0answers
109 views

Proof by induction for a splay tree?

I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is: Prove by induction that if all nodes in a splay ...
1
vote
1answer
86 views

Smallest(k) in red-black tree. How is it O(logn)?

Is it the same as find minimum for a binary search tree? I know recoloring runs in O(logn) and rotations are O(1). Even if we are wanting it to find the 'k-th' smallest key in the red-black tree. ...
7
votes
3answers
1k views

When are binary trees better than hashtables in real world applications?

I am currently bushing up on my data structures and basic algorithms, part of that is the Binary Tree. I do understand the algorithms, and how to implement a binary search tree and such. I do so how ...