Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
here is the C# code:
class Dfs<T> where T : IComparable<T>
{
private readonly Node<T> _source;
private readonly Dictionary<T, T> _paths = new Dictionary<T, T>();
private T _max = default(T);
public Dfs(Tree<T> tree)
{
_source = tree.Root;
}
public void Solve()
{
Search(_source);
var stack = new Stack<T>();
stack.Push(_max);
for(var n = _paths[_max]; _source.Value.CompareTo(n)!=0;n=_paths[n])
{
stack.Push(n);
}
stack.Push(_source.Value);
while(stack.Count>0)
{
Console.WriteLine(stack.Pop());
}
}
private void Search(Node<T> node)
{
if(node.Value.CompareTo(_max) > 0)
{
_max = node.Value;
}
if(node.Left!=null)
{
_paths.Add(node.Left.Value, node.Value);
Search(node.Left);
}
if(node.Right!=null)
{
Search(node.Right);
_paths.Add(node.Right.Value, node.Value);
}
}
}
firstly it's not bst, so your comparison "_source.Value.CompareTo(n)!=0" is not valid.
secondly you are using O(n) space which can be reduced to O(lgn)
Recursive solution:
find the index of max value in left and right subtree and return the index of max value among root, left and right.
Once we get the index of max node in the tree, then path will be index/2 recursively..
#define NOT_DEFINED -1000000007
vector<int> tree(n);
int main(){
tree[0]=NOT_DEFINED;
// Input tree vector starting at root node 1
// left child index= 2*node
// right child index= 2*node+1
int val = func(1);
printPath(val);
return 0;
}
void printPath(int node){
if(node !=1)
printPath(node/2);
printf(node);
}
int max_index(int a, int b){
if(tree[a]>tree[b]) return a;
return b;
}
int func(int node){
if(tree[node] == NOT_DEFINED)
return 0;
int left = func(2*node);
int right = func(2*node+1);
return max_index(node,max_index(left,right));
}
void maxpath(struct Node *node,int *arr,int max_arr[],int index,int &max,int &max_index)
{
if(!node)
return;
arr[index++]=node->data;
if(!node->left && !node->right)
{
int temp=0;
for(int i=0;i<index;i++)
temp+=arr[i];
if(temp>max)
{
for(int i=0;i<index;i++)
max_arr[i]=arr[i];
max=temp;
max_index=index-1;
}
}
if(node->left)
maxpath(node->left,arr,max_arr,index,max,max_index);
if(node->right)
maxpath(node->right,arr,max_arr,index,max,max_index);
}
We would find out the location of the node with max value by traversing the tree.After finding it,we would again traverse from root ,and put the entry of the last traversed node in an array ,but each time we enconter the leaf node ,we will put 0 in the array.Along with address ,we also put height of each node.We will update till we reach the max node.After that we need to just traverse the array aand find the height of each node,till we reach the root
it is easy to find max value via recursion,
it is a little tricky to pass the path information. The recursive function returns the max sum of the current tree, and uses a reference to return the path generating the sum at the same time.
#include <vector>
#include <iostream>
using namespace std;
void print( vector<int> v){
vector<int>::iterator it ;
for( it = v.begin(); it != v.end(); ++it )
cout << *it << " " ;
}
struct Node{
Node* left;
Node* right;
int value;
};
int maxPath( Node* n, vector<int> &path ){
if( n != NULL ){
//cout<<n->value<<endl;
vector<int> leftPath;
int leftMax = maxPath( n->left, leftPath );
vector<int> rightPath;
int rightMax = maxPath( n->right, rightPath );
path = leftMax > rightMax ? leftPath : rightPath;
int ret = leftMax > rightMax ? leftMax : rightMax;
path.push_back( n->value );
return ret + n->value;
}
else
return 0;
}
int main(){
Node* root = new Node;
root->value = 1;
root->left = new Node;
root->left->value = 2;
root->right = new Node;
root->right->value = 3;
root->right->left = new Node;
root->right->left->value = 4;
vector<int> path;
cout<<maxPath(root,path)<<endl;
print(path);
}
I was thinking that if we maintain a stack of nodes build by traversing the tree. While building, we follow a specific pattern - we push parent, then parent.left and then parent.right. If any of the parent doesn't have any child, we push zero value in that place.
After constructing such stack, we could easily find out which node has max value. If the max value node is found in odd index, then the path from the root will be the nodes at odd position index till that maximum node. Or otherwise, it will be the even position indexes.
consider the tree to be the directed graph, perform the regular DFS to find the paths between root and all the nodes and find the max value at the same time. Print the path to the max node in the end.
- S.Abakumoff February 12, 2013