Questions tagged [binary-trees]
a rooted tree in which each node has no more than two children
482
questions
0
votes
2answers
180 views
How to convert a Complete Binary Tree to a Priority Search Tree in O(n)
There doesn't seem to be any resources on this.
I would like to know if there is a linear-time algorithm to convert a Complete Binary Tree with data left-to-right increasing stored in external nodes, ...
110
votes
5answers
133k views
What's the difference between a binary search tree and a binary heap?
These two seem very similar and have almost an identical structure. What's the difference? What are the time complexities for different operations of each?
6
votes
2answers
274 views
Find if a sequence of node is a result of a binary tree preorder traversal
Assume we have a sequence of 0's and 1's: $n_0, n_1, ..., n_N$, in which 0 stands for a leaf node, and 1 stands for an uncertain node (it may or may not be a leaf node). How to check if this sequence ...
0
votes
1answer
78 views
Build a tree for $(-\infty,+\infty)$ similar to dyadic interval trees for $\left[0,+\infty\right)$
Using dyadic intervals, I can build a binary tree for $\left[0,+\infty\right)$ by having a node the $i$-th at level $l$ representing the range
$\left[i\cdot2^l,(i+1)\cdot2^l\right)$ and has the $(i)$- ...
8
votes
1answer
33k 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 ...
0
votes
1answer
114 views
Binary Tree Node Insertion
I was trying to implement a Binary Search Tree using this article as a reference: Binary Search Tree in JavaScript.
I was thinking especially about the node insertion method. Here's my ...
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, $...
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 ...
4
votes
5answers
897 views
Building a tree with the heap property from an array and preserving its order
How efficiently can I build a binary tree satisfying the heap property from an array and such that the inorder traversal of the tree is the original array?
For example, if I have:
2 1 5 6 2 3
I ...
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
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-...
0
votes
1answer
367 views
Leaf nodes of B+ Tree
I have a b+ tree and i want to find the record associated with a specific key Ki.
So i run the b+ tree search algorithm. If a certain node in the search path is a leaf and K=Ki, then the record exists ...
0
votes
1answer
492 views
Determine minimum and maximum number of leaves on a complete tree
I want to determine the minimum and maximum number of leaves of a complete tree(not necessarily a binary tree) of height $h$.
I already know how to find minimum($h+1$) and maximum($2^{h+1}-1$) number ...
3
votes
1answer
8k views
Is a balanced binary tree a complete binary tree?
Considering that the opposite is true it's not mentioned anything about this. I am assuming its not, but I need a very good distinction between these two types of binary trees.
All I know is this:
...
1
vote
1answer
40 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 ...
1
vote
1answer
713 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 ...
2
votes
1answer
261 views
The Height of subtree in Heap
In order to find the recurrence function of The Height in Heap, the following figure is drawn.
Question 1: How can we compute the height if Right subtree in form of Log in base 3, and why do we have ...
0
votes
1answer
118 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
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 ...
1
vote
1answer
423 views
Understanding B tree key deletion step from CLRS algorithm
CLRS explains B tree key deletion as follows:
If the key $k$ is in node $x$ and $x$ is a leaf, delete the key $k$ from $x$.
If the key $k$ is in node $x$ and $x$ is an internal node, do the ...
4
votes
3answers
615 views
Randomly built binary search trees
In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove:
The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$.
We define "...
1
vote
1answer
1k views
Red Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root
I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest et al), and have been studying the deletion algorithm for red black trees. However, I am confounded at the ...
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:
...
0
votes
1answer
34 views
Finding the number of children of the predecessor node of a given node in a Binary Search Tree(BST)
I have some propositions regarding BSTs , please can someone confirm whether they are true or false:
Question :
1.Suppose we have a node $n_1$ with a value $val_1$ i.e $n_1(val_1)$
2.We wish ...
-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 ...
3
votes
2answers
1k views
General method behind converting recursive inorder, preorder and postorder traversals of a binary tree to a non-recursive one?
I am reading both recursive and non-recursive using stack methods to implement inorder, preorder and postorder traversal of a binary tree at https://en.wikipedia.org/wiki/Tree_traversal#Depth-...
2
votes
1answer
220 views
Splay trees: why are depths of nodes on the access path halved?
The original paper describing splay trees Self-Adjusting Binary Search Trees by Sleator and Tarjan claims that:
Splaying not only moves x to the root, but roughly halves the depth of every node ...
35
votes
2answers
23k views
Hash tables versus binary trees
When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL ...
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 ...
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
3answers
879 views
Depth first or breadth first ordering in binary search trees?
Let's say that I make a binary search tree and store it in an array so that I end up with an array that is more cache friendly to binary search compared to a sorted array.
The binary tree is full on ...
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 ...
2
votes
1answer
675 views
How to efficiently create balanced KD-Trees from a static set of points
From Wikipedia, KD-Trees:
Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
2
votes
1answer
28 views
Difference between Recursion Tree & Binary Tree
What's the difference? is a Recursion tree private case of Binary tree?
4
votes
1answer
642 views
Optimal Binary Search Trees Knuth
Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289
Please have a look at this paper, specifically page 18 in which he tries to prove his ...
1
vote
1answer
197 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
22 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.
...
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 ...
1
vote
2answers
67 views
check if a binary tree is a binary search tree
I have some doubts about this algorithm which checks if a binary tree is a binary search tree:
...
0
votes
0answers
24 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
320 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 <...
