# 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
0answers
705 views

### Tight upper bound on height of a red-black tree

"Introduction to Algorithms" by Cormen et al., 3rd edition, Lemma 13.1 states that A red-black tree with $n$ internal nodes has height at most $2\log(n+1)$, i.e. $h \le 2\log(n+1)$. Can equality ...
1answer
1k views

### Is a BST considered a data structure or abstract data type

and why? It seem abstract in that it is and idea created and implemented with nodes arranged a certain way. But it did not show up in the text here: https://en.wikipedia.org/wiki/...
2answers
342 views

### Find height of deepest FULL level in binary tree

Suppose I have a binary tree that is guaranteed to have at least one level that holds the maximum amount of nodes possible. I want to find the height of the deepest level that is full/holds the ...
1answer
135 views

### Prove key of leaf is larger or smaller than key of parent if leaf is largest key in smaller tree or smallest in larger tree with respect to parent

Show that for any leaf v in a binary search tree, if u is the parent of v, then either key[v] is the largest key in the tree smaller than key[u], or key[v] is the smallest key in the tree larger than ...
2answers
274 views

### Find if a sequence of node is a result of a binary tree preorder traversal

Assume we have a sequence of 0's and 1's: $n_0, n_1, ..., n_N$, in which 0 stands for a leaf node, and 1 stands for an uncertain node (it may or may not be a leaf node). How to check if this sequence ...
1answer
713 views

### What is the main difference between binary decision tree and binary decision diagram(BDD)?

What is the main difference between binary decision tree and binary decision diagram(BDD)? From what I can tell I only understand that a binary decision diagram is a more compact representation ...
0answers
35 views

### Read nodes of a BST in blocks of size $k$ and traverse it in $\mathcal{O}(log_kn)$

This describes how one can neatly store a binary search tree as an array. I'm looking for a way to store a BST that will allow me to traverse any root to leaf path by loading $\mathcal{O}(log_kn)$ ...
0answers
103 views

### Update and find-smallest-absolute-value operations on a tree

I have a balanced binary tree that stores a number in each node, initially zero. I want to build a data structure that will support the following two operations: Given a vertex $v$ in the tree and a ...
4answers
6k views

### How are binary trees represented on disk

Assume I have a word document, the contents in it are stored on the disk as bits. Nothing so complex here. When the word processor reads those bits, it just knows how to display on screen. But what ...
2answers
2k views

### What are drawbacks of Tree Sort algorithm (with balanced tree) vs Tree Sort (with unbalanced tree)?

Tree Sort algorithm with unbalanced tree may yield $O(n^2)$ worst-case time complexity/performance. But Tree Sort algorithm with balanced tree guarantees $O(n\log n)$ worst-case time performance. So ...
2answers
481 views

### Heights series in the DFS traversal of a binary tree

Assume a binary tree of height N. All nodes have exactly 2 children and all leaves have height N. For example, the following tree has N=3: ...
1answer
179 views

### The height of 5-balnced tree is O(logn)

Binary tree with external leaves is a 5-balanced tree if the path from the root to the farthest external leaf is no more than 5 times as long as the path from the root to the nearest external leaf, ...
2answers
3k views

### Algorithm to create tournament brackets

I'm designing a web app to host e-sports tournaments and want to create an algorithm that generates tournament brackets. Given a list of participants' user ID's (minimum 4, maximum let's say 64), I ...
1answer
107 views

### Is there a name for this traversal-optimized representation of a binary tree data structure?

I have used a purely functional binary tree structure in which there is a single node that is "marked". It allows for $O(1)$ access and modification of the marked node's value, as well as $O(1)$ ...
0answers
1k views

### Day-Stout-Warren algorithm for balancing BST. How does vine to tree work?

I was trying to understand the dsw algorithm for balancing a binary search tree in-place using this virgina tech page. The wikipedia page and vt page are more or less similar. I am having a hard time ...
1answer
693 views

### Check if a binary tree is a perfect tree

I'm trying to write an algorithm to check if a given binary tree is a perfect binary tree, and of course with the lowest complexity. I was thinking to calculate the height of the tree $h$ and the ...
2answers
407 views

### Balanced Binary Search Tree Two-Sum with Constraints

My question spawns from this question. The question is straightforward: Can we find whether there exist 2 values in a balanced binary search tree where their sum equals a given target value? Now ...
2answers
4k views

### How exactly Hashing performs better than a Binary Search?

The time complexity of a Binary Search is O(log n) and Hashing is O(1) - so I've read. I have also read that Hashing outperforms Binary search when input is large, for example in millions. But I see ...
0answers
141 views

### Finding post-order traversal of a binary tree from its in-order and pre-order traversals lower bound

I know that we can construct a BST by just having its pre-order traversal in $O(n)$ time (this link). But what if the tree is just a binary tree and we have its in-order and pre-order traversals? I ...
1answer
62 views

### Prove $T$ is a BST iff for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$

Let $T$ be a complete binary tree. Prove that $T$ is a binary search tree if and only if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child ...
0answers
115 views

### What would be the probabilty of a randomly generated tree to be a Red-Black Tree

The question is not related to the homework I was working on a homework, and the specification was to generate a random tree with n elements(n being in the thousands for the assignment) and asked me ...
1answer
32 views

### Info about dataset from which a Huffman tree was generated

I know that given the following huffman tree: you can say that C occurs most in the dataset from which it was generated and D and B occur the least. Can you also say that the left most leaf on a ...
0answers
251 views

### WAVL Trees - Number of rebalances

I was experimenting with a WAVL Tree code I wrote. One thing I noticed is that on average, there was much less rebalancing actions after delete than after insert. In fact, average rebalances after ...
1answer
397 views

### Number of Inner nodes in a B-Tree

the question goes as follows: In a B-tree (d,2d) of height h, what is the minimal and maximal number of inner-nodes (excluding leaves)? My idea: Minimal: The root is 1, it has a minimum of 2 ...
0answers
33 views

### Binary Search Tree: If two different traversals are given, will there be a unique tree that satisfies the traversals? [duplicate]

I have come across algorithms that can create a BST if any two of the 3 traversals are given (there would be three different algorithms for the 3 combinations) This is an example I was wondering, is ...
2answers
2k views

### Have I invented a new data structure?

EDIT: Seems like what this structure is nothing more than a 26-bit bitwise trie, as KWillets suggested in the comments! You can think of the words we insert the trie as 26-bit Bitsets where the i-th ...
1answer
555 views

### Forming red-black tree from binary tree conserving in-order traversal

What is the optimal algorithm (in terms of time complexity) that can transform any binary tree to a red-black tree, with the requirement that in-order traversal must yield the same values for the new ...
1answer
546 views

### Link-cut trees: using access() and link()

I am having some trouble on understanding link-cut trees, so I need some help. Suppose that we have nodes $A, B, C, D$ and we want to do the following operations: Link(A,B) Link(B,C) Link(C,D) ...
1answer
1k views

### The number of nodes in a binary tree

If a binary tree is both a max-heap and an AVL tree, what is its largest possible number of nodes, assuming all keys are different?
1answer
78 views

### Build a tree for $(-\infty,+\infty)$ similar to dyadic interval trees for $\left[0,+\infty\right)$

Using dyadic intervals, I can build a binary tree for $\left[0,+\infty\right)$ by having a node the $i$-th at level $l$ representing the range $\left[i\cdot2^l,(i+1)\cdot2^l\right)$ and has the $(i)$- ...
2answers
1k views

### Is binary tree just a two-dimension-doubly-linked-list?

We all know the structure of a binary tree: struct binary_tree { binary_tree *parent; int data; binary_tree *left; binary_tree *right; }; So a ...
1answer
85 views

### Binary Tree Question

Using the diagram of a binary tree and algorithm answer the following: If the following commands store(1,laurence), store(1, ron), store(1,graham), store(1,abe) and store(1,martin) are executed what ...
4answers
25k views

### What is “rank” in a binary search tree and how can it be useful?

I am having a bit of trouble wrapping my mind around what a ranked binary search tree is and why having a rank is important. I am hoping that someone can clarify a few things for me. What I have ...
0answers
36 views

### Number of possible balanced binary trees [duplicate]

A tree is balanced if the subtrees of each node differ in height by at most one. How many balanced binary trees can we create from $n$ nodes?
1answer
146 views

### Where I can find example how prove red black tree?

I need prove that any red-black tree with at least two elements obtained through the insertion algorithm has at least one red node. For this, I need use Induction. I don't understand how apply ...
1answer
130 views

### A closed form expression for # of inputs of a binary tree and its number of nodes

Is there any closed from expression that can express the number of input pins of a binary tree based on height of the tree and its number of nodes? In case that the binary tree is a full tree, it is ...
1answer
625 views

### Strict-Binary Tree - Same Post-order & Pre-order sequences?

I'm going through some past exam papers for my course and I'm having trouble completing this one question. It is as follows: "Draw a strict binary tree with seven nodes that has the same pre-order ...
1answer
964 views

### Determine if the sequence of numbers is a post order traversal of a binary tree

The question is: given a sequence of numbers, find an algorithm that determines if the sequence of numbers is in post order traversal of a binary search trees. Up to now, I have understood the ...
1answer
441 views

### Total depth of external nodes in complete binary tree

Assume a proper and complete binary tree $T$ with $n>1$ nodes. Let $E(T)$ represent the sum of the depths of all external nodes in $T$, and $I(T)$ represent the sum of the depths of all internal ...
0answers
297 views

### What is the intuition behind balancing in AVL trees?

I am not sure that my question is clear from the first sight. But I will try to explain what I mean. For now, I am learning balancing the trees on the example of AVL trees. We know that to balance ...
1answer
411 views

### Speculating big O for a binary tree

I have a binary tree with $n$ nodes. The tree is not necessarily balanced. For each node of the tree, I count down the total number of the nodes for its left sub-tree as $n_L$ and then I count down ...
0answers
102 views

### How to cut a full binary tree evenly

Given a full binary tree of size $n$, I need to cut the tree into two by choosing an edge and removing it. I want the cutting to be as equal as possible (i.e. the two subtrees have as equal weight as ...
1answer
261 views

### The Height of subtree in Heap

In order to find the recurrence function of The Height in Heap, the following figure is drawn. Question 1: How can we compute the height if Right subtree in form of Log in base 3, and why do we have ...
0answers
19 views

### How to avoid empty spots when inserting in a B+tree

When you insert a new item in a B+tree leaf node, and the node is full, two new nodes are created and they're both filled halfway and the values get re-distributed accordingly. Before the insertion: ...
1answer
85 views

### Number of n-node binary trees containing an m-node binary subtree

In a paper I see the following lemma about unlabeled binary trees: If $s_1$ and $s_2$ are both m-node binary trees, then the number of n-node binary trees containing $s_1$ as a subtree is the same ...
1answer
374 views

### Number of nodes of height $h$ in a heap or almost complete binary tree

I came up with the following statement: If there are $X$ nodes of height $h$ in an almost complete binary tree, there can be at most 1 node of height $h$ that is not full. That is to say, $X-1$ ...
0answers
607 views

### Using rotate to balance a red-black tree?

You have a Black-Red Tree of height h that has two childs: Left child is a full binary tree of height h-1 Right child ...
2answers
64 views

### Find initial ranks

Assume there is an array $A$ of $n$ elements. $A$ contains every number from $1$ to $n$. We are given an array $B$ of $n$ elements. If we move each element $A[i]$ left by $B[i]$ places starting from \$...
1answer
887 views

### For AVL trees, how do we know if a RL or a LR rotation is needed?

Suppose I am trying to construct a simple AVL tree: Upon inserting 'B' the tree becomes imbalanced. How do I exactly know that I need a LR or RL rotation without making any guesses? From what I ...
0answers
606 views

### How to build a heap better than Incremental and In-place method using decision tree?

For an array A = [a1, a2, a3, a4] of distinct numbers, I have built heap using binary decision tree by Incremental and In-place method. Incremental method: In-place method: Is there a way to build ...