Questions tagged [binary-trees]

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

Filter by
Sorted by
Tagged with
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 ...
Jungle's user avatar
  • 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, ...
MathX's user avatar
  • 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. ...
heretoinfinity's user avatar
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 ...
ilovewt's user avatar
  • 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 ...
sleekster's user avatar
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 ...
ihsingh2's user avatar
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 ...
Avv's user avatar
  • 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 ...
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
  • 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 ...
Anthony Garcia's user avatar
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\}]=...
Jordan K's user avatar
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. ...
Euler-Maskerony's user avatar
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?
Sepehr Golestanian's user avatar
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: ...
Bradley Cable's user avatar
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 ...
Ruperrrt's user avatar
  • 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 ...
prototycoon2's user avatar
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 ...
Mike's user avatar
  • 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 ...
treeman8's user avatar
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 ...
Eranynomous's user avatar
-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 ...
Mocak's user avatar
  • 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. ...
user154030's user avatar
-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 (...
ihsingh2's user avatar
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 ...
Mikhail Genkin's user avatar
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 ...
AyamGorengPedes's user avatar
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: ...
ledonter's user avatar
  • 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 ...
Yarin's user avatar
  • 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 ...
BrockenDuck's user avatar
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 ...
Pwaol's user avatar
  • 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 ...
dlq's user avatar
  • 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 ...
Bob Alice's user avatar
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 ...
SVMteamsTool's user avatar
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 ...
Fausto Zamparelli's user avatar
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 ...
Bender's user avatar
  • 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 &...
AsukaMinato's user avatar
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 ...
user4779's user avatar
  • 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 ...
Rodrigo's user avatar
  • 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 : ...
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,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 $...
user3472's user avatar
  • 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, ...
user7828's user avatar
-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 ...
Pri's user avatar
  • 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 ...
yupbank's user avatar
  • 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 ...
yupbank's user avatar
  • 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 ...
splicer's user avatar
  • 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}{...
FreeZe's user avatar
  • 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 ...
Spyromancer's user avatar
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? ...
Mihir Sanjay's user avatar
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 ...
northerner's user avatar
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}$ ...
Mario Carneiro's user avatar
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: ...
Vladyslav Shlianin's user avatar

1
2 3 4 5
11