Questions tagged [binary-trees]
a rooted tree in which each node has no more than two children
482
questions
0
votes
0answers
12 views
Can an LTL formula uniquely be represented by an expression tree?
Just like we can represent a mathematical expression uniquely with a binary expression tree, I was wondering if we could do the same for LTL formulae? Such that no two different looking LTL formula ...
0
votes
1answer
29 views
Prove that in a tree where each node has 0 or 2 children, number of nodes with 0 child is one more than the number of nodes with 2 children
How to prove
In a tree where every node has either $0$ or $2$ children, the number of nodes with $0$ child is $1$ more than the number of nodes with $2$ children.
1
vote
0answers
30 views
Weight of lowest common ancestor satisfies strong triangle inequality
How do I prove that $d(x,y)$, defined as the weight of the lowest common ancestor of $x,y$, satisfies the strong triangle inequality:
$$ d(x,y) \le \max(d(x,z), d(y,z)) $$
How do I even start such a ...
3
votes
0answers
45 views
How to find the Expected height of a randomly built binary tree
I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or ...
0
votes
0answers
21 views
Order-statistic tree: Worst-case running time of a sequence of $n$ insertions/deletions and $m$ calls to SELECT operation
Assume I have an order-statistic tree, $T$, which is a red-black tree where every node $x$ also has the attribute $x.size$. How can I compute the worst-case running time of an arbitrary sequence of $n$...
0
votes
2answers
40 views
Assigning keys to the nodes of a Binary search tree given its shape
Let's say I have a Binary search tree with $n$ nodes and know its shape. I also knows each node has a unique key that is an integer between $1$ and $n$ (inclusive). This would make the assignment of ...
0
votes
1answer
26 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
vote
3answers
74 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
28 views
Difference between Recursion Tree & Binary Tree
What's the difference? is a Recursion tree private case of Binary tree?
2
votes
3answers
245 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
203 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
23 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
18 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
36 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
25 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
324 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 <...
-1
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
42 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
23 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
29 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
39 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
743 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
119 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.
...
0
votes
1answer
33 views
5
votes
1answer
41 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
154 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
152 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
40 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
24 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
48 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
143 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
50 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
4k 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
24 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
39 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
47 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
41 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
43 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-...
