Salesforce Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Even though recursive solution should be avoided as much as possible since for large tree they are bound fail with stack overflow, here is the pseudo code for recursive solutions:
dfs_recursive (Node n){
if n==null
return;
end-if
if n has children
for each entry c in n->children
dfs_recursive(c);
end-for
end-if
print n; //post order DFS
}
bfs_pre_recursive {
Q <-- initialize a queue
Node marker <-- initialize a node
Q.enqueue(root);
Q.emqueue(marker);
bfs_recursive(Q, marker);
}
bfs_recursive (Queue Q, Node MARKER) {
while true
Node n=Q.dequeue();
If n is MARKER
break;
end-if
print n
if n has children
for each entry c in n->children
Q.enqueue(c);
end-for
end-if
end-while
if Q is not empty
Q.enque(MARKER);
bfs_recursive(Q, MARKER);
end-if
}
public static void BFS(TNode root){
Queue<TNode> q = new LinkedList<TNode>();
q.add(root);
recursiveBFS(q);
}
public static void recursiveBFS(Queue<TNode> q){
if(q.isEmpty())
return;
TNode t = q.poll();
System.out.println(t.data);
for(Tnode temp : t.childrenList)
q.add(temp);
recursiveBFS(q);
}
class Node{
int data;
Node children; // Linked list of children
}
Node DFS(int data, Node root){
if(root == null)
return(null);
if(root.data == data);
return(root);
Node child = root.children;
while(child != null){
if(child.data == data)
return(child);
Node returnVal = DFS(data, child);
if(returnVal != null)
return(returnVal);
child = child.next();
}
return(null);
}
Node BFS(int data, Node root){
LinkedList<Node> queue = new LinkedList<Node>();
queue.addLast(root);
return(BFSRecursive(data, queue));
}
Node BFSRecursive(data, queue){
Node node = queue.getFirst();
if(node != null)
return(null);
if(node.data == data)
return(Node);
Node child = node.children;
while(child != null){
if(child.data == data)
return(child);
queue.addLast(child);
child = child.next();
}
return(BFSRecursive(data,queue));
}
Not sure why you're using data as input param and checking if a node's value is same as data.
data represents the value we are searching for in the tree. we compare it with the node's data to see if the node contains the data we are looking for and then return if it does.
Thanks CodeSpace for the response.
Unfortunately I've given a vote-down because the algorithm didn't consider a list of children (i.e. Node child = root.children; is incorrect as it should be something like List<Node> children=root.children)
- george.maggessy April 07, 2013