The binary-tree tag has no wiki summary.
0
votes
3answers
249 views
Print bottom view of a binary tree
For a binary tree we define horizontal distance as follows:
Horizontal distance(hd) of root = 0
If you go left then hd = hd(of its parent)-1, and
if you go right then hd = hd(of its ...
1
vote
0answers
147 views
Binary Tree/Knowledge Base design C++
Currently I have a binary tree template setup where my main is using it with strings to make a question/answer game. I'm using a knowledge base that works as an interface to the binary tree that main ...
2
votes
2answers
207 views
Is Pre-Order traversal same as Depth First Search?
It seems to me like pre-order traversal and DFS are same as in both the cases we traverse from root till the left branch and back to root and then to the right branch recursively. Could any please ...
2
votes
2answers
388 views
Unit testing to prove balanced tree
I've just built a self-balancing tree (red-black) in Java (language should be irrelevant for this question though), and I'm trying to come up with a good means of testing that it's properly balanced.
...
0
votes
1answer
614 views
Convert Algebraic Expression directly into Binary Tree Structure (sans prefix / postfix)
I am looking all over internet to find a logic to convert an Algebraic Expression into a Binary Tree.
I could only find ones where you first convert the algebra expression to postfix or prefix and ...
0
votes
0answers
41 views
Solving point in interval queries
There are n intervals given by starting (a[1], a[2], ..., a[n]) and ending points (b[1], b[2], ..., b[n]) and m queries of the form: given an integer x find the indices of the intervals which contain ...
1
vote
1answer
170 views
Balance Tree with depth n has how many nodes maximum?
I couldn't find the answer anywhere, but let's say we have a B-Tree with min = 1 and max = 2: What is the formula to calculate the maximum number of nodes in this B-Tree if the depth is say 100? This ...
4
votes
4answers
3k views
Usefulness of pre and post order traversal of binary trees
This may be very naive, but I was wondering, it the context of binary trees (plain, sorted and balanced), of all the traversal types:
depth-first pre-order
depth-first in-order
depth-first ...
29
votes
5answers
3k views
Programming interview question on Trees
I was asked this interview question at a top internet website company recently.
Certain empty glasses of water are arranged in the following order
When you pour liquid into the 1st glass if ...
3
votes
2answers
761 views
Morse Code - Binary Tree
How is the Morse Code representation of a letter determined?
"E" = "."
"T" = "-"
Why is it not alphabetic? As in let "A" = ".", "B" = "-", "C" =".-", etc.
I'm trying to develop an algorithm for a ...
6
votes
1answer
1k views
What is the usage of Splay Trees in the real world?
I decided to learn about balanced search trees, so I picked 2-3-4 and splay trees.
What are the examples of splay trees usage in the real world?
In this Cornell: ...
2
votes
1answer
792 views
Keeping binary search tree balanced
I am educating myself on algorithms and data structures. For that, I am doing a simple program that would read lines like this:
bdhj 168.24
dahf 42.88
dhfa 128.92
First column represents an account ...
0
votes
1answer
388 views
How should I setup a UI for editing a binary tree?
I need to allow the user to create an binary tree. I have a Backbone Model populating properly from the database, the problem I am stuck on is how do I setup the ui elements in a way that is fairly ...
0
votes
1answer
393 views
Why can't an AVL tree be recreated using pre-order traversal?
Given a binary search tree, I understand why I can use breadth-first and pre-order traversal to list the entries of the tree in such a way as to reconstruct the tree in the order in which its ...
0
votes
7answers
3k views
How to find siblings of a tree?
On my interview for an internship, I was asked following question:
On a whiteboard write the simplest algorithm with use of recursion which would take a root of a so called binary tree (so called ...
5
votes
2answers
637 views
Do you get the benefits of a B-Tree in a managed language?
My understanding is that one of the key features of a B-Tree (and a B+Tree) is that it is designed such that the size of its nodes are some multiple of the block size of whatever media the data is ...
4
votes
2answers
338 views
Is this the right strategy to convert an in-level order binary tree to a doubly linked list?
So I recently came across this question - Make a function that converts a in-level-order binary tree into a doubly linked list. Apparently, it's a common interview question.
This is the strategy I ...
3
votes
2answers
688 views
Speed of MySQL type index access vs. binary jump search on a huge file?
I am dead set on moving over to a MySQL database for some huge data sets I'm working with but right now I don't have the time. In the meantime I am curious about a technical performance issue ...
0
votes
3answers
846 views
AVL Tree Balancing Problem
Take the following tree:
50
40
30
20
10
Which node will be balanced first? 50 or 30
Case 1: 50
The tree is
30
20 40
...
6
votes
6answers
3k views
Which self balancing binary tree would you recommend?
I'm learning Haskell and as an exercise I'm making binary trees. Having made a regular binary tree, I want to adapt it to be self balancing. So:
Which is most efficient?
Which is easiest to ...
