Questions tagged [binary-trees]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
62 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 (...
8
votes
1answer
13k 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{height}(v)...
4
votes
1answer
2k 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
56 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
297 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
60 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
25 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
420 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
159 views

Time Complexity of the code

I am having trouble finding the time complexity of the below code. ...
1
vote
0answers
58 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
128 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 ...
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 ...
0
votes
2answers
180 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 ...
2
votes
1answer
227 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
198 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
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
2answers
2k 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
1k 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 ...
3
votes
0answers
42 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
160 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
31 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
313 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
121 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
995 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
65 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
150 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
147 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 ...
1
vote
2answers
211 views

Calculating unbalanced binary trees

Two-part question: Is there any more specific name than "unbalanced binary tree" to describe the tree below? The distinguishing characteristics are: i. The root node and left children must have ...
2
votes
0answers
148 views

Algorithm to find nodes with given a distance

We have a map of a branching river without any islands (tree of confluences, see picture), there are piers on the river bank ( not necessarily on the confluences). We are given the distances between ...
2
votes
1answer
46 views

Inserting values at maximal distance from current value

I have the following problem. Given an array A, filled with 0s, we should set some elements to be equal 1, considering such rules: If all elements equal 0,set A[0] to 1 Next 1 should be set at ...
1
vote
1answer
83 views

Prove that the number of full nodes plus one is qual to the number of leaves in a nonempty binary tree

I'm trying to write an induction statement to prove a full node in a tree but I have no idea how to do that. I've always been terrible when it comes to logic. Where do I even start with this? I know ...
1
vote
1answer
2k views

Number of binary search trees with maximum possible height for n nodes

I'm using the definition of the height of a tree as the longest possible path from the root to a leaf by its number of edges, e.g. a tree of 2 nodes has a height of 1. With that in mind, what would ...
1
vote
1answer
603 views

Maximum sum of depths of all external nodes in a Binary Tree

Let $T$ be a (possibly improper) binary tree with $n$ nodes, and let $E(T)$ be the sum of the depths of all the external nodes of $T$. (In a proper binary tree each node have 0 or 2 children. An ...
-2
votes
1answer
484 views

Obtain data structure able to do reverse range updates

For given array $A$ of size $N$, note that the array is going to be permutation of the numbers from 1 to N, each number will be there exactly once, we want to obtain data structure being able to ...
0
votes
0answers
276 views

Code arithmetic expression in a binary tree

How to present (code into) an expression consisting of brackets and following operations: +, -, / and * into a binary tree. Then, I need to write an algorithm that will derive that very tree. Any ...
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 ...
0
votes
1answer
778 views

Time complexity of creating the unique binary tree from given inorder and preorder (or postorder) traversal sequences

Given inorder and preorder (or postorder) traversal sequences of a binary tree balanced binary tree binary search tree of n nodes, what is the time complexity of creating the respective unique tree.
1
vote
0answers
235 views

Proof of Fenwick Tree's correctness

Unfortunately (like many other authors) Fenwick does a very bad job of explaining his work (the Binary Indexed Tree) in the original text. The paper lacks a proper formal proof of why this structure ...
2
votes
2answers
818 views

Is there a way to calculate exactly how many binary trees are possible if only one of the preorder, inorder and postorder traversals is given?

I am studying tree traversals and I've got to know that we can uniquely determine the binary tree if their: Case 1. Preorder & inorder traversals are given or Case 2. postorder & inorder ...
4
votes
0answers
93 views

Number of binary trees of size $n$ such that all subtrees of same size are equal?

In the following, I consider rooted, unlabelled, ordered binary trees, where each node has exactly $0$ or $2$ children (I will simply call them binary trees). A binary tree $t'$ is a subtree of a ...
0
votes
1answer
510 views

Data structure that supports finding frequency of given element in $O(\log n)$ and most frequent elemnt in O(1) time

Ok, so I got this for homework and been struggling for a while now. The full assignment requires this: While N = number of elements in given array and n = number of different elements, init(S,A[1......
1
vote
1answer
250 views

Why do we need binary trees when we have multi branch trees? [closed]

Why do we need binary trees when we have multiway trees. Are binary trees even used. Are they used only for teaching the concepts of trees?
1
vote
1answer
50 views

rebalance red-black tree with many violations

Every red-black tree implementation I've come across use a strategy that considers re-balancing the tree after each mutation (e.g. insert, delete, ...). I have a situation where I graft several sub-...
1
vote
0answers
67 views

How to assign the increasing keys to the nodes of a complete binary tree on n nodes in inorder?

I'm looking at the Multiplicative Binary Search and come across this. It's the preparation you need to do for you to use the Multiplicative binary search procedure. I somehow do not know how to do ...
0
votes
0answers
277 views

Path of the binary tree which has the highest number of bends

It is an interview question: Given a binary tree print the path of the tree which has the highest number of bends. I could come up with a solution which will keep track the left or right child ...
1
vote
1answer
486 views

Rooted Binary Tree - Chain Nodes Algorithm

The question is that I have to give a recursive algorithm in pseudocode, that counts the number of chain node in a rooted binary tree. Chain node is defined as a node that has only one child and that ...
0
votes
1answer
458 views

Why postfix arithmetic expression is not ambiguous?

A binary tree can be written as an expression, no matter prefix, postfix or infix. But why an infix expression needs brackets, while the others don't? Say, why postfix, prefix produce only one binary ...
0
votes
1answer
239 views

Is there an example of an AVL tree that is taller than a binary heap?

I am curious because I took a quiz and answered false to the question: "The height of an AVL tree may be greater than the height of a binary heap with the same elements." I have been trying to think ...
1
vote
1answer
546 views

What do we benefit from using ternary search trees rather than binary search trees?

Ternary search trees are very common in the text editing area. They could be used to implement Auto complete feature, spell checking, Partial-Match searching, Near-Neighbor Searching & many many ...
0
votes
1answer
810 views

When to rebalance the AVL tree?

Consider we have an AVL tree. Its left subtree A has disbalance coefficient has value +1 (meaning the right subtree has greater depth). Its right son has disbalance coefficient -1 (meaning left ...

1 2 3
4
5
10