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

learn more… | top users | synonyms

0
votes
0answers
60 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
33 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 ...
2
votes
1answer
39 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
54 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
28 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
32 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
33 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
97 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
20 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
24 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
28 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
253 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
52 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
49 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
35 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
28 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
21 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
51 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
77 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
62 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
30 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
39 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
79 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
95 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
40 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
125 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
46 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 ...
4
votes
1answer
315 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
202 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
293 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
41 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
84 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
490 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
12 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
96 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
48 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
45 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
103 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
70 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 ...
1
vote
1answer
79 views

Proving correctness of an AVL-Tree colouring algorithm

I came up with the following recursive algorithm to colour the nodes of an AVL tree so that the resulting tree is red-black. The logic is that the algorithm first colours the root and, recursively, ...
1
vote
0answers
68 views

Ranking in complete binary trees

I have a binary tree, the node has two subtrees, every node except the the leaves, has 2 children and all the leaves are at the same level. I want to know the worst and best case complexities when I ...
1
vote
1answer
84 views

Prove any binary tree with $n$ nodes has at least $1+\log_2 n$ levels

Prove that any binary tree with $n$ nodes has at least $1+\log_2 n$ levels. I tried setting $n=8$ and plugging in $8\geq\log_2 8 = 8\geq 3$. But I'm not sure how I can prove this by induction.
0
votes
0answers
83 views

Randomized algorithm to make a Binary Search Tree from an array of $n$ distinct elements

An array $\mathcal{A}$ of $n$ distinct integers $\{a_1,a_2,\ldots,a_n\}$ is given. I'm asked to design a randomized (esp. Las Vegas) algorithm to make a Binary Search Tree out of these elements, such ...
1
vote
1answer
50 views

What kind of order is binary tree ancestry?

Let isAncestor be a relation on binary tree nodes such that isAncestor x y means y can be ...
-2
votes
1answer
41 views

Inequality to be disproved

Suppose that a search for a key in a binary search tree ends up in a leaf. Consider three sets : A,the keys to the left of the search path B,the keys on the search path C, the keys to the right of the ...
1
vote
1answer
201 views

Binary tree traversals reversed

Am I correct in saying that traverse(node): if node is null, return print node traverse(node's right subtree) traverse(node's left subtree) would ...
0
votes
0answers
25 views

How to insert and delete in vantage-point tree?

I'm trying to implement a vantage point tree, but am having trouble determining how insertion and deletion functions would be implemented. Can you describe these operations?
2
votes
1answer
144 views

Check whether it is possible to turn one BST into another using only right-rotations

Given two binary search trees T1 and T2, if it is possible to obtain T2 from T1 using only right-rotation, we say that T1 can be right-converted to T2. For example, given three binary search tree T1, ...