http://www.geeksforgeeks.org/find-the-largest-subtree-in-a-tree-that-is-also-a-bst/ Given a Binary Tree, write a function that returns the size of the largest subtree which is also a Binary Search Tree (BST). If the complete Binary Tree is BST, then return the size of whole tree. Examples: Input: 5 / \ 2 4 / \ 1 3 Output: 3 The following subtree is… Read More »
One way to serialize a binary tree is to use pre-oder traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #. _9_ / \ 3 2 / \ / \ 4 1 # 6 / \ / \… Read More »
I wrote finding lca long time ago. Today, I learned this more concise code for finding LCA in Binary Tree. The idea is that if there is no p or q in bottom, return null. Or return p, q or root. public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == p… Read More »
This one is from leetcode. Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target. This is a very interesting problem. The best solution is that we maintain a k size window. We traverse tree in-orderly. Let diffHead = abs(head – target), diffTail… Read More »
https://leetcode.com/problems/range-sum-query-mutable/ Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. The update(i, val) function modifies nums by updating the element at index i to val. Example: Given nums = [1, 3, 5] sumRange(0, 2) -> 9 update(1, 2) sumRange(0, 2) -> 8 This problem… Read More »
Segment tree is a very useful data structure which can give answer for range problem in O(logN) time once we have pre-built the tree. Such as sum, min, max in range [i, j]. Lazy propagation is used to lazily update value in segment tree. We try not to update node value as much as possible. We… Read More »
https://leetcode.com/problems/minimum-height-trees/ For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list… Read More »
Write an Iterator that takes a nested(deep) list and flattens it out. For e.g. Collection A = {1, 2, {3, 4, 5, {6, 7}, {8,9}}, 10} When you call DeepIterator it = new DeepIterator(A) ; while(it.hasNext()){ System.out.println(it.next); } The key part of this problem is that the processed data is Collection type, which is the… Read More »
It’s a long time that I spend to comprehend building suffix tree by ukkonen’s algorithm. Here I summarize some major point of this algorithm. 1. Suffix link. A internal node(t1, t2, t3,…,tn) has a suffix link. It points to another internal node or root which it’s a node for t2, t3, …, tn 2. Phase. When building a… Read More »
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 »