## Goldman Sachs Interview Question for Software Engineer / Developers

• 1
of 1 vote

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

Using level Order Traversal we can determine the maximum depth of the Tree. The lowest level we can reach is the height of the tree. This involves the use of 2 stacks. For current level all the nodes are pushed on a temporary stack and then at the end of iteration put into Main Stack. We continue till main stack is not empty.

``````import java.util.Iterator;
import java.util.Stack;

class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public int maxDepth(TreeNode root) {
if(root==null)
return 0;

int depth=0;
Stack<TreeNode>elements=new Stack<TreeNode>();
Stack<TreeNode>curElements=new Stack<TreeNode>();
elements.push(root);
TreeNode temp=null;
while(!elements.isEmpty())
{
++depth;;
while(!elements.isEmpty())
{
temp=elements.pop();
if(temp.left!=null)
curElements.push(temp.left);

if(temp.right!=null)
curElements.push(temp.right);
}
}

return depth;
}``````

}

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

breath-first

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

I would use breadth-first on 2 queues. Alternate between the queues until both are empty. 1 queue is unexpanded nodes. 2nd queue is expanded nodes. As long as one queue is not empty, increment your counter. If you use 1 queue, you won't know where each level ends.

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

void doDepth(element& node, unsigned recursLevel, int& depth)
{
if(node==null)
return;

if(recurseLevel > depth)
depth=recurseLevel;

doDepth(node.left, recurseLevel+1,depth);
doDepth(node.right, recurseLevel+1, depth);
}

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

You can also use a stack, which will be more memory efficient. For example:

``````unsigned int
MaxDepth(Node * node)
{
// The "int" in the following pair<> is
// 0 if the branch has not been expanded yet
// 1 if the left child has been expanded
// 2 if both children have been expanded.
stack<pair<Node *, int> > trace;

// Activate the root node.
trace.push(make_pair(node, 0));
unsigned int max_depth = 0;

while (!trace.empty()) {

// Record the max depth.
max_depth = max(max_depth, trace.size());

// Hit leaf? Or are done with this node.
if (trace.top().first->IsLeaf()
||  trace.top().second == 2)
{
trace.pop();
}
// Unexpanded?
else if (trace.top().second == 0) {
trace.top().second = 1; // Update our state.
trace.push(make_pair(trace.top().first->LeftChild(), 0));
}
// One child expanded. Expand other child.
else {
assert(trace.top().second == 1);
trace.top().second = 2; // Update our state.
trace.push(make_pair(trace.top().first->RightChild(), 0));
}
}
return max_depth;
}``````

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

Works well, but unless I'm missing something, you should only push the left/right children if they exist.

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

int doDepth(element& node, unsigned recursLevel, int& depth)
{
if(node==null)
return 1;
else
{

deptleft=1+doDepth(node.left, recurseLevel+1,depth);
deptright=1+doDepth(node.right, recurseLevel+1, depth);

if(deptleft>deptright)
depth=deptleft;
else
depth=deptright;
}

return depth;
}

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

BFS works. Cool idea

int Tree::MaxDepthItr(TNode* node)
{
if(NULL == node)
return 0;

queue<TNode*> qNodes;
qNodes.push(node);
qNodes.push(NULL);

int count = 0;

while( qNodes.size() > 0)
{
TNode* node = (TNode*)qNodes.front();
qNodes.pop();

if( NULL == node)
{
count++;

if(qNodes.size() == 0)
break;

qNodes.push(NULL);
}
else
{
if(node->left)
qNodes.push(node->left);
if(node->right)
qNodes.push(node->right);
}
}
return count;
}

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

I am not sure the logic above for checking NULL will help determine when to increment the count !! It seems weird to me.

What you need to do is maintain a pointer for the Next Lvel at any particular depth. During iteration you check whether the current node is same as Next Level, if they are then increment the depth. Here is the code sample

template <class TYPE>
struct BNode
{
public:
TYPE _data;
BNode *_pLeft;
BNode *_pRight;
BNode(const TYPE &iNum):_data(iNum),_pLeft(NULL),_pRight(NULL)
{
}

BNode();
};

int GetTreeDepth()
{
if( NULL == _pRoot )
{
return 0;
}
queue< BNode<TYPE>* > queueOfNodes;
BNode<TYPE>* pCurrent = _pRoot;
queueOfNodes.push( pCurrent );
BNode<TYPE>* pNextLevel = NULL;
if( NULL != pCurrent->_pLeft ){
pNextLevel = pCurrent->_pLeft;
}
else if( NULL != pCurrent->_pRight ){
pNextLevel = pCurrent->_pRight;
}
else{ // both left & right child are NULL i.e only 1 node i.e root
// exists in the tree
return 0;
}

int depth = 0;
while( 0 != queueOfNodes.size() ){
// Get the next entry from the queue
pCurrent = (BNode<TYPE>*)queueOfNodes.front();
queueOfNodes.pop();
// Check if current node from queue starts a new depth level of the treee
if( pNextLevel == pCurrent ){
pNextLevel = NULL;
depth++;
}
// Insert left child node in the queue
if( NULL != pCurrent->_pLeft ){
queueOfNodes.push( pCurrent->_pLeft );
}
// Insert right child node in the queue
if( NULL != pCurrent->_pRight ){
queueOfNodes.push( pCurrent->_pRight );
}
// Check if next level is to be set or not.
if( NULL == pNextLevel )
{// Next level = NULL means pCurrent happens to be the 1st
// node visited at a particular depth
if( NULL != pCurrent->_pLeft ){
pNextLevel = pCurrent->_pLeft;
}
else if( NULL != pCurrent->_pRight ){
pNextLevel = pCurrent->_pRight;
}
}
}
return depth;
}

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

Wow the formatting sucks !! Trying to paste it again. lets see !!

template <class TYPE>
struct BNode
{
public:
TYPE _data;
BNode *_pLeft;
BNode *_pRight;
BNode(const TYPE &iNum):_data(iNum),_pLeft(NULL),_pRight(NULL)
{
}

BNode();
};

int GetTreeDepth()
{
if( NULL == _pRoot )
{
return 0;
}
queue< BNode<TYPE>* > queueOfNodes;
BNode<TYPE>* pCurrent = _pRoot;
queueOfNodes.push( pCurrent );
BNode<TYPE>* pNextLevel = NULL;
if( NULL != pCurrent->_pLeft )
{
pNextLevel = pCurrent->_pLeft;
}
else if( NULL != pCurrent->_pRight )
{
pNextLevel = pCurrent->_pRight;
}
else
{ // both left & right child are NULL i.e only 1 node i.e
// root exists in the tree
return 0;
}

int depth = 0;
while( 0 != queueOfNodes.size() )
{
// Get the next entry from the queue
pCurrent = (BNode<TYPE>*)queueOfNodes.front();
queueOfNodes.pop();
// Check if current node from queue starts a new
// depth level of the treee
if( pNextLevel == pCurrent )
{
pNextLevel = NULL;
depth++;
}
// Insert left child node in the queue
if( NULL != pCurrent->_pLeft )
{
queueOfNodes.push( pCurrent->_pLeft );
}
// Insert right child node in the queue
if( NULL != pCurrent->_pRight )
{
queueOfNodes.push( pCurrent->_pRight );
}
// Check if next level is to be set or not.
if( NULL == pNextLevel )
{// Next level = NULL means pCurrent happens to be
// the 1st node visited at a particular depth
if( NULL != pCurrent->_pLeft )
{
pNextLevel = pCurrent->_pLeft;
}
else if( NULL != pCurrent->_pRight )
{
pNextLevel = pCurrent->_pRight;
}
}
}
return depth;
}

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

int max_depth(Node n)
{
if (n==null) return 0;
int left = 1 + max_depth(n.left);
int right = 2 + max_depth(n.right);
return left>right?left:right;
}

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

if size is not given, go for BFS.
Else, if n is the size: height of the binary tree is log n (base 2)

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

You are wrongly assuming that the tree is height balanced!
Besides, when we talk abt trees size is usually not known, only pointer to root.

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

Go for BFG and make a variable maxDepth,which is the depth of the tree....
Algo is as follows
1.Use BFS mechanism.
2.while calculating the distance from root to the current node make a check like
if(current_node->left == NULL && current_node->right_node == NULL)

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

Go for BFG and make a variable maxDepth,which is the depth of the tree....
Algo is as follows
1.Use BFS mechanism.
2.while calculating the distance from root to the current node make a check like
if(current_node->left == NULL && current_node->right_node == NULL)
{

}

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

Go for BFG and make a variable maxDepth,which is the depth of the tree....
Algo is as follows
1.Use BFS mechanism.
2.while calculating the distance from root to the current node make a check like
if(current_node->left == NULL && current_node->right_node == NULL)
{
/*This check verify that it's a leaf node*/
depth = depth + 1;/*Calculate the depth*/
if(depth > maxDepth)
{
maxDepth = depth;
}
}
There is no need to use two queue.

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

Iam sure some more optmizations need to be done for this , but the below code will work to produce the height of any given binary tree without using recursion - it uses BFS algorithm .
int height(struct node *p)
{
struct node *a[30];
struct node *b[30];
struct node *c[30];
int j=0,bcount=0,ccount=0;
int max = 0;
a[0] =p;
while(j==0 || bcount>0 || ccount >0)
{

if(bcount > 0)
{
while(bcount >0)
{
p = b[bcount-1];
if(p->left != NULL)
{
c[ccount++] = p->left;
}
if(p->right != NULL)
{
c[ccount++] = p->right;
}
bcount--;
}
max++;
}
else if(ccount > 0)
{
while(ccount >0)
{
p = c[ccount-1];
if(p->left != NULL)
{
b[bcount++] = p->left;
}
if(p->right != NULL)
{
b[bcount++] = p->right;
}
ccount--;
}
max++;
}else
{
p = a[j];
if(p->left != NULL)
{
b[bcount++] = p->left;
}
if(p->right != NULL)
{
b[bcount++] = p->right;
}
j++;
max++;
}// end of else
}

return max;
}

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

LOL @ the fixed size array.

And... thanks for the self-explanatory code. You even added a comment, so kind.

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

using DFS / BFS

struct state
{
Node* tree;
int depth
};

int maxd=INT_MIN;
queue<state> Q;

state start,t,w;
start.tree=root;
start.d=0;

Q.push(start);

while(!Q.empty() )
{
t=Q.top();
Q.pop();

maxd=max(maxd,t.d);

if(t.tree->left)
{
w.tree=t.tree->left;
w.d=t.d+1;

Q.push(w);

}

if(t.tree->right)
{
w.tree=t.tree->right;
w.d=t.d+1;

Q.push(w);

}

}

return max;

}

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

You SIR, are the biggest moron..

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

one more way : any tree traversal algorithm using iteration will help in solving this problem , you have to make sure that you maintain a variable MAX accordingly .

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

Level order traversal could be used also

Method 1:

``````int Height(Tree t) {
int height = -1;
if(t != NULL) {
std::list<Tree> q; //Queue to store tree nodes
q.push_back(t);
q.push_back(NULL); //null is the delimeter to show end  of the level
while(!q.empty()) {
TreeNode *node = q.front();
q.pop_front();
if(node == NULL) {//delimeter encountered, increase height and push NULL if q not empty
height++;
if(!q.empty())
q.push_back(NULL);
}
else {
if(node->left)
q.push_back(node->left);
if(node->right)
q.push_back(node->right);
}
}
}
return height;
}``````

Method 2:

``````int height2(TreeNode *root) {
if (!root) return 0;
queue<TreeNode*> nodesQueue;
int nodesInCurrentLevel = 1;
int nodesInNextLevel = 0;
int nodes = -1;
nodesQueue.push(root);
while (!nodesQueue.empty()) {
TreeNode *currNode = nodesQueue.front();
nodesQueue.pop();
nodesInCurrentLevel--;
if (currNode) {
cout << currNode->data << " ";
nodesQueue.push(currNode->left);
nodesQueue.push(currNode->right);
nodesInNextLevel += 2;
}
if (nodesInCurrentLevel == 0) {
nodes++;
cout<<"\n";
nodesInCurrentLevel = nodesInNextLevel;
nodesInNextLevel = 0;
}
}
return nodes;
}``````

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

#include<iostream>
#include<queue>
using namespace std;
struct node{
int data;
node *left;
node *right;
};
void print_height(node *root)
{
int height=0,sz=0,newsz=0;
queue<node *> Q;
node *temp;
if(root==NULL)
{printf("0\n");return ;}
Q.push(root);
while(!Q.empty())
{
if(sz)
{
height++;
}
for(int i=0;i<sz;i++)
{
temp=Q.front();
if(temp->left)
{
Q.push(temp->left);
newsz++;
}
if(temp->right)
{
Q.push(temp->right);
newsz++;
}
}
sz=newsz;
newsz=0;
}
printf("height:%d\n",height);
}

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

in post-order traversal using stack we can keep track of exiting depth

``````int maxDepthIterative(struct node *root) {
if(root==NULL) return 0;
stack <struct node*> s;
s.push(root);
int depth=0;
struct node *previous=NULL,*current;
while(!s.empty())
{
current=s.top();
if(!previous || previous->left==current || previous->right==current ){
if(current->left)
s.push(current->left);
else if(current->right)
s.push(current->right);
}
else if(current->left==previous)
{
if(current->right)
s.push(current->right);
}
else
s.pop();
previous=current;
if(s.size()>depth)
depth=s.size();
}
return depth;
}``````

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

int findDepth(Node* h, int d)

``````if (h == NULL)
return d;

++d;
int ld = findDepth(h->left, d);
int rd = findDepth(h->right, d);
return (ld > rd) ? ld : rd;``````

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

``````int findDepth(Node* h, int d) {
if (h == NULL)
return d;

++d;
int ld = findDepth(h->left, d);
int rd = findDepth(h->right, d);
return (ld > rd) ? ld : rd;
}``````

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

The recursive solution for the above problem will be as given below:
Implementation:

``````int find_height(struct node *root){
if(root == NULL)
return;
int ldepth = find_height(root->left);
int rdepth = find_height(root->right);
if(ldepth > rdepth)
return ldepth + 1;
return rdepth + 1;``````

Now, the iterative solution of the above problem will be done by using a queue and doing a level order traversal which is shown below:
Implementation:

``````int find_height(struct node *root){
if(root == NULL)
return;
queue<struct node*> q;
int height = 0;
q.push(root);
while(1){
int countnodes = q.size();
if(countnodes == 0)
return height;
height++;
if(countnodes > 0){
struct node *node = q.front();
q.pop();
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
countnodes--;
}
}``````

}

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.

### 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.