# Questions tagged [binary-trees]

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

482 questions
Filter by
Sorted by
Tagged with
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 ...
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.
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 ...
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 ...
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$...
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 ...
26 views

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 ...
25 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 ...
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). ...
324 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 <...
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 ...
42 views

### LOUDS Succinct Tree Representation

I am trying to make my Trie tree structure as compact as possible. While searching about this I came across to "Level order Unary Degree Sequence " i.e. LOUDS representations using bit ...
23 views

### Expected runtime for hashing with a binary search tree as collision handling

I thought about implementing a data structure with expected runtime of O(1) for insertion, deletion and look-up and a worst case runtime for these operations of O(log(n)). This is under the assumption ...
28 views

### Is the heap in “Data Structures Algorithms in Java” by Goodrich, Tamassia, and Goldwasser missing sentinel leaves?

In the book, Data Structures Algorithms in Java Sixth Edition by Goodrich, Tamassia, and Goldwasser on page 339, there is an "Example of a heap storing 13 entries with integer keys. The last ...
29 views

### Range sum query - tree representation efficiency

I was reading about possible solutions to the well known problem: Given array A with length N create a structure that enables ...
39 views

### (Searching + Splaying) in a Splay Tree

Given a tree To search for value 1, I do the following splay operations: i) Zag on 7 ii) Zag on 1 And hence obtain 1 in the root. But why would this be incorrect? i) Zag on 1 ii) Zag on 1 The ...
743 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 ...
119 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. ...
33 views

Recursive ...
41 views

4k views

### What are the minimum and maximum numbers of elements in a heap of height h?

I came across the question: What are the minimum and maximum numbers of elements in a heap of height $h$? To which I came up with this theory: $$\sum_{i=0}^{h-1} 2^i = 2^h-1$$ $2^h-1$ is the ...
24 views

### Recurrence Relations for Perfect Quad Trees (same as binary trees but with 4 children instead of 2)

I have to write and solve a recurrence relation for n(d), showing how I arrive at the formula and solve the recurrence relation, showing how I arrive at the solution. Then prove my answer is correct ...
39 views

### Use tree in-order traversal to determine whether a BST or Heap

Given these in-order traversal lists: 1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19 2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17 I need to determine whether each one of those lists represent a valid BST ...
47 views

### Does the heap property in the definition of binary heaps apply recursively?

The definition of binary heaps says that it should be a complete binary tree and it should follow the heap property where according to the heap property, the key ...
41 views

### Product of all nodes except for one in Binary Tree

Assume we are given a binary tree with an integer sitting at each node. I am looking for an efficient way to find for every path from the root to a leaf every possible product with exactly one node ...