This is a practice for tree function. It returns the diameter trail of a tree by traversing each node only one time. The process is similar to finding diameter. During traverse each node, keep track of the trail of from the furthest leaf to node itself. For the following tree, it should return the diameter trail 1,… Read More »
Problem description: Given a Binary Tree and a key ‘k’, find distance of the closest leaf from ‘k’. A / \ B C / \ E F / \ G H / \ / I J K Closest key to ‘H’ is ‘K’, so distance is 1 for ‘H’ Closest key to ‘C’ is ‘B’,… Read More »
In the structure of my PatriciaTree, it has following parameters: char c, indicate the char the node has. HashMap<Character, PatriciaTree> children, indicate the children the node has. String leftString, this a bit difficult to explain. So let me raise an example. If root only has a word “dog”. So the structure would be like: .root…….… Read More »
Given a sequence of an in-order traversal 4,3,1,2,7,5,8, construct the BST. The basic idea: The idea is that a sub-tree can be buildt only if the next value is within the min and max value of its current node.. On thing which needs to be mentioned, is that there is not unique BST for a in-order traversal sequence.… Read More »
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. public class FindLargestBST { public static Tree getTree(){ Tree t50 = new Tree(50); … Read More »
This is the solution to here: link public class BuildSumTree { public static void main(String[] args) { Tree tree = Tree.getSumTree3(); System.out.println(ifSumTree(tree, new MyInteger(0))); } /* * http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/ */ public static boolean ifSumTree(Tree tree, MyInteger sum){ if(tree==null||(tree.left==null&&tree.right==null)){ //return true if tree… Read More »
This is a solution to here: link public class BuildSumTree { public static void main(String[] args) { Tree tree = getSumTree(); tree = convertToSumTree(tree); } /* * http://www.geeksforgeeks.org/convert-a-given-tree-to-sum-tree/ */ public static int convertToSumTree(Tree tree){ if(tree==null){ … Read More »
I made this code, it is because I saw there is a problem in geeksforgeeks: link But it only gets the distance of 2 nodes. I’m thinking how to get the path of the 2 nodes. The idea is inspired by Pavel Fusu’s code. link The process is below: 1. Find the lca node. link 2. Find… Read More »
public static Tree findLca(Tree tree, MyInteger lcaNum, int node1, int node2){ if(tree==null){ return null; } MyInteger lLca = new MyInteger(0); Tree ltree = findLca(tree.left, lLca, node1, node2); if(lLca.i==2){ lcaNum.i=2; return ltree; } MyInteger rLca = new MyInteger(0); Tree rtree = findLca(tree.right, rLca, node1, node2); if(rLca.i==2){ lcaNum.i=2; return rtree; } int selfLca = 0; if(node1==tree.value||node2==tree.value){ selfLca… Read More »
public class PostOrderNonTraverse { public static void main(String[] args){ Tree t17 = new Tree(17); Tree t16 = new Tree(16); Tree t15 = new Tree(15); Tree t14 = new Tree(14); Tree t13 = new Tree(13); Tree t12 = new Tree(12); Tree… Read More »