Interview Question
Country: United States
If distance is 1 this will be true but how about greater than 1? it also says:
"another example is F(root.7,2) will the return nodes 12,4"
It seems to me that this should be a graph problem rather than a tree problem. A tree is also a graph so maybe we should build a graph from the tree, then use dfs to find target(7) first, than use bfs to find nodes in the given distance(1 or 2 in the example)
In the structure of the node representation maintain "distance_from_the_root" field. Make a first pass through the tree and calculate this distance.
In the 2nd pass we only need to print the descendants of the given node (which is easy) and the ascendants at the given distance. To calculate the ascendants
if (nodes->dist_from_root > given_dist) {
traverse (dist_from_root - given_dist) from the root in the direction of the node
} else {
traverse (dist_from_root - given_dist) in the opposite direction
}
You can use DFS/BFS to get the given node's level and then make two more calls to a function which returns a list from above and below the node's level. The main function is F()
void getNodes(TreeNode* root, vector<int>& list, int reqLevel, int curLevel) {
if(! root) return;
if(reqLevel == curLevel)
list.push_back(root->data);
getNodes(root->left,list,reqLevel,curLevel+1);
getNodes(root->right,list,reqLevel,curLevel+1);
}
int getNodeLevel(TreeNode* root, int key, int curLevel) {
if(!root) return -1;
if(root->data == key)
return curLevel;
int left = getNodeLevel(root->left,key,curLevel+1);
int right = getNodeLevel(root->right,key,curLevel+1);
return max(left,right);
}
void F(vector<int> list, TreeNode* root,int key, int dist) {
if(!root) return;
int nodeLevel = getNodeLevel(root,key,0);
if(nodeLevel == -1) return;
getNodes(root,list,nodeLevel-dist,0);
getNodes(root,list,nodeLevel+dist,0);
}
1. Maintain another array, represent this as graph . Apply dijkstra and get it done :)
2. Get distance from root to all nodes
-> distance from root to sourceNode is 's' and given distance is 'd'
1. d>s
->return d-s distant node from other branch.
->return d+s distant node from same branch
2.d<s
->return s-d distance node from same branch
->return d+s distance node from same branch
PostOrder(node, height, hashmap):
if node ==None:
return
BFS( node.left, height +1, hashmap )
BFS( node.right, height +1, hashmap )
hashmap [node.value] = height
hashmap = {}
PostOrder(root, 0 , hashmap) O(|V| + |E|)
target_height = hashmap[target_node]
target_distance
for i in hashmap.keys():
if i != target_node.value and abs( hashmap[i] - hashmap[target_node ]:
print target_node.value
Since it's a binary tree, return the children and the parent of the given node.
- Anonymous August 29, 2014