CareerCup

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);
        	}
        	elements.addAll(curElements);
        }
        
     return depth;
}

}

breath-first

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.

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);
}

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;
}

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;
}

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;
}

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;
}

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;
}

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;
}

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

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)

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)
{

}

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.
Any comments welcome

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;
}

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;

}

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 .

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;
}

#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);
}

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;
 }

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;

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;
}

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--;
}
}

}