Questions tagged [binary-trees]

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

Filter by
Sorted by
Tagged with
121
votes
2answers
39k 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 ...
110
votes
5answers
133k 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?
35
votes
2answers
23k 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 ...
31
votes
1answer
9k 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 ...
30
votes
2answers
8k 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-...
29
votes
2answers
12k 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 ...
27
votes
1answer
48k 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
5k 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
5k 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
555 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
830 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 ...
17
votes
2answers
14k 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
11k 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
1k 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
6k 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
199 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 $...
13
votes
2answers
6k 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 ...
12
votes
1answer
17k 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 ...
11
votes
4answers
6k 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 ...
11
votes
6answers
1k views

Find the number using binary search against one possible lie

We all know this classic problem, "there is some hidden number and you have to interactively guess it.", which could be solved using binary search when we know that maximum number that we can guess. ...
10
votes
3answers
49k 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
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/...
10
votes
2answers
2k 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
4k 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
5k 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
4answers
25k 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 ...
9
votes
1answer
1k 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
2k 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
1answer
33k 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 ...
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)...
8
votes
2answers
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 ...
8
votes
1answer
8k 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$. ...
8
votes
0answers
617 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
3k 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
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
2answers
783 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
15k 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
245 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
28k 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 ...
6
votes
3answers
6k views

Compute height of AVL tree as efficiently as possible

Given an AVL tree, I want to compute its height as efficiently as possible. $\newcommand{\bf}{\text{bf}}\newcommand{\height}{\text{height}}$ Each node of an AVL tree stores its balance factor ($\bf$),...
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
409 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
2answers
4k views

Why is this not a valid Red-Black tree?

I'm having some difficulty understanding the rules for valid red-black tree. If my understanding is correct there are 4 rules that a tree has to follow to be a red-black tree. Every node has a color ...
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
657 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
886 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
0answers
154 views

Impossibility of certain type of tree traversal algorithm

I was wondering for some time how to approach a situation like the following one. Imagine a standard binary tree data structure with $n$ nodes in it. Each node contains pointers to its left and right ...
6
votes
0answers
211 views

Correctness of a greedy Algorithm on Knockout Tournaments

You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
6
votes
2answers
274 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 ...

1
2 3 4 5
10