CareerCup

Here is the efficient version, Time : O(n). Also similar approach as we do regularly find height of a tree In regular tree, we assume when hit null it's a leaf. But, in this case leaf is Circular DLL. So, if my cur node's left's right is pointing to cur node then it's a leaf.

public int height(BinaryTreeNode<Integer> root) {
		if (null == root) {
			return 0;
		}
		if (isLeaf(root)) {
			return 1;
		}
		return 1 + Math.max(height(root.left), height(root.right));
	}

	private boolean isLeaf(BinaryTreeNode<Integer> root) {
		BinaryTreeNode<Integer> left = root.left;
		if (null == left)
			return false;
		return left.right == root;
	}

The basic solution can be achieved by the below steps ::
1) Find atleast one leaf node
2) Loop thru doing binary search all the leaf nodes as they are all in DLL which will return the level of the node.
3) Find the maximum of the return value which will be the height of the tree


Step 1:: In at max O(n)
Step 2:: No of Leaf nodes*binary search --- O(nlogn)
Step 3 :: No of Leaf Nodes

So order of the above operation is O(nlogn) in worst case
Aerage will be O(logn^2)
Best case will be O(n)

Perform BFS traversal and keep track of the level with an int var incrementing it as each level + 1 for each next level until you reach leafs (no children), for each leaf in List of nodes of level check:

if (node-> left != null && node->left->right != null && node->left->right.equals(node)) {
  return level;
}

class Solution {
  
  class Node{ 
    Node right;
    Node left;
    Object value;
  }
    
  public static void main(String[] args) {
  
    new Solution().run();
  }
  
    void run(){
      
    Node a= new Node();
    Node b= new Node(); a.left=b;
    Node c = new Node(); a.right=c;
    
    Node d = new Node(); b.left = d;
    Node e = new Node(); b.right = e;
    Node f = new Node(); c.left = f;
    Node g = new Node(); c.right = g;
    
    d.right = e; e.left = d;
    e.right = f; f.left = e;
    f.right = g; g.left = f;
    g.right = d; d.left = g;
    
    System.out.println( "Tree Height: "+treeHeight( a ));
    
  }
  
   int treeHeight( Node root ){
      
      Map< Node, Integer > valueMap = new  HashMap<>();
      
      Node currentNode = root;
      int depth = 1;
      while ( !valueMap.containsKey( currentNode ) ){
        
        valueMap.put( currentNode, depth );
        depth++;
        currentNode = currentNode.left;
        
      }
      
      return valueMap.get( currentNode );
    }
    
}

Step 1 can be done by tortise heir algorithm. Rest of the steps are evident i guess

FindLeaf()
{
	node *temp1=root;
	node *temp2=root;
	while(temp1!=temp2)
	{
		temp1=movenext(temp1);
		temp2=movenext(temp2);
		temp2=movenext(temp2);
	}

	node *leftnode=temp1;
}

node *movenext(node *temp)
{
	if(temp->left!=NULL)
		temp=temp->left;
	else
		temp=temp->right;
	return temp;
}

Step2 --> Max of Iterate thru DLL and binary search for the height.

public void TreeHeight(node root, int height)
{
    if(root==null)
    {
        return null;
    }

    if(goDown(root,Math.pow(2,height)))
    {
        TreeHeight(root.left,height+1);       
    }else{
        System.out.println("the height of the tree is: "+height);
    }
}

public boolean goDown(node currNode,int circel)
{
    node slow = currNode;
    node fast = currNode;

    for(int i=0;i<=circel;i++)
    {
        slow = slow.left;
        fast = fast.left.left;
    }

    // if this level is leaf level the fast and slow nods
    //should be the same one
    if(slow==fast)
    {
        return false;
    } else{
        return true;
    }
}

public void TreeHeight(node root, int height)
{
    if(root==null)
    {
        return null;
    }

    if(goDown(root,Math.pow(2,height)))
    {
        TreeHeight(root.left,height+1);       
    }else{
        System.out.println("the height of the tree is: "+height);
    }
}

public boolean goDown(node currNode,int circel)
{
    node slow = currNode;
    node fast = currNode;

    for(int i=0;i<=circel;i++)
    {
        slow = slow.left;
        fast = fast.left.left;
    }

    // if this level is leaf level the fast and slow nods
    //should be the same one
    if(slow==fast)
    {
        return false;
    } else{
        return true;
    }
}

public void TreeHeight(node root, int height)
{
    if(root==null)
    {
        return null;
    }

    if(goDown(root,Math.pow(2,height)))
    {
        TreeHeight(root.left,height+1);       
    }else{
        System.out.println("the height of the tree is: "+height);
    }
}

public boolean goDown(node currNode,int circel)
{
    node slow = currNode;
    node fast = currNode;

    for(int i=0;i<=circel;i++)
    {
        slow = slow.left;
        fast = fast.left.left;
    }

    // if this level is leaf level the fast and slow nods
    //should be the same one
    if(slow==fast)
    {
        return false;
    } else{
        return true;
    }

}

The basic idea is walk every left node until it reach the end.

#include <stdio.h>
#include <stdlib.h>

#define null   0

using namespace std;

typedef struct s_node
{
private:
   int      m_val;
   s_node*  m_left_node;
   s_node*  m_right_node;

public:
   s_node(int val)
   {
      m_val       = val;
      m_left_node = null;
      m_right_node= null;
   }

   void add_left_node(s_node* node)
   {
      m_left_node = node;
   }

   void add_right_node(s_node* node)
   {
      m_right_node = node;
   }

   s_node* get_left_node()
   {
      return m_left_node;
   }

   s_node* get_right_node()
   {
      return m_right_node;
   }

   int get_val()
   {
      return m_val;
   }

   ~s_node()
   {
      if(m_left_node)
      {
         m_left_node = null;
      }

      if(m_right_node)
      {
         m_right_node = null;
      }
   }
}SNODE;

int main(int argc, char** argv)
{
   //the following is examples of this test.
   SNODE *root    = new SNODE(1);
   SNODE *two     = new SNODE(2);
   SNODE *three   = new SNODE(3);
   SNODE *four    = new SNODE(4);
   SNODE *five    = new SNODE(5);
   SNODE *six     = new SNODE(6);

   //build relationship
   root->add_left_node(two);
   root->add_right_node(three);
   two->add_left_node(four);
   two->add_right_node(five);
   three->add_left_node(six);
   four->add_left_node(six);
   four->add_right_node(five);
   five->add_right_node(six);
   six->add_right_node(four);

   SNODE* walk = root;
   int height  = 0;

   while(walk)
   {
      walk = walk->get_left_node();
      height++;
   }

   height--;

   printf("height = %d\n", height);

   delete root;
   delete two;
   delete three;
   delete four;
   delete five;
   delete six;
   return 0;
}