Assign inorder index to Binary Tree
How do we assign inorder index to binary tree?
Given a tree below:
1
2 3
4 5 6 7
Assign an index below to above tree as you can see below:
4
2 6
1 3 5 7
Following code does not work for case 6 as it assigns 10 as we are double counting passed down index from the argument and from the left child. Can we achieve this without using global variable?
int assignIndex(Node root, int index) {
if (root == null)
return 0;
int leftIndex = assignIndex(root.left, index);
root.index = leftIndex + index + 1;
int rightIndex = assignIndex(root.right, root.index);
if (rightIndex == 0)
return root.index;
else
return rightIndex;
}
1 answer

The problem in the above program is return of two different values at two different occasions. So the issue can be solved by returning only latest index values at all occasions if you don't want to use global variables.
int assignIndex(Node root, int index) { if (root.left != null) index = assignIndex(root.left, index); index++; root.index = index; if (root.right != null) index = assignIndex(root.right, index); return index; }
See also questions close to this topic

How do I make a "composite key" (and what is this even called)?
I have two key strings, representing two objects of two different classes of objects. The keys are unique within their classes. I need to create a unique key representing the combination of these two keys. How do I do this?
I can't just concatenate them, because any character could be present in the base keys. I could maybe escape the concatenation delimiter before I concatenate? I could create a hash of the two keys, but this feels heavy.
Are there built in functions to help me do this? Is this "called something"? It seems like this would be a common (solved) problem.
(I'm looking for this specifically in Javascript, but I'm curious about higher level solutions or frameworks as well)

Interview  Array of Integers A with a size N, with indexes 0 <= P <= Q < N, write a function to find maximum of (A[Q] + A[P] + QP)
I received this interview question, but I wasn't sure how to solve it:
You're given an array of integers A with a size N. For the indexes 0 <= P <= Q < N, write a function that finds the maximum of (A[Q] + A[P] + QP). Expected time complexity is O(N) and O(1) space.
What would be the solution in Java?
Thanks in advance.

The shortest path between nodes in graph
I don't know if I should be asking this here or not, the question is about algorithm. Imagine you have an undirected graph. Edges have different values. Imagine that some vertice are "good" and some are "bad". Now I want to determine two good nodes, so that path between them is shortest possible (if path include bad nodes that's not a problem).

I'm trying to insert an element in specific index but i got this output
public void InsertAtFront(E data){ MyNode<E> x = new MyNode(data); if (tail == null ){ tail =x; } x.setNext(head); if(head != null ){ head.setPrev(x); } head =x ; size++; } public void InsertAtEnd(E data){ MyNode<E> x = new MyNode(data); if ( head == null){ x.setPrev(null); head = x; return; } x.setNext(null); x.setPrev(tail); tail = x; MyNode tmp = head; while (tmp.getNext() != null){ tmp = tmp.getNext(); } tmp.setNext(x); x.setPrev(tmp); size++; } public void InsertAtPos(int index, E x){ MyNode tmp = head; for (int i=0; i <= index && tmp.getNext() != null; i++){ tmp =tmp.getNext(); } MyNode <E> newNode = new MyNode<>(x); newNode.setNext(tmp.getNext()); tmp.setNext(newNode); if(newNode.getNext() != null) newNode.getNext().setPrev(newNode); newNode.setPrev(tmp); } Mylinkedlist mylinkedlist = new Mylinkedlist(); MyNode myNode = new MyNode(); mylinkedlist.InsertAtFront(5); mylinkedlist.InsertAtFront(2); mylinkedlist.InsertAtEnd(4); mylinkedlist.InsertAtEnd(8); mylinkedlist.InsertAtPos(2,9); mylinkedlist.trevarse();
and here is my output 2 5 4 9 8
in this case the method should print 2 9 5 4 8 i've tried to debug this code but it didn't work , the methods InsertAtFront and InsertAtEnd are working correctly i think the bug is from InsertAtPos , and i want to know if i can improve my methods and i'm wondering if we can use recursion here ?

Collisions in a HashTable Data Structure
I need help understanding hashtables, so correct e if I am wrong. A hashtable computes the index of the array with a key by encripting the key. The resultant encryption is the index. Collisions are unavoidable because there are high chances of getting the same index and we can use chaining to create a linked list inside each index of the array. The runtime of a hashtable is o(1)

Binary Tree array implementation
I've got a problem with implementing Binary Tree from given array. I can find a root, but I don't know how to find children of Nodes.
e.g. [8, 2, 3, 4, 20, 6] > tree:
4 2 6 8 3 20
How can I find those children?

push_back() binary tree into vector
I'm trying to put all the elements from a binary search tree into a vector, in order. Here is the function:
edit: adding instructions for clarity. Write a class for implementing a simple binary search tree capable of storing numbers. The class should have member functions:
void insert(double x) bool search(double x) void inorder(vector <double> & v)
The insert function should not use recursion directly or indirectly by calling a recursive function. The search function should work by calling a private recursive member function
bool search(double x, <double> & v )
The inorder function is passed an initially empty vector v; if fills v with the inorder list of numbers stored in the binary search tree. Demonstrate the operation of the class using a suitable driver program.
EDIT: Added full code for clarity.
#include "stdafx.h" #include <iostream> #include <vector> class BinaryTree { private: struct TreeNode { double value; TreeNode *left; TreeNode *right; TreeNode(double value1, TreeNode *left1 = nullptr, TreeNode *right1 = nullptr) { value = value1; left = left1; right = right1; } }; TreeNode *root; //pointer to the root of the tree bool search(double x, TreeNode *t) { while (t) { std::cout << "running through t." << std::endl; if (t>value == x) { return true; } else if (x < t>value) { std::cout << "wasn't found, moving left." << std::endl; search(x, t>left); } else { std::cout << "wasn't found, moving right." << std::endl; search(x, t>right); } } std::cout << "wasn't found." << std::endl; return false; } public: std::vector<TreeNode> v; BinaryTree() { root = nullptr; } void insert(double x) { TreeNode *tree = root; if (!tree) { std::cout << "Creating tree." << x << std::endl; root = new TreeNode(x); return; } while (tree) { std::cout << "Adding next value." << std::endl; if (tree>value == x) return; if (x < tree>value) { tree = tree>left; tree>value = x; } else { tree = tree>right; tree>value = x; } } } bool search(double x) { return search(x, root); } void inOrder(std::vector <double> & v) { { if (left) left>inOrder(v); v.push_back(value); if (right) right>inOrder(v); } } TreeNode* left = nullptr; TreeNode* right = nullptr; double value; }; int main() { BinaryTree t; std::cout << "Inserting the numbers 5, 8, 3, 12, and 9." << std::endl; t.insert(5); t.insert(8); t.insert(3); t.insert(12); t.insert(9); std::cout << "Looking for 12 in tree." << std::endl; if (t.search(12)) { std::cout << "12 was found." << std::endl; } std::cout << "Here are the numbers in order." << std::endl; return 0; }
I'm unable to get the values to push into the vector. Any ideas as to how I can accomplish this?

Javascript Binary Search Tree methods not working
I am trying to build this simple Javascript Binary search tree. I have simply created the addItem method for the tree, but no item seems to get added to the tree. I have divided the addItem method into several other methods to ensure that the tree reference is passed properly without any errors. I think the problem is occurring in the addNode recursive calls.
Below the is the given code:
class Node{ constructor(value){ this.value=value; this.left=null; this.right=null; } show(){ console.log(this.value); } } class BST{ constructor(){ this.root=null; } addNode(node, item){ if(node==null){ node=new Node(item); } else if(item<=node.value){ this.addNode(node.left, item); } else { this.addNode(node.right, item); } } addFunc(tree, item){ this.addNode(tree.root, item); } addItem(item){ this.addFunc(this, item); } } let bst = new BST(); bst.addItem(5); bst.addItem(43); bst.addNode(12); console.log(bst); // shows BST{root:null}

Split Look up table for 128bits setbits calculation
How do you use splitting of lookup table for getting the set bits from a string.
I want to implement a split look up table to find the number of 1s in a array.
Thank You, 
Given an input array, how to find all the possible sub arrays with a given sum K and also, these sub arrays need not be contiguous
lets say array = [1,5,8,3,4]
and K = 12
So, the required sub arrays are array1 = [5,3,4], array2 = [1,8,3] and array3 = [8,4]
sum of elements of array1 = 5 + 3 + 4 = 12, array2 = 1 + 8 + 3 = 12, and array3 = 8 + 4 = 12

Bubble sort  Number of passes
This question is regarding the number of passes when executing a bubble sort.
By a pass, we mean one full iteration through the array. For example, one pass of the array
[1, 4, 2, 8, 5]
would be,[1, 4, 2, 8, 5] // (swapped 2 and 4) [1, 2, 4, 8, 5] // (swapped 5 and 8) [1, 2, 4, 5, 8]
This array only required 1 pass, but other arrays require multiple passes, such as the following array:
[10, 5, 4, 8, 2]
.My question is, without doing an actual bubble sort, what is the fastest algorithm that finds the number of passes that need to be executed in order to have the array fully sorted? The algorithm should have have a complexity faster than
O(N^2)
(in other words,O(NlogN)
or faster).
EDIT: an implementation on Prune's idea below would be appreciated.
EDIT 2: This is my current implementation which is flawed.
Take the unsorted array A, and call the sorted array A_sort. The array has size N.
Let bin(x) represent the index of x in A_sort, which is found using binary search.
Find the maximum difference through the following approach:
int diffMax = 0  bin(A[0]) + 1; for(int i = 1 to N): diffMax = max(diffMax, ibin(A[i]) + 1)
While this implementation works for arrays with no repeated elements, it fails on arrays with repeated elements.