Questions tagged [binary-trees]
a tree in which each node has no more than two children
1
vote
2answers
73 views
Difficulty understanding the solution of heap problem in CLRS book?
I am reading the solution of this problem in CLRS:
Show that there are at most $\lceil {n/2^{h+1}} \rceil$ nodes of height $h$ in any $n$-element heap.
Solution: All the nodes of height $h$ ...
1
vote
2answers
46 views
Random walks on Complete Binary Trees
Let $T$ be a complete binary tree of height $n$ and root $r$.
A random walk starts at $r$, and at each step uniformly at random moves on a neighbor.
There are $m$ random walkers all starting at $r$ ...
0
votes
0answers
72 views
Binary search on a path of minimum heap
WhereTo(H,X) is searching for the place to set X (an integer) in a minimum heap-H.
The function is executing a binary search on a path of a heap.
Assumption: We have the specific path because it ...
1
vote
1answer
51 views
AVL tree worst case height proof
The worst case height of AVL tree is $1.44 \log n$. How do we prove that?
I read somewhere about Fibonacci quicks but did not understand it.
1
vote
2answers
54 views
Build a balanced binary tree from list in linear time
I couldn't figure this one out. Given an unsorted list, we want to build a balanced binary tree (not a search tree, namely - left child is of lower key, and right child of higher key). Can we do it in ...
0
votes
0answers
20 views
How does a binary tree waste memory when stored as nodes and references?
I'm researching binary trees and came across this section describing storage methods.
It states that:
In a language with records and references, binary trees are typically constructed by having a ...
2
votes
1answer
49 views
Merging of two increasing binary trees why do we exchange left and right subtree
We say that a binary tree : $B(l, x, r)$ is increasing if $x$ is smaller than all the nodes of the binary tree and if $l$ and $r$ are also increasing trees.
One way to merge these kind of trees is as ...
1
vote
1answer
30 views
Minimal, “natural” set of operations to manipulate a binary tree
Consider binary trees with some abstract values at the leaves. A tree t2 is said to be "derivable" from a tree t1 iff the set of values in the leaves of t2 is included in the set of values in the ...
0
votes
0answers
30 views
Storing binary tree with arbitrarily sized nodes without linked-list or large 32-bit pointers
So you can store a binary tree without pointers using a 1-D array:
Binary Trees can be represented using 1-D array in memory(Fig 1).The rule to store binary tree in array are :
The values of ...
2
votes
1answer
47 views
Prove number of nodes in heap
Consider a variation of the normal heap which we will call the x-heap
The x-heap of height $h$ has the following properties:
It will have $2^h$ nodes
A height of $0$ corresponds to the single root ...
1
vote
1answer
209 views
$O(n\log n)$ algorithm for minimizing number of inversions in leaves of complete binary tree
I'm having trouble making an algorithm to fit these specs:
Given a complete binary tree ($n = 2^d$ leaves) with integers in leaves.
Reading the leaves from left to right makes a sequence of integers (...
2
votes
1answer
21 views
Binary Tree Multithreaded Time Complexity
Let's say you want to get the value of all nodes in a binary tree (order doesn't really matter). If in each thread, you spawn two more threads to deal with the left subtree and the right subtree, then ...
2
votes
1answer
49 views
Algorithm to find the two closest elements in a BST
For example, consider an AVL tree:
Performing the two_close(T) should give back (13, 12), as they are the closest elements together. Said another way, you can take any two other elements in the tree, ...
1
vote
1answer
56 views
Finding optimal multiplication order and optimal binary tree
I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree.
Consider the following ...
0
votes
0answers
39 views
Binary tree for 2 elements
I want to understand Binary Search for 2 element list made of 1,2. I draw a tree as below. Is it correct?
If I want to search for an element 2, it will make 2 comparisons. If I want to search for an ...
2
votes
0answers
32 views
Documentation of “bin number” trees
TL;DR: I implemented a special (?) binary tree and can't find any further details on the method I used on the internet. I would like to know if there are any scientific papers discussing my ...
5
votes
2answers
183 views
What is the point of traversing a binary tree in preoder, inorder or postorder?
Why would you want to traverse a binary tree in preoder, inorder or postorder? Why not use an order like breadth-first search for all graphs?
1
vote
1answer
37 views
AVL Rotations Abbreviations
I read that there are 4 types of rotations:
Left rotation
Right rotation
Left-Right rotation
Right-Left rotation
What are the corresponding abbreviations: RL,LR,RR,LL? Is there a reference how to ...
1
vote
1answer
45 views
Optimize sorting matrix entries by row and column
I am writing a routine to store an $M$-by-$N$ sparse matrix in a balanced binary tree. The insertion routine calls a comparison function to determine where a new matrix entry $(i,j)$ should be ...
1
vote
1answer
27 views
Binary trees and preallocated nodes
I want to design a binary tree with preallocated nodes, in order to avoid calling malloc/free every time I want to insert/delete a node. The problem is I don't know ahead of time how many nodes the ...
1
vote
1answer
146 views
AVL Tree rotations : How to balance below AVL Tree with imbalance at root node
How to balance this AVL tree after inserting node 5, using left/right rotations as indicated in the AVL tree tutorial. I have tried applying both double rotations but with no luck. Either of the ...
1
vote
1answer
50 views
Searching in a Binary Search Tree
I'm studying Binary Search Trees (BST) and I would like to verify that my understanding of BSTs is correct.
For example, let S = [17, -10, 7, 19, 21, 23, -13, 31, 59].
Binary Search Tree for S, with ...
1
vote
1answer
24 views
Running time based on smallest subtree
I've constructed an algorithm on (rooted) binary trees, where the running time at a node depends on the size of its smaller subtree, where we compute from each leaf upwards towards the root.
More ...
1
vote
2answers
68 views
Deriving the average depth for a randomly generated binary search tree
If $D(n)$ is the internal path length (sum of the depths of all nodes) for some tree $T$ with $n$ nodes then we have the following recurrence relation: $$D(n)=D(i)+D(n-i-1)+N-1$$ where I simply taken ...
0
votes
1answer
28 views
How can we form a graph from this problem?
So from the above diagram, we can move either right or down. So a binary tree is built that way. It's written ...
2
votes
1answer
323 views
The number of balanced trees with N node and L leaves
An algorithm is requested to calculate all balanced binary trees which can be built with $N$ nodes, having exactly $L$ leaves. A balanced tree is a binary tree in which the difference between the ...
1
vote
2answers
56 views
is a deterministic algorithm for breadth-first traversal possible (binary heap)
Imagine I have a binary heap, traversed in a breadth first manner like so:
...
2
votes
2answers
805 views
Proving Postorder Traversal's Time Complexity
I am looking at the following algorithm for performing a Postorder Traversal of a binary tree
...
1
vote
2answers
159 views
Why can't we just use preorder traversal to check if a tree is subtree of binary tree?
Is preorder traversal enough to check if a tree is subtree of a binary tree?
Are there any scenarios which I can miss if I use just the preorder traversal?
What other methods can be used to check if ...
2
votes
1answer
409 views
Average height of a BST with n Nodes
I have to find the maximum, minimum, and average height of a BST with n nodes. After doing some researching I found that the maximum height is $n-1$ and the minimum height is $\log_2(n+1)-1$. My ...
2
votes
1answer
53 views
Selecting a subtree in an array representation of a binary tree
Consider a zero-indexed array representation of a binary tree (as in a binary heap), where
0 is the root
The left child of i is ...
-4
votes
1answer
31 views
Construct an array from a binary tree
I am looking for a suggestion. I know it is possible to construct a binary tree from an array. I want to know that vice verse is true? Is it possible to construct an array from a binary tree? If yes ...
1
vote
0answers
48 views
Upper bound on the average path length in binary search tree
I have been reading the chapter 6.2.2 in Knuth's book about lower and upper bound on the average path length in binary search tree.
And I have problems with understanding small details of Theorem M (...
4
votes
2answers
855 views
Time Complexity to find height of a BST
Below is a question I was asked in an Interview
What is the best case time complexity to find the height of a Binary Search Tree?
I answered it explaining using the below algorithm
$\mathrm{...
2
votes
1answer
168 views
Heap structure in array, computing parent and child
I am studying data structures from Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, and in the section of heapsort it talks about a data structure beneath the algorithm : a heap, ...
1
vote
0answers
26 views
Example of binary trees with maximum rotation distance
In the 1988 paper Rotation Distance, Triangulations, and Hyperbolic Geometry, Sleator, Tarjan and Thurston show that for any pair of $n$-node binary trees, the maximum rotation distance between them ...
2
votes
1answer
190 views
Insert into binary tree and keep it balanced
Assuming each node stores its depth, how can I achieve this? Note that I'm not talking about a binary search tree so I shouldn't need rotations. All I want is filling the tree from left to right.
2
votes
1answer
32 views
What is the average size of a jump in a binary tree?
Assume that a full binary tree is layed out in memory recursively in the following way.
First the Root followed by Tree representation of left subtree followed by tree representation of right subtree. ...
0
votes
1answer
22 views
Need help understanding which values can be inserted into a specific node in a binary tree
I am studying binary trees and I am failing to see what numbers can be inserted into this specific node position. The values to pick from are : 16, 24, 36, 45, 49, 51, 58.
I have tried values 24, 36, ...
2
votes
0answers
125 views
Analysis expected depth of a binary search tree given random values?
I have a guess about the problem above. Suppose I have a binary search tree $T$ initially empty. Suppose I drawn $x_1,\ldots,x_k$ (from some real interval $[a,b]$) keys and I want to insert the keys ...
1
vote
2answers
79 views
1
vote
0answers
35 views
Building segment tree to find minimum suffix sum in range
Let's say we have array $A$ of $N$ integers, each of them in the range $[-1, 1]$. We define an array $B$ of $N+1$ integers, such that $$B_{N+1} = 0, \\B_i = A_i + A_{i+1} + A_{i+2} + \dots + A_{N}= ...
1
vote
1answer
48 views
Question on word probability for hierarchical softmax used in natural language processing
I am reading the following paper: https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf
On page 4 of the paper they describe the ...
1
vote
0answers
66 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 ...
0
votes
2answers
44 views
Recursive relations in binary trees
I have an exercise in my algorithm's Course for which I have the correction but do not understand it.
1.Exercise .
Let Th be a full binary three of height h(meaning all the levels all completely ...
0
votes
0answers
41 views
Generation vs expansion BFS
I can not understand the difference between generation and expansion of nodes. How the time and space complexity of BFS are different in each two scenarios?
...
2
votes
1answer
69 views
Proving time-complexity analysis for merge-sort-like algorihtm
I have this algorithm, which is exactly like merge-sort, but instead of halving the array each recursion, it actually splits it into $1/4$ and $3/4$ parts. Other then that, it does exactly the same ...
2
votes
1answer
144 views
Weighted probability using Huffman Tree
I want to produce a value from a set, where each value has an associated weight.
Eg:
[(1, 4), (2, 3), (3, 3)]
should give me a 40% chance of picking 1, and a 30%...
0
votes
1answer
70 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
2answers
798 views
How does in-order traversal in Binary search tree works (recursion)
I visit some question but their implementations are slightly different and my doubt is not like theirs. I have this code in Javascript.
The code is typical BST implementation with methods to support ...
