Morris (InOrder) traversal is a tree traversal algorithm that does not employ the use of recursion or a stack. In this traversal, links are created as successors and nodes are printed using these links. Finally, the changes are reverted back to restore the original tree. Algorithm Initialize current as root While current is not NULL …
HashMap computeIfAbsent() method in Java with Examples
The computeIfAbsent(Key, Function) method of HashMap class is used to compute value for a given key using the given mapping function, if key is not already associated with a value (or is mapped to null) and enter that computed value in Hashmap else null. If mapping function of this method returns null, then no mapping …
Continue reading “HashMap computeIfAbsent() method in Java with Examples”
Edit Distance
The edit distance algorithm is very popular among the data scientists. It’s one of the basic algorithms used for evaluation of machine translation and speech recognition. The naive approach would be to check for all possible edit sequences and choose the shortest one in-between. That would result in an exponential complexity and it’s an overkill …
Long VS Integer
Long is the Object form of long, and Integer is the object form of int. Integer is a signed 32 bit integer type Denoted as Int Size = 32 bits (4byte) Can hold integers of range -2,147,483,648 to 2,147,483,647 default value is 0 Long is a signed 64 bit integer type Denoted as Long Size …
How to avoid Integer Overflow when comparing two node valued in BST?
For example, if here are one BST as: [Integer.MIN_VALUE, Integer.MIN_VALUE] If I want to compare if the left child node is smaller or equal to parent nod – 1, the value gonna be overflow. In this case, don’t use Integer.MIN_VALUE, use null as the default instead. Here is an example about using null as comparison …
Continue reading “How to avoid Integer Overflow when comparing two node valued in BST?”
Recover Binary Search Tree
This is No.99 in LeetCode. Here are approaches to this problem: Approach 1: Sort an Almost Sorted Array Where Two Elements Are Swapped Algorithm Here is the algorithm: Construct inorder traversal of the tree. It should be an almost sorted list where only two elements are swapped. Identify two swapped elements x and y in …
How to get random number in a range in Java
Let’s use the Math.random method to generate a random number in a given range: public int getRandomNumber(int min, int max) { return (int) ((Math.random() * (max – min)) + min); } Why does that work? Well, let’s look at what happens when Math.random returns 0.0, it’s the lowest possible output: 0.0 * (max – min) …
Continue reading “How to get random number in a range in Java”
How to sort 2D array in Java
My code : Arrays.sort(intervals, new Comparator<int[]>(){ @Override public int compare( int[] a, int[] b ){ return a[0]==b[0] ? a[1] – b[1] : a[0] – b[0]; // return Integer.compare( a[0], b[0] ); } }); And here is an simple way: Arrays.sort(myArr, (a, b) -> a[0] – b[0]);
Sort List
This is No.148 Problem in LeetCode. Here are two approaches as below: Top Down Merge Sort Recursively split the original list into two halves. The split continues until there is only one node in the linked list (Divide phase). To split the list into two halves, we find the middle of the linked list using …
How to construct a BST with a given pre-order array?
Code is below: // build the tree private TreeNode build_tree( String[] node, int min, int max ){ // invalid corner case if( idx >= node.length ){ return null; } TreeNode root = null; // valid value if( Integer.valueOf(node[idx]) > min && Integer.valueOf(node[idx]) < max ){ // build the root root = new TreeNode( Integer.valueOf( node[idx]) …
Continue reading “How to construct a BST with a given pre-order array?”