Questions tagged [binary-trees]
a rooted tree in which each node has no more than two children
499
questions
0
votes
1answer
13 views
Are AVL&RB Trees without additional storage for balance information in each node feasible?
One advantage claimed for scapegoat trees over other balanced trees like AVL or red-black(RB trees - just mentioning AVL henceforth) is not needing to store additional balance information.
But can't ...
1
vote
1answer
20 views
Do Adjacency Lists from Binary Trees go both ways?
From my reading and research it appears it's one way, however my lecturer states that it goes both ways in his examples.
Let me show you what i mean by this.
He claims that a binary tree built from a ...
0
votes
0answers
24 views
Find balanced edge of a binary tree
What algorithm can be used to find a balanced edge in a binary tree? If we remove that particular edge, the tree is split up nearly equally.
Each tree will have at most $ \ceil{(2n-1)/3}$
0
votes
1answer
25 views
Algorithm to find the saddle point in a Binary tree
How to find a saddle point in a binary tree. where saddle point is a node in a tree whose value = min(the node and all its ancestors) = max ( the node and all its descendants)
1
vote
1answer
26 views
Splitting a binary tree into two halves
I am looking to prove the following:
Each binary tree with $n \ge 2$ nodes has an edge whose removal results in two trees, each having at most $\lceil (2n-1)/3 \rceil$ nodes.
I am not sure how to ...
1
vote
1answer
65 views
How to join two Scapegoat Trees in O(log n) time?
I am working on some binary-search-tree research and was surprised to find no mention of an algorithm to join two Scapegoat Trees. This is where two trees $L$ and $R$ are joined to create a single ...
2
votes
1answer
53 views
Why recording non-existent children in the pre-order traversal will differentiate different binary trees?
I have tried to solve and understand LeetCode question "297. Serialize and Deserialize Binary Tree", and after I read their solution I came up with a question that I will be glad If you can ...
0
votes
2answers
57 views
Binary Tree as 2D array with variable length raws
Usually we use the tree data structure when we care about time complexity for ins/del/...
-In this special case problem, space saving is mandatory too that is 2 pointers for each node is unaffordable; ...
1
vote
1answer
38 views
Applications of Complete Binary Tree?
Wondering what are the real word applications of the Complete binary trees or Almost complete binary trees where the the last level of the tree may not be complete and all nodes in the last level are ...
3
votes
1answer
47 views
Observations about the structure of an optimal Binary Search Tree
My question is about part 15.5 in CLRS (third edition)*, on optimal binary search trees.
I am confused about the following sentences:
Consider any subtree of a binary search tree. It must contain ...
0
votes
2answers
78 views
Kth largest element of a Min Heap of size K is always root element
Why the Kth largest element of a Min Heap of size K is always root element of the Min Heap ? How to prove this ?
1
vote
0answers
141 views
Minimum required ancestor-descendant relationship of n nodes to build a binary tree out of
I have an algorithmic question. Suppose there is a ground truth binary tree of N nodes and there is an oracle which answers queries of the form: given any user specified pair of nodes a and b, do a ...
0
votes
2answers
72 views
Is DFS better than BFS for space complexity when finding path from root to a node in a tree?
For simplicity, and I think without loss of generality, we can consider a binary tree. Suppose that we want to find the path between the root node and some node in the tree (we don't know where it is ...
1
vote
1answer
52 views
More efficient way to parse array into binary search tree
Let's assume I have array which I need to parse into binary tree
...
0
votes
1answer
42 views
When can a (max) heap be a BST?
Cheers, let's suppose we have a MAX heap which does not allow duplicate elements. Is it possible for this heap to be a BST ? Choose the right answer(s) below:
A heap can never be a BST
A heap is ...
0
votes
1answer
23 views
Find two nodes in a BST such that the root's key is the average of their keys without extra space in $\theta(n)$ worst case time
We can do this in $\theta(n^2)$ time if we calculate the average of all couples of nodes in the tree and compare it to the root, but this is too much time.
We can do this in linear time but with extra ...
1
vote
1answer
26 views
Is this a good way to arrange data in a tree?
I was recently learning about Binary Search Trees(BSTs) and thought it could be made even more efficient by making some changes.
As binary search trees have numbers greater than the root node on the ...
0
votes
1answer
36 views
Checking two properties of a tree
I have the following definition:
A green-blue tree is a binary tree that follows the following properties:
Each green node has only blue descendants.
Every path that goes from a node to a leaf has ...
0
votes
1answer
25 views
Converting Binary Search Tree into Decreasing Ordered Linked List
Given a BST with n nodes, the algorithm should create a linked list that contains a decreasing order sorted array. The algorithm should have a worst case time complexity O(n). The signature of the ...
1
vote
1answer
50 views
If a key in a red-black tree has exactly one child (which isn't null) then it is always red
I have the following claim:
Prove or disprove: If a key in a red-black tree has exactly one child (which isn't null) then it is always red.
My attempt:
Disproof.
We will exhibit a counterexample:
...
0
votes
1answer
62 views
Translating the in-order index of a node in a complete, balanced binary tree into the level-order index
Consider the topmost part of a complete, balanced binary tree of all 64-bit numbers, exemplified here.
As highlighted by the lack of a 7*2^64/8 term it is not ...
0
votes
0answers
19 views
Time analysis of $m$ search operation in a Splay tree of nodes who have subtrees of size at least $\frac{n}{\log n}$
I know that the Worst-case for $m$ search operations in a Splay-tree is $O(m\log n +n \log n)$
The thing I'm not sure of is how this runtime depends on the size of the subtrees of the searched nodes.
...
-1
votes
1answer
41 views
Are there any trees where Preorder$(T_1) =$ Preorder$(T_2)$ and Inorder $(T_1) = $Inorder $(T_2)$, but $T_1 \neq T_2$?
Is it possible for two binary trees $T_1 \neq T_2$ that both Preorder and Inorder traversal are equal ?
1
vote
1answer
64 views
How to prove the correctness of the binary tree inversion algorithm?
Define the inversion of a binary tree as the tree whose left sub-tree is a mirror reflection of the original tree's right sub-tree around the center and right sub-tree a mirror reflection of the ...
0
votes
0answers
13 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
40 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
36 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
102 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
28 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
59 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
30 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
100 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
25 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
34 views
Difference between Recursion Tree & Binary Tree
What's the difference? is a Recursion tree private case of Binary tree?
3
votes
3answers
352 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
308 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
23 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
19 views
Proof the number of expected node in a binary using mathematical induction
The following algorithm constructs a binary tree.
...
1
vote
1answer
53 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
24 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
29 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
24 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
563 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
44 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
25 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
33 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
34 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
...
