Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [binary-trees]

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

1
vote
1answer
15 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 ...
0
votes
0answers
19 views

Are heaps equal if first Heapinsert and immediately Heapdelete a node

Pretty much what the title asks: If I add a node via HeapInsert and immediately delete it with HeapDelete, will the heaps be the same? (assuming it's a MAX heap)
1
vote
1answer
31 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 ...
0
votes
0answers
28 views

Help with understanding the type of task

I am stuck with a problem I want to solve, and I cannot understand which approach to use to solve it efficiently. The problem sounds as follows: "There are initial (x,y) = (0,1). We can move left or ...
0
votes
0answers
33 views

Binary search tree with minimum potential

How to construct a n-node binary serach tree such that its potential is the minimum? The size, rank and potential are defined as follows The size $s(v)$ is the number of nodes in a subtree (include v)...
1
vote
1answer
15 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 ...
0
votes
0answers
28 views

Average runtime for search in AVL tree

The Question: Suppose there is a hash table implemented with an array of AVL trees. Assume the hash function was very bad for our data, and half of the keys got mapped to one position/bucket, and the ...
0
votes
0answers
61 views

Expected length of path from root node to leaf node in arbitrary tree

Let $T$ be an arbitrary binary search tree on $n$ keys. Arbitrary means that T is not necessarily random, so $T$ could have height $n$. Consider the following process: Start at the root of $T$. ...
1
vote
1answer
50 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
37 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
23 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
30 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
26 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 ...
0
votes
0answers
65 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 ...
0
votes
0answers
36 views

how many binary trees with 6 leaves have this property

How many binary trees with 6 leaves have 2 leaves on the left and 4 leaves on the right (trees are without degenerate nodes)
1
vote
2answers
40 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
266 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
69 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
135 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
44 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
25 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
42 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 (...
3
votes
2answers
418 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
51 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
24 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
78 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
29 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
21 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
73 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
70 views

Time Complexity of the code

I am having trouble finding the time complexity of the below code. ...
1
vote
0answers
23 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
33 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
47 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
40 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
26 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
44 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
69 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
61 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
444 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 ...
3
votes
1answer
155 views

$O(n\log n)$- algorithm for finding tree root

All numbers from $1$ to $n = 2^k-1$ are written in unknown way in a full binary tree of height $k$. We say that a number $t$ lies between $i$ and $j$ if after removing $t$ from the tree we obtain ...
0
votes
0answers
31 views

Why are red-black trees still preferred over weak AVL trees [duplicate]

Both have a maximum height of 2*logn WAVL trees have a maximum height of 1.44*logn if built using only insertions. If built using both insertions and deletions, then inserts will tend to restore the ...
3
votes
0answers
25 views

Proving an upper-bound on the cost of all calls to rebuild() during a sequence of m operations in a scapegoat tree

I'm reading through Open Data Structures by Pat Morin and am currently looking at scapegoat trees. The book is free and can be downloaded from here: http://opendatastructures.org/ods-java.pdf On page ...
-1
votes
1answer
38 views

Number of different increasing binary trees

This is a homework question that I am unable to solve. Any help would be really appreciated. Given $B$ an increasing binary tree with root $r$ and $n$ nodes labelled $1, 2, . . . , n$ such that on ...
0
votes
1answer
22 views

The optimal way to find leaves in a weighted full binary tree

Let T be a full binary weighted tree. For a node v in T, the cost of going right is a i.e w(v, v.right) = a while w(v, v.left) = b How do I find optimal paths to all leaves from the root. I don't ...
0
votes
1answer
158 views

BinaryTree minimum possible height

I have one question for which I don't know any good solution (and my solution doesn't satisfy constraints). Namely, on one of the interviews i got problem like this: Determine the minimum possible ...
1
vote
1answer
56 views

Why does the ouput of an NC0 circuit depend on only a constant number of input bits?

I understand that NC0 circuits have a constant depth and bounded gate fan-in of two, but I'm struggling how to understand why the language is in NC0 iff there is a constant c such that for every n, ...
3
votes
1answer
305 views

Difficulty in updating the balance factor of nodes in AVL tree

In this figure x,y,z are the nodes on which rotation is performed and T1, T2, T3, T4 are the subtrees. I have understood how the rotation is working and have no trouble with that. The problem I am ...
1
vote
1answer
55 views

Number of elements with lower index equal to some element, for all items on an array

Let $A$ be an array of size $n$, and $f(i, r, a_r)$ be the number of indices $k$ such that $a_k$ = $a_r$ and $i \le k \le r$. Example to clarify: Imagine the array: $[1, 2, 3, 2, 2, 3, 4, 5]$. $f(0,...
2
votes
1answer
51 views

Doubt regarding binary trees and counting

Question: A binary Tree T is semi-balanced, if for every node m in T: $$ \frac{R(m)}{2} <= L(m) <= 2*R(m) $$ where, L(m) is the number of nodes in the left sub-tree of m and R(m) is the ...
3
votes
0answers
140 views

Total number of red black tree arrangements

Consider a list of n integers. And assume we take each integer from this list sequentially and add it to a red-black tree. Then for the n! permutations of the list how many red-black tree ...