# 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
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 (...
1answer
13k views

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)... 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, ... 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 ... 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. 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. ... 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, ... 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 ... 2answers 159 views ### Time Complexity of the code I am having trouble finding the time complexity of the below code. ... 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}= ... 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 ... 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 ... 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 ... 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 ... 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%... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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, ... 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 ... 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,... 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 ... 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 ... 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 ... 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 ... 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 to 1 Next 1 should be set at ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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. 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 ... 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 ... 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 ... 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......
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?
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...