Questions tagged [binary-trees]

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

Filter by
Sorted by
Tagged with
0
votes
2answers
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, ...
110
votes
5answers
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?
6
votes
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 ...
0
votes
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)$- ...
8
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
26 views

Can you add up all the nodes of a special binary tree in polynomial time, in respect to the number of levels?

Let's say you have a binary tree defined by a group $S=\{a:[5,6],b:[7,67],c:[45,12],...\}$ (this group is just an example). The binary tree is constructed so that there are two starting parent nodes, $...
0
votes
0answers
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 ...
4
votes
5answers
897 views

Building a tree with the heap property from an array and preserving its order

How efficiently can I build a binary tree satisfying the heap property from an array and such that the inorder traversal of the tree is the original array? For example, if I have: 2 1 5 6 2 3 I ...
0
votes
1answer
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.
1
vote
0answers
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 ...
3
votes
0answers
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 ...
0
votes
0answers
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$...
0
votes
2answers
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 ...
0
votes
1answer
43 views

How many different (full/complete) in-order binary-trees do exist?

Given be a binary tree whose elements printed in-order results in [1,2,3,4]. Q1: How many different binary-trees do exist? Q2: How many different complete binary-...
0
votes
1answer
367 views

Leaf nodes of B+ Tree

I have a b+ tree and i want to find the record associated with a specific key Ki. So i run the b+ tree search algorithm. If a certain node in the search path is a leaf and K=Ki, then the record exists ...
0
votes
1answer
492 views

Determine minimum and maximum number of leaves on a complete tree

I want to determine the minimum and maximum number of leaves of a complete tree(not necessarily a binary tree) of height $h$. I already know how to find minimum($h+1$) and maximum($2^{h+1}-1$) number ...
3
votes
1answer
8k views

Is a balanced binary tree a complete binary tree?

Considering that the opposite is true it's not mentioned anything about this. I am assuming its not, but I need a very good distinction between these two types of binary trees. All I know is this: ...
1
vote
1answer
40 views

Is there an Interval Tree which supports O(1) dynamic space requirements for queries?

I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key). In general ...
1
vote
1answer
713 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 ...
2
votes
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 ...
0
votes
1answer
118 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. ...
1
vote
3answers
74 views

How balanced is a binary tree in the average case?

For algorithms involving binary trees, time or space complexity is often O(logn) in the best case of a completely balanced tree, and O(n) in the worst case of a completely unbalanced tree. Sure, it's ...
1
vote
1answer
423 views

Understanding B tree key deletion step from CLRS algorithm

CLRS explains B tree key deletion as follows: If the key $k$ is in node $x$ and $x$ is a leaf, delete the key $k$ from $x$. If the key $k$ is in node $x$ and $x$ is an internal node, do the ...
4
votes
3answers
615 views

Randomly built binary search trees

In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove: The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$. We define "...
1
vote
1answer
1k views

Red Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root

I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest et al), and have been studying the deletion algorithm for red black trees. However, I am confounded at the ...
0
votes
1answer
24 views

Reassigning BT root and its children

Given the root of a binary tree, for instance below, I am running the following tests in Python: 1 / \ 2 5 / \ 3 4 Test 1: ...
0
votes
1answer
34 views

Finding the number of children of the predecessor node of a given node in a Binary Search Tree(BST)

I have some propositions regarding BSTs , please can someone confirm whether they are true or false: Question : 1.Suppose we have a node $n_1$ with a value $val_1$ i.e $n_1(val_1)$ 2.We wish ...
-1
votes
1answer
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 ...
3
votes
2answers
1k views

General method behind converting recursive inorder, preorder and postorder traversals of a binary tree to a non-recursive one?

I am reading both recursive and non-recursive using stack methods to implement inorder, preorder and postorder traversal of a binary tree at https://en.wikipedia.org/wiki/Tree_traversal#Depth-...
2
votes
1answer
220 views

Splay trees: why are depths of nodes on the access path halved?

The original paper describing splay trees Self-Adjusting Binary Search Trees by Sleator and Tarjan claims that: Splaying not only moves x to the root, but roughly halves the depth of every node ...
35
votes
2answers
23k views

Hash tables versus binary trees

When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL ...
2
votes
3answers
245 views

For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes

in my notes I have one fact: in a binary tree with $n$ elements ($n$ divisible by three) there is a node $u$ such that the number of nodes in the subtree with root $u$ is at least $\frac{n}{3}$ and at ...
6
votes
0answers
154 views

Impossibility of certain type of tree traversal algorithm

I was wondering for some time how to approach a situation like the following one. Imagine a standard binary tree data structure with $n$ nodes in it. Each node contains pointers to its left and right ...
5
votes
3answers
879 views

Depth first or breadth first ordering in binary search trees?

Let's say that I make a binary search tree and store it in an array so that I end up with an array that is more cache friendly to binary search compared to a sorted array. The binary tree is full on ...
1
vote
1answer
40 views

Height of AVL tree with balance condition of 2

The maximum height of an AVL tree with a balance condition of 1 is 1.44log(n). So the worst case height is O(logn). However, if the balance condition was hypothetically 2 (meaning that the allowed ...
2
votes
1answer
675 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
2
votes
1answer
28 views

Difference between Recursion Tree & Binary Tree

What's the difference? is a Recursion tree private case of Binary tree?
4
votes
1answer
642 views

Optimal Binary Search Trees Knuth

Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289 Please have a look at this paper, specifically page 18 in which he tries to prove his ...
1
vote
1answer
197 views

prove that in binary heap buildheap function does at most 2N-2 comparison

prove that in binary heap buildheap function does at most 2N-2 comparison I don't know how should I prove it I need some hint thanks. buildheap procedure: we have n element and we build a heap at ...
2
votes
0answers
19 views

Repairing a perfect binary merkle forest

Let's say we have a forest of imperfect binary merkle trees of different heights (this is an invariant). Only the numbered nodes store data, the rest store hashes. Here is an example with 4 trees, ...
0
votes
1answer
22 views

Edge-disjoint paths in trees

How do I prove the following proposition? Let $T$ be a tree, and let $S$ be a subset of the vertices. If $|S|$ is even then we can partition $S$ into pairs $(x_i,y_i)$ such that the paths $x_i-y_i$ ...
1
vote
1answer
18 views
0
votes
0answers
22 views

Trying to convert algorithm from recursive to iterative

I have this algorithm to sum binary tree branches from leftmost branch to rightmost one, so the solution is an array of sums: ...
0
votes
0answers
36 views

Number of weight-balanced nodes in binary tree

I have to show that a binary tree with $n$ nodes has at least $(n-1)/2$ weight-balanced nodes and at most $n-1$ weight-balanced nodes. Here a node is weight-balanced if its siblings satisfy $\...
0
votes
0answers
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 ...
1
vote
2answers
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: ...
0
votes
0answers
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 ...
0
votes
0answers
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). ...
1
vote
1answer
320 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 <...

1
2 3 4 5
10