Original problem is from g4g: link. And I solved it by recursion: link But further problem is given by Abdul Rais, which requires to convert sum tree by post-order threaded binary tree. At first glance, I don’t know how does post-order threaded binary tree look like. I’ve only seen in-order threaded binary tree. In order to find… Read More »
Given a tree structure, serialize it, and deserialize it. One of the way to do it, is to store the number of children in the serializing. Take below tree as an example: The serializing result will be: The red ones are the number of children information. And use queue to implement it. Check my code on… Read More »
Problem: Given n strings, check if exist 2 of strings which can group a palindrome. For example, for strings ‘aaa’, ‘aac’, ‘ab’, ‘acblb’, ‘ac’, ‘ddcaa’. ‘aac’ and ‘ddcaa’ can group into palindrome; ‘acblb’ and ‘ac’ can group into palindrome. We can solve this problem using trie and rolling hash queue. For example, below is when first 4… Read More »
This is an application for rolling hash queue. In the picture below, let’s find the palindrome in binary tree. So, the right answer should be 1-2-3-2-1. In order to do that, I recursively visit each node. And I maintain 2 rolling hash queues during recursion. When it goes to a leaf node, check the rolling… Read More »
For example, we have intervals [1,3] [2,7] [3,6] [5,5] [8,9] If we give a number 3, it should return: [1,3] [2,7] [3,6] Solution 1, Linear solution An obvious solution is to iterate all intervals. This takes O(n) time. Solution 2, Range tree. Maintain 2 BST for left and right bound. Find the range for… Read More »
The problem is from g4g. link Problem: Given a sorted array. Write a function that creates a Balanced Binary Search Tree using array elements. Basic idea is to create the tree by the middle position. Then recursively create the left sub tree and right sub tree by left part array and right part array. package… Read More »
According to wikipedia link, order statistic tree mainly offers 2 following functions: Select(i) — find the i’th smallest element stored in the tree Rank(x) – find the rank of element x in the tree, i.e. its index in the sorted list of elements of the tree In order to find the rank/index, it is important to… Read More »
This is a practice for Tree. The idea is to find all results in a certain range in BST. import java.util.ArrayList; import java.util.List; import util.Tree; public class FindRangeInBst { public static void main(String[] args) { Tree bst = Tree.getBst(); List<Tree> result = new ArrayList<Tree>(); findRangeInBst(bst, 11, 16, result); … Read More »
Evolved from segment tree1, this segment tree can find not only the segments, but also individual points. The code is quite similar to segment tree1, please refer here link. Below is my code: package util; public class IntervalTree { SegIntervalNode[] segNodes; public IntervalTree(int left, int right) { int diff = right –… Read More »
Problem description: Given a range [0, n]. Then given some of sections in [0, n], find the total sections in [0, n] For example, given [0,8]. Then given section sets [2, 4], [3, 5], [6, 7]. The result should be [2, 5], [6, 7]. A brute force solution is to go over each section sets, find… Read More »