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

learn more… | top users | synonyms

-3
votes
0answers
13 views

Min/Max Depth of a binary tree [on hold]

Is the Min Depth of this tree 2, because of the distance of leaf node "9"? Is the Max Depth if this tree 4, because of the distance of leaf node "2"?
4
votes
0answers
49 views

Does this data structure already exist, and is there a better alternative?

Consider a polymorphic Haskell function type, like the type for .: (a -> b) -> (b -> c) -> a -> c This type ...
0
votes
0answers
47 views

A problem of weight-balanced tree [on hold]

I'm interested in the problem described here : Is finding a weight-balanced tree NP-hard? (and here for a restricted version : Dynamic programming to find the least possible balance of a full binary ...
0
votes
0answers
56 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 ...
4
votes
1answer
111 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 ...
0
votes
1answer
17 views

What is the order of this traversal method?

Please see below pseudo-code for finding the max-height of a b-tree ...
0
votes
1answer
65 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 ...
0
votes
1answer
55 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 ...
0
votes
1answer
161 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 ...
2
votes
2answers
21 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
26 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
39 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
26 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
42 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
184 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
205 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
40 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
77 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
61 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 ...
6
votes
2answers
112 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 ...
-3
votes
2answers
64 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
50 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
69 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 ...
-1
votes
1answer
67 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
201 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
23 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
110 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
46 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
484 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
77 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
82 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
100 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
32 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
33 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
206 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
93 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
113 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
43 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
53 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
149 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 ...
3
votes
1answer
134 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
55 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
150 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
48 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
1k 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: ...
2
votes
2answers
274 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
328 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
120 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
578 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?