1.Non recursive method to calculate height of the binary tree.
Solution: Level Order Traversal.

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

 

2.Given a sorted array, construct Balanced BST
Solution:

#include<stdio.h>
#include<stdlib.h>
struct TNode
{
  int data;
  struct TNode* left;
  struct TNode* right;
};

struct TNode* newNode(int data);

struct TNode* sortedArrayToBST(int arr[], int start, int end)
{
   if (start > end)
      return NULL;
   int mid = (start + end)/2;
   struct TNode *root = new Node(arr[mid]);
   root->left =  sortedArrayToBST(arr, start, mid-1);
   root->right = sortedArrayToBST(arr, mid+1, end);
   return root;
}

struct TNode* newNode(int data)
{
   struct TNode* node = (struct TNode*)malloc(sizeof(struct TNode));
   node->data = data;
   node->left = NULL;
   node->right = NULL;
   return node;
}

void preOrder(struct TNode* node)
{
   if (node == NULL)
      return;
   printf("%d ", node->data);
   preOrder(node->left);
   preOrder(node->right);
}

int main()
{
   int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25};
   int n = sizeof(arr)/sizeof(arr[0]);
   struct TNode *root = sortedArrayToBST(arr, 0, n-1);
   printf("\n PreOrder Traversal of constructed BST ");
   preOrder(root);
   return 0;
}

 

3.Given two Binary Tree, need to check both are same or not(Without using recursion). Extend the solution for Tree.
Solution: Just do a level order traversal.

public class Solution 
{
   public boolean isSameTree(TreeNode p, TreeNode q) 
   {
      Queue<TreeNode> firstQueue = new LinkedList<TreeNode>();
      Queue<TreeNode> secondQueue = new LinkedList<TreeNode>();
      firstQueue.add(p);
      secondQueue.add(q);
      while(!firstQueue.isEmpty() && !secondQueue.isEmpty())
      {
          TreeNode first = firstQueue.poll();
          TreeNode second = secondQueue.poll();
          if(first == null && second == null)
          {
             continue;
          }
          else
             if(first == null || second == null)
             {
                 return false;
             }
             else
             {
                 if(first.val != second.val)
                 {
                    return false;
                 }
                 firstQueue.add(first.left);
                 firstQueue.add(first.right);
                 secondQueue.add(second.left);
                 secondQueue.add(second.right);
             }

      }
      return true;
   }
}

 

4.How do you verify whether a binary tree is balanced? If the depth difference between a left subtree and right subtree of any node in a binary tree is not greater than 1, it is balanced. For instance, the binary tree in Figure 1 is balanced.
Solution:
Solution 1: Visiting Nodes for Multiple Times
According to the definition of balanced binary trees, this problem can be solved by getting the depth difference between the left and right subtrees of every node. When a node is visited, the function depth is invoked to get the depth of its left and right subtrees. If the depth different is 1 at most for all nodes in a binary tree, it is balanced. This solution can be implemented based on the TreeDepth discussed in the preceding problem, as shown below:

bool IsBalanced_Solution1(BinaryTreeNode* pRoot)
{
if(pRoot == NULL)
  return true;

int left = TreeDepth(pRoot->m_pLeft);
int right = TreeDepth(pRoot->m_pRight);
int diff = left - right;

if(diff > 1 || diff < -1)
   return false;

return IsBalanced_Solution1(pRoot->m_pLeft)&& IsBalanced_Solution1(pRoot->m_pRight);
}

This solution looks concise, but it is inefficient because it visits some nodes for multiple times. Take the binary tree in Figure 1 as an example. When the function TreeDepth takes the node 2 as a parameter, it visits nodes 4, 5, and 7. When it verifies whether the binary tree rooted at node 2 is balanced, it visits nodes 4, 5, and 7 again. Obviously, we could improve performance if nodes are visited only once.

Solution 2: Visiting Every Node Only Once
If a binary tree is scanned with the post-order algorithm, its left and right subtrees are traversed before the root node. If we record the depth of the currently visited node (the depth of a node is the maximum length of paths from the node to its leaf nodes), we can verify whether the subtree rooted at the currently visited node is balanced. If any subtree is unbalanced, the whole tree is unbalanced. This new solution can be implemented as shown in below:

bool IsBalanced_Solution2(BinaryTreeNode* pRoot)
{
int depth = 0;
return IsBalanced(pRoot, &depth);
}

bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth)
{
if(pRoot == NULL)
{
   *pDepth = 0;
    return true;
}

int left, right;

if(IsBalanced(pRoot->m_pLeft, &left) && IsBalanced(pRoot->m_pRight, &right))
{
   int diff = left - right;
   if(diff <= 1 && diff >= -1)
  {
      *pDepth = 1 + (left > right ? left : right);
       return true;
  }
}

return false;
}

After verifying left and right subtrees of a node, the solution verifies the subtree rooted at the current visited node and passes the depth to verify its parent node. When the recursive process returns to the root node finally, the whole binary tree is verified.