Questions tagged [binary-trees]
a rooted tree in which each node has no more than two children
478
questions
0
votes
1answer
13 views
Can you add up all the nodes of a special binary tree in polynomial time, in respect to the number of levels?
Let's say you have a binary tree defined by a group $S=\{a:[5,6],b:[7,67],c:[45,12],...\}$ (this group is just an example). The binary tree is constructed so that there are two starting parent nodes, $...
-1
votes
0answers
22 views
What are R trees? How it works?
I have just read about some data structure which are used rarely, one of them is R trees.
I searched a little about it and found that it is used for spatial search. The Wikipedia page says that it can ...
-1
votes
0answers
28 views
How to write a Binary tree to a file in C++
I want to serialize a binary tree into a .txt file. I am traversing the tree using bfs, to be able to just multiply by 2 (or 2+1 for right child) to jump to a left child of a node, and I want to write ...
1
vote
3answers
65 views
How balanced is a binary tree in the average case?
For algorithms involving binary trees, time or space complexity is often O(logn) in the best case of a completely balanced tree, and O(n) in the worst case of a completely unbalanced tree. Sure, it's ...
0
votes
1answer
24 views
Reassigning BT root and its children
Given the root of a binary tree, for instance below, I am running the following tests in Python:
1
/ \
2 5
/ \
3 4
Test 1:
...
2
votes
1answer
25 views
Difference between Recursion Tree & Binary Tree
What's the difference? is a Recursion tree private case of Binary tree?
2
votes
3answers
231 views
For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes
in my notes I have one fact:
in a binary tree with $n$ elements ($n$ divisible by three) there is a node $u$ such that the number of nodes in the subtree with root $u$ is at least $\frac{n}{3}$ and at ...
1
vote
1answer
87 views
prove that in binary heap buildheap function does at most 2N-2 comparison
prove that in binary heap buildheap function does at most 2N-2 comparison
I don't know how should I prove it I need some hint thanks.
buildheap procedure: we have n element and we build a heap at ...
2
votes
0answers
19 views
Repairing a perfect binary merkle forest
Let's say we have a forest of imperfect binary merkle trees of different heights (this is an invariant). Only the numbered nodes store data, the rest store hashes. Here is an example with 4 trees, ...
0
votes
1answer
20 views
Edge-disjoint paths in trees
How do I prove the following proposition?
Let $T$ be a tree, and let $S$ be a subset of the vertices. If $|S|$ is even then we can partition $S$ into pairs $(x_i,y_i)$ such that the paths $x_i-y_i$ ...
1
vote
1answer
17 views
Proof the number of expected node in a binary using mathematical induction
The following algorithm constructs a binary tree.
...
1
vote
1answer
40 views
Height of AVL tree with balance condition of 2
The maximum height of an AVL tree with a balance condition of 1 is 1.44log(n). So the worst case height is O(logn). However, if the balance condition was hypothetically 2 (meaning that the allowed ...
0
votes
0answers
22 views
Trying to convert algorithm from recursive to iterative
I have this algorithm to sum binary tree branches from leftmost branch to rightmost one, so the solution is an array of sums:
...
0
votes
0answers
33 views
Number of weight-balanced nodes in binary tree
I have to show that a binary tree with $n$ nodes has at least $(n-1)/2$ weight-balanced nodes and at most $n-1$ weight-balanced nodes. Here a node is weight-balanced if its siblings satisfy $\...
0
votes
0answers
10 views
Complexity of a cutting operation on a list of binary trees
Consider a list of full binary trees of heights $(h_0, h_1, \ldots, h_{n-1})$ where a tree with a single leaf is deemed to have height 0.
The list has the property that the height of the tree when ...
0
votes
0answers
22 views
Data structure for a queue of weighted elements
Consider a queue of elements with weights $w_0, w_1 \ldots, w_{n-1}$. The queue supports two operations:
Inserting one element at the back of the queue
Reducing the weight of one element in the ...
0
votes
0answers
15 views
Probability that BST has exact height
Consider keys $[ 1 \ldots n]$. We want to calculate probability that BST tree has height = $h$.
(We assume that distribution is uniform over all $C_{n}$ trees, where $C_n$ - n-th Catalan number).
...
1
vote
1answer
242 views
What exactly is the difference between a Balanced Binary Search Tree and an AVL tree?
I'm learning some Data Structures and I cannot figure out the difference between the Balanced BST and the AVL Tree. From my understanding, an AVL tree is a balanced tree with the height difference <...
0
votes
1answer
30 views
Depth of binary tree with few single children
The node of a binary tree is called a single child if it has a parent but does not have a sibling. The root is by definition not considered a single child.
Let $T$ be a binary tree of size $n$, and ...
0
votes
0answers
29 views
LOUDS Succinct Tree Representation
I am trying to make my Trie tree structure as compact as possible. While searching about this I came across to "Level order Unary Degree Sequence " i.e. LOUDS representations using bit ...
0
votes
0answers
21 views
Expected runtime for hashing with a binary search tree as collision handling
I thought about implementing a data structure with expected runtime of O(1) for insertion, deletion and look-up and a worst case runtime for these operations of O(log(n)). This is under the assumption ...
0
votes
2answers
28 views
Is the heap in “Data Structures Algorithms in Java” by Goodrich, Tamassia, and Goldwasser missing sentinel leaves?
In the book, Data Structures Algorithms in Java Sixth Edition by Goodrich, Tamassia, and Goldwasser on page 339, there is an
"Example of a heap storing 13 entries with integer keys. The last ...
1
vote
1answer
27 views
Range sum query - tree representation efficiency
I was reading about possible solutions to the well known problem:
Given array A with length N create a structure that enables
...
0
votes
0answers
35 views
(Searching + Splaying) in a Splay Tree
Given a tree
To search for value 1, I do the following splay operations:
i) Zag on 7
ii) Zag on 1
And hence obtain 1 in the root. But why would this be incorrect?
i) Zag on 1
ii) Zag on 1
The ...
1
vote
1answer
361 views
Why does the formula floor((i-1)/2) find the parent node in a binary heap?
I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the index of the parent of element at index i can be found with
parent ...
0
votes
1answer
63 views
How to draw the heap for an array in Java?
I have an assignment to draw the heap after an ArrayList and a LinkedList is created.
...
1
vote
1answer
30 views
5
votes
1answer
40 views
Test two LTL expression trees for equivalence
Is there an algorithm on how to check if two LTL expressions (represented as binary trees) are semantically equivalent? Since there are many smaller equivalences such as
$a\Rightarrow b \equiv \neg a \...
6
votes
0answers
153 views
Impossibility of certain type of tree traversal algorithm
I was wondering for some time how to approach a situation like the following one. Imagine a standard binary tree data structure with $n$ nodes in it. Each node contains pointers to its left and right ...
5
votes
2answers
144 views
Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2?
The title could be a little bit confusing, and it is not easy to summarize it within a sentence, therefore I will explain it in detail below. If you have any thoughts on optimizing and rephrasing the ...
0
votes
1answer
26 views
Basic Binary search tree query
Inorder traversal of BST is always sorted.But can we say Binary tree is BST if and only if inorder is sorted?I mean if inorder is sorted,can we conclude it is always BST?
2
votes
0answers
23 views
How to linearly combine loss functions to preserve optimal substructure property?
I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has ...
0
votes
0answers
33 views
Simplify logical expression represented as binary tree
I implemented logical expressions using a binary tree in C++. Now I want to be able to simplify such an expression using rules like e.g.
but have issues with the commutativity. Assuming the ...
1
vote
0answers
23 views
Recording a histogram in a tree exhibits strange best case
The task is to record a histogram from a streaming data source.
One data point is, say, a 16 bit integer. The maximum multiple of one data point before the stream ends, is < 2^32. The main ...
2
votes
0answers
24 views
Data Structures for BST where size uniquely determines shape
There are several data structures in which the number of elements uniquely determines the shape.
Examples would be binary heaps, arrays, lists, Braun trees, and Merkle mountain ranges.
Are there any ...
0
votes
1answer
39 views
Range search in a max-heap
I am having trouble with coming up for a suitable algorithm for this question. A max-heap is essentially visualized as a binary tree not a binary search tree. Also the runtime of the algorithm must ...
0
votes
0answers
9 views
Why are these BVH split heuristic formulas different?
I've been doing some research into changing the split heuristic I use for a work project comprised of a BVH binary tree.
The heuristic I currently use is centroid median as described here, but I seek ...
2
votes
1answer
121 views
Efficiently storing and modifying a reorderable data structure in a database
I'm trying to create a list curation web app. One thing that's important to me is being able to drag-and-drop reorder items in the list easily. At first I thought I could just store the order of each ...
1
vote
1answer
48 views
Best case “skew height” of an arbitrary tree
Given an arbitrary binary tree on $n$ nodes, choose an assignment $A$ from each parent to one of its children (the "favored child" as it were). We define the skew height of the tree as $H_A(\...
0
votes
1answer
3k views
What are the minimum and maximum numbers of elements in a heap of height h?
I came across the question:
What are the minimum and maximum numbers of elements in a heap of height $h$?
To which I came up with this theory:
$$\sum_{i=0}^{h-1} 2^i = 2^h-1$$
$2^h-1$ is the ...
0
votes
0answers
20 views
Recurrence Relations for Perfect Quad Trees (same as binary trees but with 4 children instead of 2)
I have to write and solve a recurrence relation for n(d), showing how I arrive at the formula and solve the recurrence relation, showing how I arrive at the solution. Then prove my answer is correct ...
0
votes
1answer
38 views
Use tree in-order traversal to determine whether a BST or Heap
Given these in-order traversal lists:
1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19
2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17
I need to determine whether each one of those lists represent a valid BST ...
0
votes
1answer
45 views
Does the heap property in the definition of binary heaps apply recursively?
The definition of binary heaps says that it should be a complete binary tree and it should follow the heap property where according to the heap property, the key ...
1
vote
1answer
40 views
Product of all nodes except for one in Binary Tree
Assume we are given a binary tree with an integer sitting at each node. I am looking for an efficient way to find for every path from the root to a leaf every possible product with exactly one node ...
11
votes
6answers
1k views
Find the number using binary search against one possible lie
We all know this classic problem, "there is some hidden number and you have to interactively guess it.", which could be solved using binary search when we know that maximum number that we can guess.
...
0
votes
1answer
37 views
How many different (full/complete) in-order binary-trees do exist?
Given be a binary tree whose elements printed in-order results in [1,2,3,4].
Q1: How many different binary-trees do exist?
Q2: How many different complete binary-...
1
vote
1answer
49 views
Can the structure of a “Complete Binary Tree”, be uniquely identified if only its pre-order or post-order or in-order traversals are given?
I am unable to reason if we can construct a complete binary tree if only one of the following 3 traversals is given: pre-order, post-order, in-order.
The following is the definition of a complete ...
1
vote
1answer
39 views
Is there an Interval Tree which supports O(1) dynamic space requirements for queries?
I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key).
In general ...
0
votes
1answer
135 views
Prove that AVL tree has this kind of property with Fibonacci sequence
Q: Prove that for any AVL tree that has $n$ nodes ($n\geq 1$)
and has a height of $h$ this property is true:
$n \geq F(h)$ where $F(h)$ is the $h$-th element in the Fibonacci sequence:
$F(0) =0, F(1)=...
0
votes
0answers
12 views
Parsing text, then searching it: one entry per position, vs. 1 JSON column per text
I have a Rails application using Postgresql.
Texts get added to the application (ranging in size -- as short as a few words, to as long as, say, 5,000 words?).
The text gets parsed, both ...
