Skip to main content

Questions tagged [binary-trees]

a rooted tree in which each node has no more than two children

Filter by
Sorted by
Tagged with
0 votes
0 answers
30 views

Can a binary tree be generated from Union-Find using union-by-rank?

I'm trying to determine if the following claims are true or false: Claim 1 When disjoint Union-Find is implemented using up-trees and union-by-rank, and initially  there was a set of 5 single nodes. ...
Daniel's user avatar
  • 71
-1 votes
1 answer
19 views

What formula was used here to calculate the average search time of the binary tree?

My teacher showed me the following slide on the PowerPoint with two binary search trees and their corresponding "average search times". The PPT did not mention what formula was used to ...
Felix An's user avatar
  • 119
0 votes
0 answers
26 views

Name for relation between trees being isomorphic after collapsing a single subtree

Suppose I have two rooted trees $T_1$ and $T_2$, such that if I select a subtree in $T_1$ and collapse it into single node (i.e. delete all nodes under the root of this subtree), then I end up with $...
ludog's user avatar
  • 90
1 vote
1 answer
39 views

Best online algorithm for a monotone priority queue that has equal amount of deletion and insertions

I got an executor thread that is given jobs to execute at certain timestamp. So this means my problem is online. While there are cases when the new job has a timestamp in the past, we can easily test ...
Giancarlo's user avatar
0 votes
0 answers
24 views

I don't understand the reason behind O(h) time complexity in this MIT OCW Algorithms question

I faced the following question in a problem session: Gal Ore is a scientist who studies climate. As part of her research, she often needs to query the maximum temperature the earth has observed within ...
Arham Zahid's user avatar
2 votes
1 answer
60 views

Possible values of root of AVL tree

I have a question: given that an AVL tree holds numbers 1, 2, 3, ..., 1000, what are the smallest and largest possible values of the root? I have a feeling it is 500 and 501, but I don't know how to ...
HBH's user avatar
  • 21
0 votes
0 answers
13 views

Is this Deterministic Unranked Root-To-Leaf Binary Tree Automata?

I believe I have a definition of deterministic root-to-leaf tree automata in the unranked binary case, and would like to check that I have this definition correct. I would also appreciate any sources ...
TomKern's user avatar
  • 103
-3 votes
3 answers
61 views

Prove that in a complete binary tree with $L$ levels, the total number of nodes $N \leq 2^{(L+1)} - 1$

Anyone please answer the question: Prove that in a complete binary tree with $L$ levels, the total number of nodes $N \leq 2^{(L+1)} - 1$.
Ayush Verma's user avatar
2 votes
2 answers
107 views

Prove that balanced binary search tree has lowest expected cost

Take numbers from 1 to 100. Put all of them in a binary search tree. Now, one of those 100 numbers is picked uniformly at random and given to us. We'd like to find it in the binary search tree. The ...
Rohit Pandey's user avatar
0 votes
0 answers
63 views

Sub-Grouping AVL tree based on nodes amount in O(log(n))

I need to find a way to split an AVL tree based on the amount of nodes in the tree, lets assume you get a number $k$ and if the number of nodes in the tree is multiplication of $k$ you need to find ...
3xhaust's user avatar
4 votes
1 answer
182 views

Improving a ranking system with "best rank"

I've implemented a ranking system (based on a score), using a Map<Player,Score> and an improved BST<Score, Set<Player>>. So now I can compute "rank of a player" in O(log(n))...
Nisalon's user avatar
  • 143
0 votes
2 answers
143 views

Recursive formula for height of BST

Let $H(n)$ be the average height of a BST with nodes from ${1,...,n}$. I think that $$H(n) = \frac{1}{n}\sum_{i = 0}^{n-1}\left[\text{max}(H(i), H(n-1 -i)) + 1\right]$$ But I don't know how to prove ...
user167064's user avatar
2 votes
1 answer
403 views

Prove that the number of comparisons between elements in binary heap build is at most (2n-2)

Question Prove that the number of comparisons between elements in binary heap build is at most $2n-2$. $n$ is the total number of the nodes. Pseudocode ...
Lior's user avatar
  • 143
1 vote
1 answer
71 views

Does a sorted sequence from in-order traversal imply a binary tree is a BST?

An in-order traversal of a binary search tree (BST) produces a sorted sequence. I wonder, if we perform an in-order traversal of a binary tree and obtain a sorted sequence, does that imply that the ...
Mason Rashford's user avatar
0 votes
0 answers
25 views

Create a class or structure like union of ranges

How to create a structure which acts as union of ranges. In that structure new ranges can be inserted beforehand and then some queries are asked to find out if the given point is covered by any of the ...
user166204's user avatar
1 vote
1 answer
107 views

Computing the index of the n^{th} ancestor of a node in a perfect binary tree / heap

I think you can compute the index of the n^{th} ancestor of the node at index i using the formula: $\lfloor i / 2^n \rfloor$ where $n \in \mathbf{Z}^+$. Note that I am assuming that the parent node is ...
Ryan Pierce Williams's user avatar
0 votes
0 answers
21 views

Minimal pairwise comparisons to combine multiple binary trees that are only relatively sorted?

I'm intending on writing a program to let my friends make pairwise comparisons of computer generated images, ranking them. I'm mostly doing this for fun and to do some learning and I picked computer ...
AncientSwordRage's user avatar
2 votes
0 answers
87 views

Data structure for prefix covering

I have a list $[1, 2, \ldots, T]$. I want to create a collection of subsets, such that: each element belongs to a small number of subsets each prefix is a union of small number of subsets (these ...
ocksumoron's user avatar
2 votes
0 answers
65 views

What is the depth distribution of a random binary tree with n nodes?

Assume I generate a random binary tree with a bounded height with $n$ nodes. For a given key we measure the length of its path (the maximum can be $n-1$). So my Question is what is the distribution of ...
Jungle's user avatar
  • 21
0 votes
1 answer
58 views

What is the technical name for one sided tree traversal and which algorithms are good for it?

Looking at the image from Wikipedia page for tree traversal what is the name for a traversal that follows the dashed line exactly with repeating visits to obtain: F, B, A, B, D, C, D, E, D, B, F, G, ...
MathX's user avatar
  • 103
0 votes
0 answers
36 views

Are pre-order, in-order and post-order the only traversals for depth-first search?

With a binary tree, the 3 approaches for the tree below are listed. ...
heretoinfinity's user avatar
1 vote
1 answer
94 views

Understanding the Internal Stack Frames in a Recursive Function Call

I'm trying to understand how the system's call stack works internally when a recursive function is called. Specifically, I'm looking at a function that computes the maximum depth of a binary tree ...
ilovewt's user avatar
  • 113
0 votes
1 answer
49 views

Is this Patricia tree implementation wrong?

I'm reading the chapter Radix Search of the book Algorithms (Robert Sedgwick). I've made a simple implementation and something isn't behaving as expected. In program ...
sleekster's user avatar
0 votes
1 answer
226 views

Prove that the subtree rooted at any node $x$ in a red black tree contains at least $2^{bh(x)} - 1$ internal nodes

To prove this, Introduction to Algorithms by Cormen et al., makes the assumption that the node has two children. For the inductive step, consider a node $x$ that has positive height and is an ...
ihsingh2's user avatar
2 votes
1 answer
167 views

Visualizing How of KD-tree Data Structure Splits Space

I am trying to understand how KD-tree works when we insert a node and how it splits the xy plane, please. Below $[5, 4]$ splits the xy-plane into left and right parts while $[2,6]$ splits it into top ...
Avv's user avatar
  • 505
0 votes
1 answer
31 views

Querying a binary search tree, find maximum

I'm studying algorithms on the very famous book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein. and I'm looking at the algorithms for finding the maximum and minimum ...
emacos's user avatar
  • 121
0 votes
0 answers
25 views

How many times is a node rotated towards the root in a weight-balanced tree?

In this paper they prove that the number of rotations after doing $n$ insertions or deletions to a weight-balanced tree is $O(n)$ (when starting from an empty tree). What isn't clear to me though is ...
MotiNK's user avatar
  • 553
2 votes
1 answer
131 views

Is there a name for this kind of binary tree?

While working on a math problem the following tree structure came up: o \ o / o / \ o o / \ / It is a binary tree with the ...
Anthony Garcia's user avatar
2 votes
0 answers
61 views

How to delete node from RB-tree

I need to implement my own red-black tree and I am stuck with deletion. I have found this book (Introduction to Algorithms) (p.222) and in the following code I can't understand this marked line. ...
Euler-Maskerony's user avatar
1 vote
2 answers
292 views

Why would we want to convert a forest or generic tree to binary tree?

Why sometimes we would want to convert generic trees or forests into a binary tree? And what's the main principle behind this convertion?
Sepehr Golestanian's user avatar
0 votes
3 answers
777 views

Size and height of binary tree, different interpretations?

I can't seem to get my head around the formulas to use for size of binary tree. Depending on who I ask, what website, etc. I see different similar answers. So if someone could explain simply either: ...
Bradley Cable's user avatar
2 votes
1 answer
934 views

Improper binary tree: maximum number of external nodes

The term external node is used as a synonym for a leaf node in the following. A binary tree shall be called proper if each node has either zero or two children. If it is not proper, it shall be called ...
Ruperrrt's user avatar
  • 123
0 votes
1 answer
59 views

BSTs with repeating keys

The problem is to count number of unique binary search trees with keys $a_1,a_2,...,a_n$, given that some of the keys are not unique. For example, $a$ could be 2, 1, 1, 4, 3, 4. We could try an ...
prototycoon2's user avatar
1 vote
1 answer
163 views

Randomly generated binary search trees case comparison

Although not an assignment, just out of curiosity; I am trying to compare a two cases A scenario where I pick a tree out of the set of possible binary search trees on the keys $1,2,\ldots,n$, with ...
Mike's user avatar
  • 33
1 vote
1 answer
45 views

Decision tree to check 2 rectangles

Given two disjoint rectangles $(a,b]\times (c,d]$ and $(e,f]\times (g,h]$ in $\mathbb{R}^2$ how can I check with a decision tree of least depth if a given point $(x,y)$ lies within the union of the ...
treeman8's user avatar
1 vote
2 answers
460 views

Can two different binary trees can have identical post-order sequence

I have found that when drawing two trees having different structures, we can get the same in-order sequence and pre-order sequence. But I haven't found if two different binary trees can have an ...
Eranynomous's user avatar
-1 votes
1 answer
64 views

Inequality about External path length

First of all LPL is Leaf path length & IPL is internal path length. While i was studying algorithm analysis for average complexity of binary search , i saw that inequality. Before that, i proved ...
Mocak's user avatar
  • 15
-1 votes
1 answer
66 views

Complete Binary Tree

R C Lacher's definition: A binary tree is complete iff the only vertices with less than two children are in the bottom two layers. Paul E. Black's definition: A binary tree in which every level (...
ihsingh2's user avatar
1 vote
1 answer
171 views

The relationship between a perfect binary tree and a complete & full binary tree

I am reading the book "Cracking the coding interview". In Chapter 4 they cover basic tree concepts. It says there that a complete binary tree is a binary tree in which every level of the ...
Mikhail Genkin's user avatar
0 votes
0 answers
31 views

What is the gold-standard description of the 2-3 tree (search, insert, delete)?

After several hours of frustration, I finally realized that the definition of two-three trees aren't standard (my lecture notes, this video, this other video, and Wikipedia) are different. My lecture ...
AyamGorengPedes's user avatar
3 votes
1 answer
140 views

Does 'reverse' mean 2 separate things in contexts of tree vs. graph traversal?

I'm somewhat confused about the Wikipedia terms about the meaning of 'reversed' in the context of tree & graph treversals Suppose I have a tree: ...
ledonter's user avatar
  • 145
2 votes
0 answers
105 views

Problem about variation of red-black trees

I got an exercise about a variation of RB trees but I am struggling to see how to solve it, therefore I'll be happy to hear your opinion about it. The exercise is: Let us define a binary search tree ...
Yarin's user avatar
  • 275
2 votes
0 answers
55 views

Efficient Implementation of join and split operations on semisplaying tree

Splaying trees are a heavily researched of theoretical computer science as they are conjectured to be optimal binary trees. They were first presented by Sleator & Tarjan in Self-Adjusting Binary ...
BrockenDuck's user avatar
2 votes
1 answer
126 views

Solution Verification: How does the postorder traversal of a BST change after rotating left?

Given a BST $T$, $x$ is a random node in it and $y$ is the right child of $x$. How does the PostOrder traversal of BST $T$ change after we rotate the tree left on node $x$? In which cases does the ...
Pwaol's user avatar
  • 164
4 votes
2 answers
2k views

Are reversed reverse preorder traversals equivalent to a postorder traversal?

I was viewing the solutions of other Leetcode users for the classic "post-order traversal of a binary tree" question, when to my surprise, I found a ton of users simply finding the reverse ...
dlq's user avatar
  • 143
2 votes
3 answers
422 views

Find the smallest difference between two numbers in a DS in O(1) time

I got an assignment to create a new data structure, with the following rules: Init - O(1). Insert x - O(log$_2$n). Delete x - O(log$_2$n). Search for x- O(log$_2$n). Find max difference between two ...
Bob Alice's user avatar
2 votes
2 answers
662 views

An α-good tree with n nodes has height O(log n)

Let $α \in [0, 1)$ be a constant. For a rooted binary tree $T$ and a node $x$ in $T$, we denote by $|x|$ the number of nodes in the subtree of $T$ rooted at $x$ (if $x$ = $NIL$ then $|x|$ = $0$). We ...
SVMteamsTool's user avatar
1 vote
2 answers
78 views

Why is a recurrence of $2N_{h-2}$ equal to $2^{h/2}$?

I was watching video 7. Binary Trees, Part 2: AVL, where professor Erik Demaine stated that $$2N_{h-2} = 2^{h/2\text{ (or maybe with floor or something... maybe it's ceiling)}}$$ where $N$ stands for ...
Fausto Zamparelli's user avatar
1 vote
0 answers
70 views

Breadth-first search (BFS) for binary tree

It is pretty simple to implement a DFS algorithm for a binary tree but what about BFS for binary trees? I tried to adapt the BFS algorithm for ordered tree, this is the result: I presume that better ...
Bender's user avatar
  • 367
1 vote
1 answer
92 views

prove an inequality on binary tree

Let $\mathcal{T}_n$ be the set of ordered binary trees that have n leaves. $d_T(v)$ means the node $v$'s depth in the tree T. Prove: for any $T\in \mathcal{T}_n$ , for any $\{c_1,c_2,...c_n\}$ , $c_i &...
AsukaMinato's user avatar

1
2 3 4 5
12