Google Interview Question
Country: United States
Interview Type: Phone Interview
1) Blacklist root
2) Traverse all leftmost nodes and blacklist them - O(Log N)
3) Traverse all rightmost nodes and blacklist them - O(Log N)
4) Traverse the tree(any BFS or DFS) and blacklist all leaves - O(N)
Time Complexity - O(N)
Traversing all leftmost nodes and black listing them could fail in the following scenario
1
2 3
4 5 6 7
8 9 10 11 12 13
14 15
Here nodes to be blacklisted : 1 2 4 8 14 15 9 10 11 12 13 7 3
In this case when looked from left, node 8 will be visible from the left side. But traversing node = node.left will not reach 8 as node 4 will not have any left child.
So what we can do is, do a BFS traversal, put a Empty node in the queue at the end of each level, and for each level black list the first node, node without left and right child, and last node in that level.
eg) Queue contents :
<e> empty node
1 <e> 2 3 <e> 4 5 6 7 <e> 8 9 10 11 12 13 <e> 14 15
So if we do dequeue operation on this queue, the conditions to be checked are,
1. if the previous node is <e> blacklist current node
2. If the next node is <e> blacklist current node
3. If both the children are null for the current node, blacklist current node.
Sorry the tree which I put with indentation in the last time got messed up.
The structure is 2,3 children of 1
4,5 -> 3
8,9 -> 5
10,11 -> 6
12,13 -> 7
14,15 -> 9
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);
}
pls explain me the question i couldn't get it....
- ram rs March 26, 2013