CareerCup

Height of Binary Tree Iteratively

private static Integer height(BinaryTreeNode root) {
		BinaryTreeNode temp;
		Queue<BinaryTreeNode> q = new LinkedBlockingDeque<BinaryTreeNode>();
		q.add(root);
		q.add(new BinaryTreeNode(-1));
		int level = 0;
		while (!q.isEmpty()) {
			temp = q.poll();
			if (temp.getData() == -1) {
				if (!q.isEmpty())
					q.add(new BinaryTreeNode(-1));
				level++;
			} else {
				if (temp.getLeft() != null)
					q.add(temp.getLeft());
				if (temp.getRight() != null)
					q.add(temp.getRight());
			}
		}

		return level;
	}

Height Recursively

	private static Integer heightRecursively(BinaryTreeNode root) {
		int leftHeight, rightHeight;
		if (root == null)
			return 0;
		else {
			leftHeight = heightRecursively(root.getLeft());
			rightHeight = heightRecursively(root.getRight());
			if (leftHeight > rightHeight)
				return leftHeight + 1;
			else
				return rightHeight + 1;
		}
	}

Height(T) = 1 + max(Height(T->left), Height(T->right))

besides recursion way, traverse the binary tree by breath-first.
use a queque as an auxiliary and an empty tag.
queue.push(root)
queue.push(tag)
height = 0;
while(!queue.empty())
{
Node node = queue.pop();
if (node.isTag())
{
++height;
queue.push(node);
}
else
{
if (node.left != null)
queque.push(node.left);
if (node.right != null)
queue.push(node.right)
}
}

Binary_Tree_height(struct tree * node)
{
if(node==NULL)
return 0;
else
return(Binanry_Tree_height(node->left)+Binary_Tree_height(node->right)+1);
}

int BinaryTreeHeight(struct node * node){
if (node == NULL) return 0;
lheight=BinaryTreeHeight(node->letf);
rheight=BinaryTreeHeight(node->right);
if (lheight>rheight)
return (lheight+1);
else
return (rheight+1);
}}

/*
        Recursive algorithm to find height (or depth) of binary tree
        O(n) time and space complexity.
        Note: Assumes rooted tree with single node is height of 1.
     */
    public static int binaryTreeHeight(BinaryTree.Node<Integer> root)
    {
          int leftHeight, rightHeight = 0;
          if (root == null)
          {
              return 0;
          } else {
              leftHeight = binaryTreeHeight(root.left);
              rightHeight = binaryTreeHeight(root.right);
              //max of the heights of two children + 1
              //instead of using Math.max
              //or could do 1 + max(Height(T->left), Height(T->right))
              if (leftHeight > rightHeight)
              {
                  return (leftHeight + 1);
              } else {
                  return (rightHeight + 1);
              }
          }

    }
    /*
    uses level-order traversal (breadth-first traversal). end of level tag is null pointer.
    Note: Assumes root height starts at 1.
    O(n) time and space complexity
     */
    public static int binaryTreeHeightIterative(BinaryTree.Node<Integer> root)
    {
        int level = 0;
        Queue<BinaryTree.Node<Integer>> queue = new LinkedList<BinaryTree.Node<Integer>>();
        if (root == null)
        {
            return 0;
        }
        queue.add(root);
        //END of first level
        queue.add(null);
        while (!queue.isEmpty())
        {
            root = queue.poll();


            //completion of CURRENT level
            if (root == null)
            {
                //put another marker for next level
                if (!queue.isEmpty())
                {
                    queue.add(null);

                }
                //increase level

                level++;
            } else {
                if (root.left != null)
                {
                   queue.add(root.left);

                }
                if (root.right != null)
                {
                    queue.add(root.right);
                }
            }
        }
        return level;
    }

int height(struct node *p)
{
int l=0,r=0;
if(p->left != NULL)
l = 1 + height(p->left);
if(p->right != NULL)
r = 1 + height(p->right);
if(l>r) return l ;
else return r;
}