Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

Since it's a binary tree, return the children and the parent of the given node.

- Anonymous August 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry - ignore this solution. Given distance doesn't have to be 1.

- Anonymous August 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Jin August 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}

- Karthik August 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}

- RK September 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- vikas September 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Leon February 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

represent tree as a graph and use BFS

- gen-y-s August 29, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More