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
8 views

AVLTree - cost of join func in split

given T1 , T2 two AVLTrees , we define the cost of a join operation : |T1.height - T2.height| +1 we insert the keys randomly . 1.analyze the cost of the average join cost when *split func is called ...
sami younis's user avatar
0 votes
0 answers
56 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
169 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
  • 141
0 votes
2 answers
137 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
316 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
55 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
23 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
94 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
20 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
60 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
55 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
35 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
70 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
45 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
176 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
126 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
  • 551
2 votes
1 answer
129 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
51 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
250 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
444 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
780 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
55 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
113 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
43 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
308 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
55 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
  • 3
-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
141 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
111 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
90 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
52 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
119 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
3 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
  • 133
2 votes
3 answers
363 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
651 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
72 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
64 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
85 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
2 votes
3 answers
2k views

Is there a reason Depth-First Search and Breadth-First search commonly called "Search" instead of "Traversal?"

From my understanding, two separate and distinct operations can be performed on binary search trees: Search and Traversal. Search: Given a key, search will run an algorithm to find the node containing ...
user4779's user avatar
  • 371
3 votes
1 answer
147 views

Using pre-,post-, and in-order indexes to find information about a Binary Search Tree

Recently I have been studying ways of traversing a BST (in python), and have collided with the terms pre-order, post-order and in-order. I believe that I understood the three terms pretty well, and ...
Rodrigo's user avatar
  • 189
3 votes
1 answer
829 views

Efficient data structure for insertion, deletion and smallest-not-in-range query on an array of integers

I'm trying to make a data structure $A$ that has the following features: insert($a$) operation : insert given integer $a$ to $A$. It is assured that all integers are unique. delete($b$) operation : ...
user avatar
0 votes
2 answers
1k views

Can a complete binary tree have at least two nodes with just one child?

https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees says A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the ...
Tim's user avatar
  • 4,865
3 votes
1 answer
279 views

finding an algorithm for creating a priority search tree in linear time with presorting

A priority search tree is a binary tree satisfying the following: every node $u$ stores a point $p_u = (x_u,y_u)$ every nonleaf $u$ stores an x-coordinate $x_u'$ called the split-line coordinate. If $...
user3472's user avatar
  • 207
1 vote
1 answer
115 views

When is a max heap tree invariant under a root removal, followed by a re-insertion of the root?

Let $T$ be a max heap tree with no duplicate values amongst the nodes. When does $T$ satisfy the following. Remove the root, and restructure the tree to satisfy the heap property. Reinsert the root, ...
user7828's user avatar
-1 votes
1 answer
63 views

Prove that f(T) = Ω(l log l) for any l-leaf binary tree T

I want to prove this: For any binary tree T, let f(T) denote the sum of the depths of all of the leaves of T. (The root is at depth 0, the children of the root are at depth 1, the grandchildren of the ...
Pri's user avatar
  • 1
0 votes
0 answers
63 views

Upper bound of sum of sub-tree depth difference on a complete binary tree with $n$ leaves

A complete binary tree with $n$ leaves has $n-1$ internal nodes. For every internal node $i$, I care about the difference between the maximum depth of the left sub-tree and the maximum depth of the ...
yupbank's user avatar
  • 215

1
2 3 4 5
12