# 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
180 views

### How to convert a Complete Binary Tree to a Priority Search Tree in O(n)

There doesn't seem to be any resources on this. I would like to know if there is a linear-time algorithm to convert a Complete Binary Tree with data left-to-right increasing stored in external nodes, ...
133k views

### What's the difference between a binary search tree and a binary heap?

These two seem very similar and have almost an identical structure. What's the difference? What are the time complexities for different operations of each?
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 ...
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)$- ...
33k views

### Size of decision tree and depth of decision tree

I'm doing some classification experiments with decision trees ( specifically rpart package in R). By setting the depth of a decision tree to 10 I expect to get a small tree but it is in fact quite ...
114 views

### Binary Tree Node Insertion

I was trying to implement a Binary Search Tree using this article as a reference: Binary Search Tree in JavaScript. I was thinking especially about the node insertion method. Here's my ...
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 ...
67 views

### check if a binary tree is a binary search tree

I have some doubts about this algorithm which checks if a binary tree is a binary search tree: ...
24 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 ...
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). ...