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

count number of partitions of a set with n elements into k subsets
This program is for count number of partitions of a set with n elements into k subsets I am confusing here
return k*countP(n1, k) + countP(n1, k1);
can some one explain what is happening here? why we are multiplying with k?NOTE>I know this is not the best way to calculate number of partitions that would be DP
// A C++ program to count number of partitions // of a set with n elements into k subsets #include<iostream> using namespace std; // Returns count of different partitions of n // elements in k subsets int countP(int n, int k) { // Base cases if (n == 0  k == 0  k > n) return 0; if (k == 1  k == n) return 1; // S(n+1, k) = k*S(n, k) + S(n, k1) return k*countP(n1, k) + countP(n1, k1); } // Driver program int main() { cout << countP(3, 2); return 0; }

Longest substring problems
So I am practicing algorithms and I am able to do the subsequence problems pretty easily as it is not too difficult to form a recurrence and then turn that into DP. However when I do the longest Substring problems I am having issues creating the recurrence in a way that is easily converted to DP.
this is my solution to length of longest palindromic substring and I believe it works, but it is not trivial to memoize without using lru_cache
s = 'ababac' @functools.lru_cache(maxsize=None) def f(i, j, flag): global s if i == j: return 1 elif i > j: return 0 else: m1 = m2 = m3 = 1 if not flag: m1 = f(i, j1, False) m2 = f(i+1, j, False) if s[i] == s[j]: m3 = f(i+1, j1, True) + 2 return max(m1,m2,m3) a = f(0, len(s) 1, False)

Binary Search using a for loop, searching for words in a list and comparing
I'm trying to compare the words in "alice_list" to "dictionary_list", and if a word isnt found in the "dictionary_list" to print it and say it is probably misspelled. I'm having issues where its not printing anything if its not found, maybe you guys could help me out. I have the "alice_list" being appended to uppercase, as the "dictionary_list" is all in capitals. Any help with why its not working would be appreciated as I'm about to pull my hair out over it!
import re # This function takes in a line of text and returns # a list of words in the line. def split_line(line): return re.findall('[AZaz]+(?:\'[AZaz]+)?', line) #  Read in a file from disk and put it in an array. dictionary_list = [] alice_list = [] misspelled_words = [] for line in open("dictionary.txt"): line = line.strip() dictionary_list.extend(split_line(line)) for line in open("AliceInWonderLand200.txt"): line = line.strip() alice_list.extend(split_line(line.upper())) def searching(word, wordList): first = 0 last = len(wordList)  1 found = False while first <= last and not found: middle = (first + last)//2 if wordList[middle] == word: found = True else: if word < wordList[middle]: last = middle  1 else: first = middle + 1 return found for word in alice_list: searching(word, dictionary_list)
 EDITED CODE THAT WORKED  Updated a few things if anyone has the same issue, and used "for word not in" to double check what was being outputted in the search.
"""Binary Search""" # search for word, if the word is searched higher than list length, print words = alice_list for word in alice_list: first = 0 last = len(dictionary_list)  1 found = False while first <= last and not found: middle = (first + last) // 2 if dictionary_list[middle] == word: found = True else: if word < dictionary_list[middle]: last = middle  1 else: first = middle + 1 if word > dictionary_list[last]: print("NEW:", word) # checking to make sure words match for word in alice_list: if word not in dictionary_list: print(word)

Converting a multiway tree to leftchild/rightsibling format?
I'm trying to write C++ code that, given a multiway tree, converts that tree into a binary tree represented in the leftchild/rightsibling format. For example, given this tree:
A /  \ B C D /  \  E F G H / \ I J
I'd like to output this tree:
A / B / \ E C \ \ F D / \ / I G H \ J
I'm not sure how to approach this problem. How should I think about doing this?

How to build a Create Function to create a linked list in c
I want to build a create function that would create new list, the function will get a 4 "function pointer", The create function will Allocates a new linkedListCreates a new empty list. This function receives the functions which will be used for copying elements into the list, freeing them when needed, comparing if elements are greater from each other and comparing it elements are equal. note that the internal iterator is not valid after calling this function. return values: NULL  if one of the parameters is NULL or allocations failed. A new List in case of success.
#include <stdio.h> #include <stdlib.h> #include <assert.h> /* Data type for the elements of the UniqueOrderedList container*/ typedef int* Element; /** Type of function pointer which copies a data element of the UniqueOrderedList */ typedef Element (*copyElements)(Element); /** Type of function pointer which releases a data element of the UniqueOrderedList */ typedef void (*freeElements)(Element); /** Type of function pointer which checks if two elements of the UniqueOrderedList * are equal. * the function should return true when two elements are equal and false otherwise. */ typedef bool (*elementsEquals)(Element, Element); /** Type of function pointer which checks if e1 element is greater than e2 element. * the function should return true when e1 is greater and false otherwise. */ typedef bool (*elementGreaterThan)(Element e1, Element e2); typedef struct uniqueOrderedList_t{ int element; struct uniqueOrderedList_t* next; } *list; Element copyInt(Element e){ int* newInt = malloc(sizeof(*newInt)); if(!newInt){ return NULL; } *newInt = *((int*)e); return newInt; } void freeInt(Element e){ free(e); } bool intEquals(Element e1, Element e2){ return *((int*)e1) == *((int*)e2); } bool intGreaterThan(Element e1, Element e2){ return *((int*)e1) > *((int*)e2); } /* bewlow is the function that I need to build */ list uniqueOrderedListCreate(copyElements a, freeElements b, elementsEquals c, elementGreaterThan d){ /*dont know what to do here*/ }
 Inserting into red black tree when the parent P is red but the uncle U is black

How to append two argument items into a stack (Python3)
So I'm currently practicing DFS & BFS approaches to binary trees and I am confused on how multiple arguments are being passed into the
.append
statements below. I know that.append
can only take one argument and that when the the arguments are encapsulated in parenthesis they are treated as so, but what does it mean when you encapsulate them?class Solution: def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ stack = [] if root is not None: stack.append((1, root)) # < Here depth = 0 while stack != []: current_depth, root = stack.pop() if root is not None: depth = max(depth, current_depth) stack.append((current_depth + 1, root.left)) # < Here stack.append((current_depth + 1, root.right)) # < Here return depth
To reiterate, what does
.append((arg1, arg2))
mean? How are thoseargs
treated and what logic is behind it? 
How to proceed Thread binary trees postorder traversal
I want to make a postorder traversal in the thread binary tree.
If I want to do a postorder traversal, not a recursive one,
For terminal nodes, I can move them by inserting the next node address in the link to an empty child node field.
But in the case of parent node must be moved any way if I don't get the hang of things constantly.
For example, in the case of "A B * C D / ", I can go 'B' > '*' to use B's right empty link field(thread).
But when I go '*' > 'C' or '/' > ''
'*' and '/' both link fields are full by child node. I don't know how to proceed.
Please let me know how you can proceed.

What are the distinguishing features of sorting algorithms?
Specify ALL features of all sorting algorithms: bubble sort, selection sort, quicksort, merge sort, counting sort.

Google Interview Question: Assign People and Cars optimally on 2D array
My friend recently got this question from google interview and I think this is a tricky question.
Given People and Cars on 2D array, find an Optimal Assignment of people and cars where you define what "optimal" means.
If we define Optimal Assignment as the least total Manhattan distance between all pairs (min sum of each pair's distance). What could be a good way to solve this and which algorithm should I use?
Is there any better way to solve this problem more efficiently with different definition of "optimal"?

Timsort execution time in Python
I'm studying some sorting algorithms and their execution times. I implemented some algorithms in Python and I am measuring how long they take to sort some arrays. I found that Python natively implements Timsort as sorting algorithm for lists. However, I wanted to compare the native Timsort with an implementation I found on GitHub (this one). How is it possible that the native implementation takes 0.000630140304565 seconds to sort an array of 51200 elements while the implementation I linked before takes 40.7546050549 seconds to sort the same array?
[EDIT] To get time I use "time.time()" before and after the execution of the sorting algorithm and then I just make the difference.
I expected the native implementation to be faster, but not so much. The fact is that I have implemented also other sorting algorithms in Python and, for example, MergeSort takes 0.148133039474 seconds to sort the same array. I did not expect this big difference between MergeSort and the Python implementation of Timsort.
[EDIT2] So the problem is that the implementation I found is not efficient and is not really Timsort. Sorry guys, I just found that Timsort was theta(nlgn) and I believed that was the right implementation. Now the problem is: does an efficient Python implementation of Timsort exist?