Search Results

• Finding if a Binary Tree is a Binary Search Tree

- by dharam
Today I had an interview where I was asked to write a program which takes a Binary Tree and returns true if it is also a Binary Search Tree otherwise false. My Approach1: Perform an inroder traversal and store the elements in O(n) time. Now scan through the array/list of elements and check if element at ith index is greater than element at (i+1)th index. If such a condition is encountered, return false and break out of the loop. (This takes O(n) time). At the end return true. But this gentleman wanted me to provide an efficient solution. I tried but I was unsuccessfult, because to find if it is a BST I have to check each node. Moreover he was pointing me to think over recusrion. My Approach 2: A BT is a BST if for any node N N-left is < N and N-right N , and the INorder successor of left node of N is less than N and the inorder successor of right node of N is greater than N and the left and right subtrees are BSTs. But this is going to be complicated and running time doesn't seem to be good. Please help if you know any optimal solution. Thanks.

• Binary to strings as binary? C #/.NET

- by acidzombie24
Redis keys are binary safe. I'd like to mess around and put binary into redis using C#. My client of choice doesn't support writing binary keys it uses keys and it make sense. However i am just fooling around so tell me how i can do this. How do i convert a raw byte[] into a string? At first i was thinking about converting a byte[] to a utf8 string however unicode has some checks to see if its valid or not. So raw binary should fail. Actually i tried it out. Instead of failing i got a strange result. My main question is how do i convert a raw byte[] to the equivalent string? My unimportant question is why did i get a 512 byte string instead of an exception saying this is not a valid UTF8 string? code var rainbow = new byte[256]; for (int i = 0; i < 256; i++) { rainbow[i] = (byte)i; } var sz = Encoding.UTF8.GetString(rainbow); var szarr = Encoding.UTF8.GetBytes(sz); Console.WriteLine("{0} {1} {2}", ByteArraysEqual(szarr, rainbow), szarr.Length, rainbow.Length); Output False 512 256

• represent binary search trees in python

- by Bunny Rabbit
how do i represent binary search trees in python?

• Do dconf use EXI binary XML?

- by Hibou57
A question came to my mind reading an answer to the question What are the differences between gconf and dconf?. In an reply to the above question, Oli said: Binary read access is far faster than parsing XML. However, there exist a W3C recommendation for binary XML, since 2010: Efficient XML Interchange (EXI) Format 1.0. Is this what dconf uses? If Yes, where is it confirmed? If No, was there some investigations toward it at some time, and what was the conclusions? Thanks for any tracks, I'm curious to know.

• Binary on the Coat of Arms of the Governor General of Canada

- by user132636
Can you help me further this investigation? Here is about 10% of the work I have done on it. I present it only to see if there are any truly curious people among you. I made a video a few weeks ago showing some strange things about the Governor General's Coat of Arms and the binary on it. Today, I noticed something kinda cool and thought I would share. Here is the binary as it appears on the COA: 110010111001001010100100111010011 As DEC: 6830770643 (this is easily found on the web) Take a close look at that number. What do you notice about it? It has a few interesting features, but here is the one no one has pointed out... Split it down the middle and you have 68307 70643. The first digit is double the value of the last digit. The second digit is double the second last digit. The third digit is half of the third to last digit. And the middle ones are even or neutral. At first, I thought of it as energy. ++-nnnn+-- But actually you can create something else with it using the values. 221000211. See how that works. You may be asking why that is significant. Bare with me. I know 99% are rolling their eyes. 221000211 as base3 gives you this as binary: 100011101000111 100011101000111 as HEX is 4747, which converts to "GG". Initials of Governor General. GG.ca is his website. When you convert to base 33 (there are 33 digits in the original code) you get "GOV" Interesting? :D There is a lot more to it. I'll continue to show some strange coincidences if anyone is interested. Sorry if I am not explaining this correctly. By now you have probably figured out that I have no background in this. Which is why I am here. Thank you.

• Binary Search Tree - Postorder logic

- by daveb
I am looking at implementing code to work out binary search tree. Before I do this I was wanting to verify my input data in postorder and preorder. I am having trouble working out what the following numbers would be in postorder and preorder I have the following numbers 4, 3, 14 ,8 ,1, 15, 9, 5, 13, 10, 2, 7, 6, 12, 11, that I am intending to put into an empty binary tree in that order. The order I arrived at for the numbers in POSTORDER is 2, 1, 6, 3, 7, 11, 12, 10, 9, 8, 13, 15, 14, 4. Have I got this right? I was wondering if anyone here would be able to kindly verify if the postorder sequence I came up with is indeed the correct sequence for my input i.e doing left subtree, right subtree and then root. The order I got for pre order (Visit root, do left subtree, do right subtree) is 4, 3, 1, 2, 5, 6, 14 , 8, 7, 9, 10, 12, 11, 15, 13. I can't be certain I got this right. Very grateful for any verification. Many Thanks

• C++ find largest BST in a binary tree

- by fonjibe
what is your approach to have the largest BST in a binary tree? I refer to this post where a very good implementation for finding if a tree is BST or not is bool isBinarySearchTree(BinaryTree * n, int min=std::numeric_limits<int>::min(), int max=std::numeric_limits<int>::max()) { return !n || (min < n->value && n->value < max && isBinarySearchTree(n->l, min, n->value) && isBinarySearchTree(n->r, n->value, max)); } It is quite easy to implement a solution to find whether a tree contains a binary search tree. i think that the following method makes it: bool includeSomeBST(BinaryTree* n) { if(!isBinarySearchTree(n)) { if(!isBinarySearchTree(n->left)) return isBinarySearchTree(n->right); } else return true; else return true; } but what if i want the largest BST? this is my first idea, BinaryTree largestBST(BinaryTree* n) { if(isBinarySearchTree(n)) return n; if(!isBinarySearchTree(n->left)) { if(!isBinarySearchTree(n->right)) if(includeSomeBST(n->right)) return largestBST(n->right); else if(includeSomeBST(n->left)) return largestBST(n->left); else return NULL; else return n->right; } else return n->left; } but its not telling the largest actually. i struggle to make the comparison. how should it take place? thanks

• Find kth smallest element in a binary search tree in Optimum way

Hi, I need to find the kth smallest element in the binary search tree without using any static/global variable. How to achieve it efficiently? The solution that I have in my mind is doing the operation in O(n), the worst case since I am planning to do an inorder traversal of the entire tree. But deep down I feel that I am not using the BST property here. Is my assumptive solution correct or is there a better one available ?

• Binary Heap Traversal Proof by Induction

- by Ahmet Alp Balkan
How to prove that: Let's say we have two binary heap trees H1 and H2 with size N. If their inorder traversals are the same, prove that H1=H2 by induction on N.

• How to Serialize Binary Tree

- by Veljko Skarich
I went to an interview today where I was asked to serialize a binary tree. I implemented an array-based approach where the children of node i (numbering in level-order traversal) were at the 2*i index for the left child and 2*i + 1 for the right child. The interviewer seemed more or less pleased, but I'm wondering what serialize means exactly? Does it specifically pertain to flattening the tree for writing to disk, or would serializing a tree also include just turning the tree into a linked list, say. Also, how would we go about flattening the tree into a (doubly) linked list, and then reconstructing it? Can you recreate the exact structure of the tree from the linked list? Thank you/

• Understanding binary numbers in terms of real world objects

- by Kaushik
When I represent a number in the decimal system, I have an intuitive knowledge of what it amounts to. For example take the number '10': I understand that it means 10 apples or 10 people... i.e I can count in the real world. But as soon as the number is converted to any other system, this understanding no longer applies. For example 10 when converted to binary will be 1010...now what does this represent? Is there a way to understand this number 1010 in terms of counting objects in the real world?

• Cannot execute binary file

- by user291727
I am new to Ubuntu and I'm trying to install Popcorn Time. I downloaded 32 bit version and tried to install it but that's where the problem started showing. I duble clicked the executable file and well, nothing happened. It's a official download from their web-site but it doesn't work. Maybe I'm doing something wrong.....Anyway, I found out that you can insatll it from a script, but people keep talking in ubuntu terms and I don't understand it, so I have a few questions: 1.How to make a script? (witch I'm suppose to run in terminal using bash comand), 2.Is it normal that i cannot run the installer, and if that is an installer or just files for the program. 3.If it is an installer, how do I make it work? 4.What does " Cannot execute binary file" mean? Thank you in advance, hope I'm not asking too many questions(please understand that I'm new to ubuntu) and sorry about my English. xD

• Include Binary Files in DEB package

- by user22611
I need to build a DEB package from mainly Node.js Javascript files, but it should include some binary files as well. They are listed inside debian/source/include-binaries. Otherwise I get the error message dpkg-source: error: unrepresentable changes to source The command in question is: bzr builddeb -- -us -uc After adding the file include-binaries, when running bzr builddeb -- -us -uc again, now I get a different error: It says dpkg-source: error: aborting due to unexpected upstream changes, see /tmp/mailadmin_0.0-1.diff.n6m5_6 I have no idea how to get rid of this. In the next line of output it tells me dpkg-source: info: you can integrate the local changes with dpkg-source --commit But if I run this command in the build area of my package, it gives me the unrepresentable changes to source error message again, even though debian/source/include-binaries is present in the build area as well. I am missing the way out of this... I tried deleting all files that are produced by the build process, still no success. Further details: The target directory is /opt/mailadmin. Since this directory is unusual, I listed it in the file debian/mailadmin.install (which contains one line:) opt/mailadmin opt/ The bzr builddeb process uses this file as expected.

• Deletion procedure for a Binary Search Tree

- by Metz
Consider the deletion procedure on a BST, when the node to delete has two children. Let's say i always replace it with the node holding the minimum key in its right subtree. The question is: is this procedure commutative? That is, deleting x and then y has the same result than deleting first y and then x? I think the answer is no, but i can't find a counterexample, nor figure out any valid reasoning. EDIT: Maybe i've got to be clearer. Consider the transplant(node x, node y) procedure: it replace x with y (and its subtree). So, if i want to delete a node (say x) which has two children i replace it with the node holding the minimum key in its right subtree: y = minimum(x.right) transplant(y, y.right) // extracts the minimum (it doesn't have left child) y.right = x.right y.left = x.left transplant(x,y) The question was how to prove the procedure above is not commutative.

• Designing binary operations(AND, OR, NOT) in graphs DB's like neo4j

- by Nicholas
I'm trying to create a recipe website using a graph database, specifically neo4j using spring-data-neo4j, to try and see what can be done in Graph Databases. My model so far is: (Chef)-[HAS_INGREDIENT]->(Ingredient) (Chef)-[HAS_VALUE]->(Value) (Ingredient)-[HAS_INGREDIENT_VALUE]->(Value) (Recipe)-[REQUIRES_INGREDIENT]->(Ingredient) (Recipe)-[REQUIRES_VALUE]->(Value) I have this set up so I can do things like have the "chef" enter ingredients they have on hand, and suggest recipes, as well as suggest recipes that are close matches, but missing one ingredient. Some recipes can get complex, utilizing AND, OR, and NOT type logic, something like (Milk AND (Butter OR spread OR (vegetable oil OR olive oil))) and I'm wondering if it would be sane to model this in a graph using a tree type representation? An example of what I was thinking is to create three "node" types of AND, OR, and NOT and have each of them connect to the nodes value underneath. How else might this be represented in a Graph Database or is my example above a decent representation?

• Is it any good to use binary arithmetic in a C++ code like "C style"?

- by user827992
I like the fact that the C language lets you use binary arithmetic in an explicit way in your code, sometimes the use of the binary arithmetic can also give you a little edge in terms of performance; but since I started studying C++ i can't really tell how much i have seen the explicit use of something like that in a C++ code, something like a pointer to pointer structure or an instruction for jumping to a specific index value through the binary arithmetic. Is the binary arithmetic still important and relevant in the C++ world? How i can optimize my arithmetic and/or an access to a specific index? What about the C++ and the way in which the bits are arranged according to the standard? ... or i have taken a look at the wrong coding conventions ... ?

• Binary Log Format in MySQL

- by amritansu
Reference manual for MySQL 5.6 states that " Some changes, however, still use the statement-based format. Examples include all DDL (data definition language) statements such as CREATE TABLE, ALTER TABLE, or DROP TABLE. " Does this statement means that even if we have ROW format for binary logs all DDLs will be logged in binary log as statement based? How does this affect replication? Kindly help me to understand this.

• Linux binary support under Mac OS X?

- by penyuan
Is there a way to add Linux binary compatibility to Mac OS X 10.5+ such as that found in FreeBSD? For instance, and totally as an example, here is Arlequin 3.5, a population genetics software that my lab uses with a Linux binary: http://cmpg.unibe.ch/software/arlequin35/Arl35Downloads.html Thank you very much!

• How to calculate the maximum block length in C of a binary number

- by user1664272
I want to reiterate the fact that I am not asking for direct code to my problem rather than wanting information on how to reach that solution. I asked a problem earlier about counting specific integers in binary code. Now I would like to ask how one comes about counting the maximum block length within binary code. I honestly just want to know where to get started and what exactly the question means by writing code to figure out the "Maximum block length" of an inputted integers binary representation. Ex: Input 456 Output: 111001000 Number of 1's: 4 Maximum Block Length: ? Here is my code so far for reference if you need to see where I'm coming from. #include <stdio.h> int main(void) { int integer; // number to be entered by user int i, b, n; unsigned int ones; printf("Please type in a decimal integer\n"); // prompt fflush(stdout); scanf("%d", &integer); // read an integer if(integer < 0) { printf("Input value is negative!"); // if integer is less than fflush(stdout); return; // zero, print statement } else{ printf("Binary Representation:\n", integer); fflush(stdout);} //if integer is greater than zero, print statement for(i = 31; i >= 0; --i) //code to convert inputted integer to binary form { b = integer >> i; if(b&1){ printf("1"); fflush(stdout); } else{ printf("0"); fflush(stdout); } } printf("\n"); fflush(stdout); ones = 0; //empty value to store how many 1's are in binary code while(integer) //while loop to count number of 1's within binary code { ++ones; integer &= integer - 1; } printf("Number of 1's in Binary Representation: %d\n", ones); // prints number fflush(stdout); //of ones in binary code printf("Maximum Block Length: \n"); fflush(stdout); printf("\n"); fflush(stdout); return 0; }//end function main