prashant2361
BAN USERTo view the nodes from the right side, above procedure can be used but the traversal of nodes will be reversed:
//right first
saveLeftPath(x.r, l+1);
saveLeftPath(x.l, l+1);
Though the question talks about B tree, basic idea should remain the same.
Consider this tree:
For the below case, when viewed from the left side, the nodes are = 2, 3, 7 & 9
2
- -
3 5
-
7
- -
9 10
Idea is that at every level the left most node is visible. Logic to find out the node visible at every left from left most side:
=> Do a inorder traversal of the tree so that left node comes before right node
=> At every level, if there is no node already seen, this node becomes the visible node
Given below is the simple method to find the left most nodes visible at every level
Map<Integer, String> levelMap = new HashMap<Integer,String>();
void saveLeftPath(TreeNode x, int level) {
if (x != null) {
if( ! levelMap.containsKey(l) ) {
levelMap.put(l, x);
}
} else return;
saveLeftPath(x.l, l+1);
saveLeftPath(x.r, l+1);
}
public static boolean compareAnyStr(String s1, String s2) {
return compareStr(s1.toUpperCase(), s2.toUpperCase());
}
public static boolean compareStr(String s1, String s2) {
if(s1.length() == 0 || s2.length() == 0) {
//if both are empty then return true
if(s1.length() == 0 && s2.length() == 0) {
return true;
}
//if s1 is empty and s2 is of length=1 and contains '*' then return true
if(s1.length() == 0 && s2.length() == 1 && s2.charAt(0) == '*') {
return true;
}
return false;
}
char ch2 = s2.charAt(0);
if(ch2 >= 'A' && ch2 <= 'Z') {
char ch1= s1.charAt(0);
return (ch1 == ch2) && compareStr(s1.substring(1), s2.substring(1));
} else {
if(ch2 == '?') {
//two cases: ? matches 0 character, ? matches 1 character of s1
return compareStr(s1, s2.substring(1)) ||
compareStr(s1.substring(1), s2.substring(1));
} else {
//two cases: * matches 0 character, * matches 1 character but we don't remove * from s2
return compareStr(s1, s2.substring(1)) ||
compareStr(s1.substring(1), s2);
}
}
}
public static void main(String[] args) throws CloneNotSupportedException {
System.out.println(compareAnyStr("abc", "abc"));
System.out.println(compareAnyStr("abc", "?bc"));
System.out.println(compareAnyStr("abc", "*d"));
System.out.println(compareAnyStr("abcde", "?bc*e"));
}
We don't have to use a special BST for this case.
Range lookup in normal BST is the order of O(key2-key1). You first search for key1 and then do the successor calls until you reach key key2
"1" is lexicographically less than "10". Please also refer to compareTo doc of String that should make things more clear.
- prashant2361 April 08, 2013So the lexicographically sorted output for the example you have specified should be = 1, 10, 11, 9 , 8 ....