Questions tagged [binary-tree]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
130 views

Ideal Profits in companies in Perfect Binary Search tree

I'm trying to solve the following problems here: In the X world, companies have a hierarchical structure to form a large binary tree network (can be assumed to be a perfect binary tree). Thus every ...
driver's user avatar
  • 111
2 votes
2 answers
274 views

Can you define node pointers in a base binary tree class?

I've created two separate binary tree classes, with some shared functions/variables and some that are not shared. So I have tried to abstract away the similarities in a base BinaryTree class. class ...
yomag1234's user avatar
3 votes
2 answers
794 views

Is the TreeSet class in java a Red Black Binary Search Tree?

I simply wanted to know if the internal implementation of the TreeSet class in java is Red Black Binary Search Tree. Ideally, I would think that it is a threaded RB-BST, since it supports iteration ...
ShayakSarkar's user avatar
-2 votes
2 answers
175 views

What is the correct use of -> operator when working with pointers?

I'm pretty new with C so I have encountered many doubts with pointers. I've already search a lot about this but there are some things that still are not clear for me, and I also think this will help ...
Nicolas Bazan's user avatar
-2 votes
1 answer
598 views

Optimal Data Structure for Searching though String

I am current developing a karaoke app in JavaFX, I need advise on the most optimal data structure storing a huge list of songs (library). I am inclined to use Binary Search Trees due to its Big O ...
Lavesh Deepak Panjwani's user avatar
1 vote
1 answer
86 views

Converting binary tree into doubly linked circular list

I am a beginner in computer science and have been asked to write a program to convert a binary tree into a circular linked list (order of the nodes in list are in inorder traversal of the tree). I ...
bobthebuilder's user avatar
1 vote
1 answer
201 views

Does a Self-Balancing Self-Sorting Binary Search Tree exist?

When we are inserting into a self-balancing tree, can we also assume it is sorting itself using those same operations? Or rather is there a traversal method that gets us the elements as a sorted list?
Jack Avante's user avatar
0 votes
1 answer
2k views

Class structure: How should a binary tree and it's node class be implemented in Java in terms of class files?

In implementing a binary tree in Java, should the node class be a separate class file independent of the BinaryTreeclass, or should it be a default class in the same class file as the BinaryTree class?...
aCarella's user avatar
  • 329
0 votes
2 answers
4k views

How to represent a directory structure in a binary tree?

I was just thinking about implementing a binary tree with its root pointing to the parent folder and then the children pointing to subdirs nested within to store a directory structure in a binary tree....
Alien128's user avatar
  • 121
4 votes
1 answer
1k views

Is it worth parsing an infix algebraic expression to postfix and then an expression tree?

I am trying to make a simple expression parser, in which users type an expression in infix notation (for example ln((1+2)(3-4))) to apply some calculations. To make this possible I need to tokenize ...
JulianSoto's user avatar
1 vote
3 answers
1k views

Which data structure is best for an auto complete drop down that learns?

I made an auto complete text box for an application I'm working on. The text box basically has an associated list that it searches each time you enter something in the box. If you enter something ...
namarino41's user avatar
1 vote
1 answer
276 views

How to build an optimal tree given items costs and edge costs?

Given: a list of 'leaves' that each have a cost, the cost of creating an 'edge' The constraint that a constructed tree node can at most have two children. We now want to find the tree with the ...
Qqwy's user avatar
  • 4,799
3 votes
2 answers
1k views

Deleting a node and returning the deleted node's value in a Binary Search Tree?

Hi I have a programming project where I'm basically using a Binary Search Tree to implement a min/max priority queue. I'm having trouble with the popMin/popMax methods. I get how to get the minimum/...
Justin's user avatar
  • 77
0 votes
1 answer
2k views

Is this a balanced or unbalanced binary tree?

Good day, I am new to java and new to this forum but I request a bit of help. I am learning java on my own and I am currently learning binary trees. I have come an algorithm that is giving me a little ...
xhenier's user avatar
  • 19
2 votes
2 answers
3k views

Can Two Binary Search Trees Have the Same Values but Different Structures?

Define a BST as: all left descendants <= n < all right descendants. Then is it possible to build two binary search trees with different structures but the same exact values? Duplicate values ...
Josh Pearce's user avatar
1 vote
0 answers
295 views

Binary tree pruning

I have a generic binary tree which is used for calculating combinations of things - i.e. a powerset in set parlance. Most of the time it is used for calculating subsets of size N. As a real world ...
Robbie Dee's user avatar
  • 9,815
1 vote
1 answer
507 views

reordering sorted array to level-order array without queue

I have very large sorted array, stored on the disk. I can random access any element. I want to make it level-ordered in order to speed up binary search there. The idea is borrowed from: http://...
Nick's user avatar
  • 295
0 votes
1 answer
756 views

Extract All Possible Paths from Expression-Tree and evaluate them to hold TRUE

This is a follow-up question of my previous one: https://stackoverflow.com/questions/38421950/better-class-structure-for-logical-expression-parsing-and-evaluation Brief introduction: rules as ...
nonsensation's user avatar
1 vote
1 answer
71 views

How do you achieve the 'BST Property' in a Template Binary Search Tree?

We recently started learning about binary search trees. We created one of our own using integers as our Key/Data. It's easy to achieve the BST property using an int key, but what happens when we ...
Sebastian King's user avatar
3 votes
3 answers
1k views

Binary Search Tree without Natural Ordering

This is kind of a multi-part question. Is it possible to do a binary search tree if the data does not possess natural ordering? Would you be forced to impose artificial ordering to such data? Like ...
adv's user avatar
  • 347
1 vote
1 answer
120 views

Joining binary trees

Suppose we have a set of binary trees with their inorder and preorder traversals given and where no tree is a subtree of another tree in the given set. Now another binary tree Q is given. Find ...
radha's user avatar
  • 19
-6 votes
1 answer
814 views

BST to AVL in O(n) [closed]

I found in different places on the internet how to turn a Binary Search Tree into an AVL tree in O(nlog(n)). I was wondering how can this be done in O(n) (as the worst case limit). It kinda seems ...
Bobo's user avatar
  • 101
0 votes
2 answers
2k views

Keeping track of the number of nodes in the subtree in black and red trees

I was wondering, if I have a black and red tree and I want to keep track of the number of nodes in the subtree, what is the most effective way to do so? I mean how do I work with these values while ...
mathew7k5b's user avatar
8 votes
1 answer
3k views

Is this Red-Black tree insertion pseudocode from Introduction to Algorithms (CLRS) correct?

For the Red-black tree insertion fixup the book distinguishes between 6 cases, 3 of which are symmetric. The cases are (z is the node being inserted): Case 1: z's uncle is red Case 2: z's uncle is ...
Bar's user avatar
  • 183
2 votes
1 answer
74 views

Efficiently determining many-to-many subset relation

I'm doing market basket analysis. I have a set of transactions. Every transaction is a set of items that were bought. I then have a set of itemsets (i.e. a set of items) that I want to determine the ...
user avatar
-1 votes
1 answer
960 views

Comparison of Red/Black Tree to Java ArrayList, what are advantages of each? [closed]

I was looking over some of the general Big-O Algorithm Complexities for different data structures, and wondered what Java's ArrayList would be considered. Since I tend to default to an ArrayList in ...
DoubleDouble's user avatar
0 votes
1 answer
1k views

Merging Two Binary Search Trees

What time in terms of Big O will it take to merge two BST's in One? Each having no of nodes n and height O(log n) with no common element. Resultant should be also a BST
user123's user avatar
  • 25
0 votes
1 answer
921 views

Python object oriented programming problems while implementing binary search tree

I am shifting from procedural C programming to OOP Python programming and I faced some problems while implementing binary search trees. I cannot make my Tree_Node null in case of deleting it. In C I ...
clereamusjd's user avatar
0 votes
1 answer
2k views

How do binary trees use memory to store its data?

So I know that arrays use a block on contiguous memory addresses to store data to memory, and lists make use of static arrays and when data is appended to the list, if there is no room, a new static ...
sw123456's user avatar
  • 249
12 votes
3 answers
839 views

Do binary trees serve a specific purpose in storing hierarchical data? What is their canonical use?

I understand the structure of binary trees and how to traverse them. However, I am struggling to realize their actual uses, purposes in programs and programming. When I think about 'real life' ...
sw123456's user avatar
  • 249
0 votes
2 answers
2k views

Efficiently find whether Binary Search Tree is Height Balanced or not?

A binary tree is height balanced if and only if the two subtrees of root are height balanced and the difference between the two subtrees height is at most 1. I implemented a code in java to find ...
Sumeet's user avatar
  • 101
13 votes
2 answers
13k views

Is it possible to speed up a hash table by using binary search trees for separate chaining?

I want to implement a Hash Table using Binary Search Trees to reduce the search complexity in the Separate Chaining process from O(n) (using linked list) to O(log n) (using BST). Can this be done, and ...
Aviral's user avatar
  • 149
2 votes
1 answer
2k views

Difference between sibling lists, left-child right-sibling binary tree and doubly-chained tree

The Wikipedia page for suffix trees descibes sibling lists as Each node has a pointer to its first child, and to the next node in the child list it is a part of. Wikipedia describes left-child right-...
user avatar
4 votes
1 answer
566 views

Is this Wikipedia pseudocode for in-order generic tree traversal correct?

Wikipedia states that the following algorithm works for any tree (not necessarily binary trees) Perform pre-order operation For each i (with i = 1 to n) do: Visit i-th, if present ...
9a3eedi's user avatar
  • 2,099
1 vote
1 answer
2k views

In which of the following tree traversal all the child nodes are visited first before the parent node [closed]

In an n-ary tree... Given a reference to some child node And a reference to a distant parent of the referenced child node Is there a method that a parent node can use to figure out which of its ...
Eric's user avatar
  • 113
2 votes
2 answers
3k views

Level order sorted binary tree from a binary tree

Lets suppose we have a binary tree . Tree node structure is as struct node { int val ; struct node *left , *right ; } Now we have to sort the tree in level order manner . For example lets ...
Saurabh Jain's user avatar
2 votes
2 answers
327 views

Is there a known standard data structure which is a hash table that resolves collisions using a binary tree?

Is there a known standard data structure which is a hash table that resolves collisions using a binary tree? If so what is the name of this data structure? I imagine such a structure would be useful ...
newlogic's user avatar
  • 415
3 votes
4 answers
2k views

Tournament bracket method to put distance between teammates

I am using a proper binary tree to simulate a tournament bracket. It's preferred any competitors in the bracket that are teammates don't meet each other until the later rounds. What is an efficient ...
Fred Thomsen's user avatar
0 votes
3 answers
1k 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 ...
shalki's user avatar
  • 101
1 vote
1 answer
713 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 ...
Instinct's user avatar
22 votes
4 answers
43k 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 ...
Srikanth Kandalam's user avatar
3 votes
2 answers
2k 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. ...
Darrel Hoffman's user avatar
0 votes
1 answer
6k 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 ...
Sudhakar's user avatar
  • 123
1 vote
1 answer
1k 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 ...
floatfil's user avatar
13 votes
3 answers
26k 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 post-order ...
Shivan Dragon's user avatar
3 votes
2 answers
5k 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 ...
MosesA's user avatar
  • 141
6 votes
1 answer
6k 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: http://www.cs.cornell.edu/courses/...
Meena's user avatar
  • 161
2 votes
1 answer
3k 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 ...
yasar's user avatar
  • 185
-1 votes
1 answer
1k views

How should I setup a UI for editing a binary tree? [closed]

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 ...
asawyer's user avatar
  • 139
0 votes
1 answer
1k 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 ...
rrazd's user avatar
  • 1,398