Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
@ashulzunke In case you didn't get the logic, I think the ideas is to to do level order traversal and increment height variable for each new level.
the condition inside while loop should be !q.isEmpty()
means the while loop should be look like this while(!q.isEmpty())
Level Order Traversal.
C++ Version:
int getHeightOfBinaryTree ( NODE* root ) {
if ( !root )
return 0 ;
int level = 0 ;
Queue *Q = CreateQueue() ;
Q->enQueue( root ) ;
Q->enQueue( NULL ) ; //To Mark End of Level
while ( !Q->isEmpty() ) {
NODE * node = Q->deQueue() ;
if ( NULL == node ) {
if ( !Q->isEmpty() )
Q->enQueue( NULL ) ;
level++ ;
}
else {
if ( node->left )
Q->enQueue ( root->left ) ;
if ( node->right )
Q->enQueue ( root->right ) ;
}
}
return level ;
}
O(N) Time and Space Complexity
What about considerations for memory consumption in all cases.
Bfs:
Balanced: n/2
Straight line: 1
Only left child has children: 2
Dfs:
Balanced: 2 ( log n + 1)
Straight line: 1
Only left child has 2 children: n / 2
If the tree structures are more likely to be balanced, then a Dfs approach would be best:
class TreeNode {
int value;
TreeNode left, right;
}
class PartAns{
TreeNode node;
int depth;
PartAns (TreeNode n, int d){
node = n;
depth = d;
}
}
...
public int height (TreeNode root){
if (root==null){
return null;
}
in maxDepth = 0;
Stack <PartAns> unchecked = new Stack <PartAns>();
PartAns a = new PartAns (root, 1);
unchecked.push (a );
int d;
TreeNode n;
while (!unchecked.isEmpty ()){
a = unchecked.pop ():
d = a.depth;
if (d > maxDepth)
maxDepth = d;
n = a.node.right;
if (n != null)
unchecked.push (new PartAns (n, d+1));
n = a.node.left;
if (n != null)
unchecked.push (new PartAns (n, d+1));
}
return maxDepth;
}
/*
* Depth of a tree without recursion
*/
public void depthIter(TreeNode node){
Stack<TreeNode> stack = new Stack<TreeNode>();
int ht=0, max=0;
boolean flag=false;
stack.push(node);
while(!stack.empty()){
flag = false;
node = stack.pop();
if(node.rightChild!=null){
stack.push(node.rightChild);
flag = true;
}
if(node.leftChild!=null){
stack.push(node.rightChild);
flag=true;
}
if(flag){
++ht;
if(ht>max)
max = ht;
}else{
ht--;
}
}
System.out.println("max depth: "+max);
}
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
int h = 0;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.l;
}
h = Math.max(h, stack.size() - 1);
current = stack.pop();
if (current != null) {
if (current.r != null) {
stack.push(null);
current = current.r;
} else {
current = null;
}
}
}
int maxDepthBTNonrecursive(BinaryNode1* ai_bn)
{
typedef std::pair<BinaryNode1*, int> DepthStackValue;
typedef std::stack<DepthStackValue> DepthStack;
DepthStack stack;
int maxHeight = 0;
stack.push(std::make_pair(ai_bn, 1));
while (!stack.empty())
{
DepthStackValue ai_bn = stack.top();
stack.pop();
if (ai_bn.second > maxHeight)
maxHeight = ai_bn.second;
if (ai_bn.first->right != nullptr)
stack.push(std::make_pair(ai_bn.first->right, ai_bn.second + 1));
if (ai_bn.first->left != nullptr)
stack.push(std::make_pair(ai_bn.first->left, ai_bn.second + 1));
}
return maxHeight;
}
- Nikesh Joshi September 27, 2014