Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
no, there is no parent link.
All the nodes are given. When I was working on it, I removed it by mistake.
i/p - B C F E A
o/p - A
Possible Approach
Apply any tree traversal(in , pre ,post) while iterating through all nodes in list. The node whose traversal list is equal to size of input list and also has the largest size is the root else return null(some nodes may be missing in input list).
You can optimize above by maintaining a list/hash of already visited nodes that have parents in previous iterations and not iterating through these.
Approach should be that, first check for nodes whose node->left and node->right is NULL. Then make these node values as NULL, as these are lowest nodes in tree. Go on doing same. If the node count becomes one, then it is the root node.
1. Take the next Tree Node from the list
2. if the Tree Node is not visited before
2.1 flag it as visited (use a Hashtable for this)
2.2 root = Tree Node
2.3 flag all child nodes in the Tree Node sub tree as visited
3. if there are more nodes in the list then go to 1
4. If list has less elements than the Hashtable //Some nodes from the tree were not given in the list
4.1 root = null //if all nodes are not given, return null
5. return root
//C#
static TreeNode GetRoot(List<TreeNode> nodes)
{
if (nodes == null)
{
return null;
}
Hashtable visitedNodes = new Hashtable();
TreeNode root = null;
foreach(TreeNode currentNode in nodes)
{
if (!visitedNodes.Contains(currentNode))
{
//traverse subtree and flag nodes as visited
Traverse(visitedNodes, currentNode);
root = currentNode;
}
}
if (visitedNodes.Keys.Count > nodes.Count)
{
root = null; //some nodes are not given
}
return root;
}
//Traverse tree
static void Traverse(Hashtable visitedNodes, TreeNode currentNode)
{
if (currentNode != null)
{
if (!visitedNodes.Contains(currentNode))//Avoid retraversal of subtrees already traversed
{
visitedNodes.Add(currentNode, null); //used just for searching so value is NULL
Traverse(visitedNodes, currentNode.left);
Traverse(visitedNodes, currentNode.right);
}
}
}
# Given a list of nodes of a tree, return the root. (you are given all nodes of tree)
def return_root_tree(lst):
num_children = {}
for node in lst:
root_helper(node, num_children)
# Now, num_children is filled with information of ( node : # of total children )
root = None
max_children = 0
for node in num_children:
if num_children[node] > max_children:
root, max_children = node, num_children[node]
return root
def root_helper(node, num_children):
if node not in num_children:
num_children[node] = 0
if not node.children:
num_children[node] = 1
return 1
for child in node.children:
num_children[node] += root_helper(child, num_children)
num_children[node] += 1
return num_children[node]
return num_children[node]
# Given a list of nodes of a tree, return the root. (you are given all nodes of tree)
def return_root_tree(lst):
num_children = {}
for node in lst:
root_helper(node, num_children)
# Now, num_children is filled with information of ( node : # of total children )
root = None
max_children = 0
for node in num_children:
if num_children[node] > max_children:
root, max_children = node, num_children[node]
return root
def root_helper(node, num_children):
if node not in num_children:
num_children[node] = 0
if not node.children:
num_children[node] = 1
return 1
for child in node.children:
num_children[node] += root_helper(child, num_children)
num_children[node] += 1
return num_children[node]
return num_children[node]
# Given a list of nodes of a tree, return the root. (you are given all nodes of tree)
def return_root_tree(lst):
num_children = {}
for node in lst:
root_helper(node, num_children)
# Now, num_children is filled with information of ( node : # of total children )
root = None
max_children = 0
for node in num_children:
if num_children[node] > max_children:
root, max_children = node, num_children[node]
return root
def root_helper(node, num_children):
if node not in num_children:
num_children[node] = 0
if not node.children:
num_children[node] = 1
return 1
for child in node.children:
num_children[node] += root_helper(child, num_children)
num_children[node] += 1
return num_children[node]
return num_children[node]
Time: O(n) Space: O(1)
1) Let's take result = 0.
2) Now let's go over all nodes. In each node: result XOR node_index XOR all child indices.
As soon as root index should be only one, and other indices have pairs(self index + smb's child index) in the end result = root_index.
Check that answer is correct!
1. Check if result < total nodes
2. Throw away result index, and iterate with XOR again. Check if result == 0
If not => We have several nodes that are alone, tree is incomplete! => return null
sg
- DarkKnight August 30, 20151) does each node have link to its parent ?
2) what do you mean by "if all nodes of a tree are not given, return null". In you example all the nodes (A-F) are not in the list (FEA). Did you mean if the list contains a node that is not in the tree ?