Questions tagged [binary-trees]

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

Filter by
Sorted by
Tagged with
105
votes
2answers
33k views

BIT: What is the intuition behind a binary indexed tree and how was it thought about?

A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial. Although the tutorial is complete in ...
97
votes
5answers
110k 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?
31
votes
1answer
18k 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 ...
30
votes
2answers
7k views

Not all Red-Black trees are balanced?

Intuitively, "balanced trees" should be trees where left and right sub-trees at each node must have "approximately the same" number of nodes. Of course, when we talk about red-black trees*(see ...
28
votes
2answers
10k views

Counting binary trees

(I'm a student with some mathematical background and I'd like to know how to count the number of a specific kind of binary trees.) Looking at Wikipedia page for Binary Trees, I've noticed this ...
28
votes
1answer
8k views

Which combinations of pre-, post- and in-order sequentialisation are unique?

We know post-order, post L(x) => [x] post N(x,l,r) => (post l) ++ (post r) ++ [x] and pre-order ...
27
votes
1answer
45k views

Two definitions of balanced binary trees

I have seen two definitions of balanced binary trees, which look different to me. A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number ...
25
votes
1answer
4k views

Why does the splay tree rotation algorithm take into account both the parent and grandparent node?

I don't quite understand why the rotation in the splay tree data structure is taking into account not only the parent of the rating node, but also the grandparent (zig-zag and zig-zig operation). Why ...
22
votes
1answer
4k views

AVL trees are not weight-balanced?

In a previous question there was a definition of weight balanced trees and a question regarding red-black trees. This question is to ask the same question, but for AVL trees. The question is, ...
20
votes
5answers
487 views

Efficient compression of unlabeled trees

Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $...
20
votes
2answers
779 views

Creating a Self Ordering Binary Tree

I have an assignment where I need to make use a binary search tree and alter it to self order itself such that items that are accessed the most (have a higher priority) are at the top of the tree, the ...
16
votes
2answers
12k views

Proving a binary heap has $\lceil n/2 \rceil$ leaves

I'm trying to prove that a binary heap with $n$ nodes has exactly $\left\lceil \frac{n}{2} \right\rceil$ leaves, given that the heap is built in the following way: Each new node is inserted via ...
16
votes
2answers
9k views

Colour a binary tree to be a red-black tree

A common interview question is to give an algorithm to determine if a given binary tree is height balanced (AVL tree definition). I was wondering if we can do something similar with Red-Black trees. ...
16
votes
2answers
989 views

Is there a faster solution for the Google Code Jam Great Wall Problem

Consider the following Google Code Jam round 1C question: The Great Wall of China starts out as an infinite line, where the height at all locations is $0$. Some number of tribes $N$, $N \le 1000$, ...
14
votes
2answers
5k views

Proving a binary tree has at most $\lceil n/2 \rceil$ leaves

I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction? For people who were following in the ...
14
votes
2answers
179 views

Function that spreads input

I'd like to know if there is a function $f$ from n-bit numbers to n-bit numbers that has the following characteristics: $f$ should be bijective Both $f$ and $f^{-1}$ should be calculable pretty fast $...
12
votes
2answers
5k views

Number of possible search paths when searching in BST

I have the following question, but don't have answer for this. I would appreciate if my method is correct : Q. When searching for the key value 60 in a binary search tree, nodes containing the key ...
11
votes
4answers
4k views

Can the pre-order traversal of two different trees be the same even though they are different?

This question pretty much explains that they can, but does not show any examples of there being two different trees with the same pre-order traversal. It is also mentioned that the in-order ...
10
votes
3answers
43k views

Why is the minimum height of a binary tree $\log_2(n+1) - 1$?

In my Java class, we are learning about complexity of different types of collections. Soon we will be discussing binary trees, which I have been reading up on. The book states that the minimum height ...
10
votes
1answer
14k views

Proof that a randomly built binary search tree has logarithmic height

How do you prove that the expected height of a randomly built binary search tree with $n$ nodes is $O(\log n)$? There is a proof in CLRS Introduction to Algorithms (chapter 12.4), but I don't ...
10
votes
2answers
1k views

How does one efficiently produce all binary sequences with an equal number of 0's and 1's?

A binary sequence of length $n$ is just an ordered sequence $x_1,\ldots,x_n$ so that each $x_j$ is either $0$ or $1$. In order to generate all such binary sequences, one can use the obvious binary ...
10
votes
2answers
3k views

What is the average height of a binary tree?

Is there any formal definition about the average height of a binary tree? I have a tutorial question about finding the average height of a binary tree using the following two methods: The natural ...
9
votes
3answers
4k views

Logarithmic vs double logarithmic time complexity

In real world applications is there a concrete benefit when using $\mathcal{O}(\log(\log(n))$ instead of $\mathcal{O}(\log(n))$ algorithms ? This is the case when one use for instance van Emde Boas ...
9
votes
1answer
5k views

Range update + range query with binary indexed trees

I am trying to understand how binary indexed trees (fenwick trees) can be modified to handle both range queries and range updates. I found the following sources: http://kartikkukreja.wordpress.com/...
9
votes
1answer
985 views

Splay tree with odd number of rotations

When inserting an item into a splay tree, rotations are performed in pairs based on either a zig-zag or zig-zig pattern. When there is an odd number of rotations to be performed, one could either do ...
8
votes
1answer
1k views

Does a graph always have a minimum spanning tree that is binary?

I have a graph and I need to find a minimum spanning tree to a given graph. What is to be done so that the output obtained is a binary tree?
8
votes
3answers
15k views

What is “rank” in a binary search tree and how can it be useful?

I am having a bit of trouble wrapping my mind around what a ranked binary search tree is and why having a rank is important. I am hoping that someone can clarify a few things for me. What I have ...
8
votes
0answers
609 views

Chained operations on sequences with two operators

Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation? Can we learn from matrix chain multiplication? A generalization of matrix chain ...
7
votes
3answers
6k views

When are binary trees better than hashtables in real world applications?

I am currently bushing up on my data structures and basic algorithms, part of that is the Binary Tree. I do understand the algorithms, and how to implement a binary search tree and such. I do so how ...
7
votes
1answer
2k views

What are the main ideas used in a Fenwick tree? [duplicate]

While I was solving a programming competition question, I came across a technique advertised as suitable for the solution. A so called Fenwick tree (a.k.a binary indexed tree) was at the heart of this ...
7
votes
1answer
25k 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 ...
7
votes
4answers
1k views

Is there a binary tree structure with fast access to recently accessed elements and worst $O \left( \log n \right )$ complexity?

The idea of splay trees is very nice as they move frequently accessed elements to the top, which can gain a considerable speed up in many applications. The drawback is that in the worst case an ...
7
votes
1answer
24k views

What is the depth of a complete binary tree with $N$ nodes?

This question uses the following definition of a complete binary tree†: A binary tree $T$ with $N$ levels is complete if all levels except possibly the last are completely full, and the last level ...
7
votes
1answer
1k views

Huffman Code VS Hu–Tucker Code

Before I'll ask my question, let me start with my understanding of the definitions, to prevent myself with further confusion, as well as giving some background. Huffman Code is the binary-code ...
7
votes
1answer
6k views

How to find a local minimum of a complete binary tree?

How to find a local minimum of a complete binary tree? Consider an $n$-node complete binary tree $T$, where $n = 2^d − 1$ for some $d$. Each node $v \in V(T)$ is labeled with a real number $x_v$. ...
7
votes
2answers
661 views

Algorithm for listing all binary trees of a given height

I've been trying to find an algorithm to list all binary trees of a given height $h$. Note that I'm not trying to count them: the number of such trees is given in the OEIS (A001699). All the ...
6
votes
2answers
13k views

Maximum number of nodes with height h

How is $\frac{n}{2^{h+1}}$ the maximum possible number of nodes at height $h$ for a binary search tree or heap tree? I saw this as proof to asymptotically bound the ...
6
votes
2answers
197 views

Help with proof involving weighted full binary tree

Given a full binary tree, $T$ (each node is either a leaf or possesses exactly two children), with $n$ leaf nodes: $v_1,v_2,...,v_n$, and weights associated with the leaf nodes: $w_1,w_2,...,w_n$, the ...
6
votes
1answer
1k views

What linked list data structure adjustments would give me fast random lookup?

I am presently using an doubly linked list (C++ std::list) to hold a bunch of records that each have a unique integer identifier. The linked list is created in ...
6
votes
2answers
327 views

Balanced Binary Search Tree Two-Sum with Constraints

My question spawns from this question. The question is straightforward: Can we find whether there exist 2 values in a balanced binary search tree where their sum equals a given target value? Now ...
6
votes
1answer
2k views

KD-Tree implementation with lat/lon coordinates

I have implemented a KD-Tree that stores coordinates (latitude, longitude). I have also implemented a Nearest Neighbor search algorithm using the Haversine distance. My question is, will I get correct ...
6
votes
2answers
490 views

Why isn't the time complexity of constructing a Fenwick tree tighter than $O(n\lg n)$?

Intuition: Suppose I have an array of nonzero integer values $A[n]$ and a partially constructed Fenwick tree of this array: $F[k], n>k$. I can see why inserting the next element would be worst ...
6
votes
1answer
776 views

Optimize binary search on Segment Tree by storing past result

Goal Let $A[n]$ be an arbitrary array of integers of length $n$. Let $S$ be a segment tree, represented by an array of records: each record containing the left and right bounds ($[l,r]$) of the ...
6
votes
2answers
226 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 ...
5
votes
3answers
785 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 ...
5
votes
1answer
455 views

Prove that for a general data structure - operations Extract_min() and Insert(x) cost $\Omega(\log n)$?

I've been given the following problem: Given a data structure $M$ that is based on comparisons and supports the following methods on a group of numbers $S$: $\text{Insert}(x)$ – add $x$ to $S$ $\...
5
votes
2answers
481 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?
5
votes
1answer
3k 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{...
5
votes
1answer
463 views

What is the complexity of these tree-based algorithms?

Suppose we have a balanced binary tree, which represents a recursive partitioning of a set of $N$ points into nested subsets. Each node of the tree represents a subset, with the following properties: ...
5
votes
1answer
480 views

Why aren't tries generally used?

To store say integers (positive), we prefer to use red black BSTs. I have never seen a explicit use of a trie anywhere to store numbers. I believe we can convert numbers to string and store them in ...