Questions tagged [binary-trees]
a rooted tree in which each node has no more than two children
544
questions
2
votes
0
answers
48
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 ...
- 21
0
votes
1
answer
51
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, ...
- 103
0
votes
0
answers
29
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.
...
- 659
1
vote
1
answer
46
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 ...
- 113
0
votes
1
answer
44
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 ...
0
votes
1
answer
133
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 ...
- 25
2
votes
1
answer
49
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 ...
- 493
0
votes
1
answer
26
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 ...
- 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 ...
- 531
2
votes
1
answer
123
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 ...
- 123
0
votes
0
answers
22
views
Manipulating a binary tree representation
I am designing a discrete probability distribution with a string of binary values as an input $\{s_i\}\in\{S_i\}$, and binary outputs $e\in E$ with Bernoulli probability $P(E=1|\{S_i\})=XOR[\{S_i\}]=...
- 1
2
votes
0
answers
38
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.
...
1
vote
2
answers
130
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?
0
votes
3
answers
123
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: ...
2
votes
1
answer
370
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 ...
- 123
0
votes
1
answer
49
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 ...
1
vote
1
answer
85
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 ...
- 33
1
vote
1
answer
42
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 ...
- 11
1
vote
2
answers
192
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 ...
- 11
-1
votes
1
answer
39
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 ...
- 3
0
votes
0
answers
208
views
Proof: Leaf Nodes of a Binary Heap Start at ⌊n/2⌋+1
I have constructed a proof to show that the leaf nodes of a binary heap (which is just a partially complete binary tree) start at ⌊n/2⌋+1. Please let me know if it holds merit. I am shaky on proofs.
...
-1
votes
1
answer
62
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 (...
- 25
1
vote
1
answer
105
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 ...
- 113
0
votes
0
answers
29
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 ...
- 109
3
votes
1
answer
102
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:
...
- 145
2
votes
0
answers
58
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 ...
- 229
2
votes
0
answers
42
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 ...
- 121
2
votes
1
answer
99
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 ...
- 164
3
votes
2
answers
1k
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 ...
- 133
2
votes
3
answers
297
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 ...
- 23
2
votes
2
answers
634
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
...
- 413
1
vote
2
answers
71
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 ...
1
vote
0
answers
52
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 ...
- 357
1
vote
1
answer
73
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 &...
- 193
2
votes
3
answers
1k
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 ...
- 371
3
votes
1
answer
131
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 ...
- 189
3
votes
1
answer
767
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 : ...
user149684
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 ...
- 4,825
3
votes
1
answer
209
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 $...
- 207
1
vote
1
answer
104
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, ...
- 11
-1
votes
1
answer
61
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 ...
- 1
0
votes
0
answers
52
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 ...
- 215
0
votes
1
answer
323
views
Bound the sum of leaf depth on a complete binary tree of $n$ leaves
A complete binary tree is defined as a tree where each node has either 2 or 0 children.
For a complete binary tree with $n$ leaves, there can be different arrangements of nodes, let's define the ...
- 215
2
votes
0
answers
36
views
upper bound on the smallest modulus for perfect hashing of a Huffman tree
Given a full binary tree with 256 leaves and depth <= 64,
let H be the set of Huffman codes described by the tree (using 0 to go left, and 1 to go right, where ...
- 121
0
votes
1
answer
178
views
Number of nodes of a binary tree at height $i$
It is well known that at height $i$ the number of nodes is bounded by $ \frac{n}{2^{i+1}} $, for example there are at most $n/2$ leafs.
Now, it makes sense only if we're taking $ \left\lceil \frac{n}{...
- 101
0
votes
1
answer
145
views
Solving a recurrence relation with two variables
I have this function which traverses each node of a left child-right sibling binary tree once and I want to solve the recurrence relation of the function.
First of all I think the relation looks like ...
- 115
0
votes
0
answers
1k
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
2
answers
181
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 ...
- 153
0
votes
1
answer
16
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}$ ...
- 531
1
vote
0
answers
46
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:
...
