Questions tagged [binary-trees]
a rooted tree in which each node has no more than two children
502
questions
0
votes
0answers
5 views
find a general case for DFS with O(1) space complexity
I found an interesting O(1) space complexity solution for DFS in a full binary tree where path information is not required. I need your help to find the general ...
0
votes
0answers
27 views
Is there a difference between Heapify and Bottom-Up/Top-Down heap construction, when using array representation of binary tree?
Won't both the methods ultimately give a max/min heap? So if I am given a binary tree, as an array, and am asked to convert it to a max heap, can I just use the bottom up construction of the heap?
...
2
votes
2answers
59 views
If both could be implemented with the other, what are the differences between priority queues and binary heaps?
I've red that a binary heap can be implemented using a priority queue. I've also red the opposite, that a priority queue can be implemented using a binary heap.
This seems strange to me as ...
0
votes
1answer
12 views
Online binary tree creation via $a\to ax$ and $ab\to a(bx)$
I wish to construct a sequence of unlabeled binary trees $T_n$ satisfying the following properties:
$T_n$ has $n$ leaves
$T_n$ is well balanced (height $\lg n+O(1)$)
$T_n$ is obtained from $T_{n-1}$ ...
1
vote
0answers
26 views
Parse algebraic expression into a list of operations
Given algebraic expression in a string, I want to split it into a list of operations for building a parallel binary tree. For example, I'm trying to convert expression such as:
...
0
votes
0answers
55 views
Write functions that run in O(1) time
This Question can be found in the book: ODS: An Introduction (Chapter 6)
Suppose we are given a binary tree with pre-, post-, and in-order numbers assigned to the nodes. Show how these numbers can be ...
0
votes
1answer
21 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
32 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
27 views
Find balanced edge of a binary tree [duplicate]
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 $\lceil{(2n-1)/3}\rceil$ nodes.
0
votes
1answer
27 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
30 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
65 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
58 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
49 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
80 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
143 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
110 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
57 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
56 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
29 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
27 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
52 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
66 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
42 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
37 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
122 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
29 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
69 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
34 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
109 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
27 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
35 views
Difference between Recursion Tree & Binary Tree
What's the difference? is a Recursion tree private case of Binary tree?
3
votes
3answers
373 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
355 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
55 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
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
30 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
603 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 ...
