Create a binary tree from an array of integers .

Write a function that given an array representation of a binary tree will convert it into a typical tree format.
The following is a visual representation of expected input and output:

Input: [7, 3, 9, 2, 4, 8, 10,11,12,13,14]
Output:
7
/ \
3 9
/\ /\
2 4 8 10

One way to build a tree is that we know that array is like a breadth first traversal . So the series it appears is the same order we need to create tree. Also other property of tree is for a node at index “index” , left child is [2*index+1] and right child is [2*index+2].

public Node createTree(Integer[] array){
        
        if(array == null || array.size == 0)
         return null;
     	Node n = array[0];
     	Queue queue =new Queue();
     	queue.add(n);
        int count = 1;
     	while(count < array.length || !queue.isEmpty()){
     		n.left = new Node(array[count++]);
     		queue.add(n);
                if(count < array.length){
                  n.right = new Node(array[count++])
     		  queue.add(n.right)
               }    	
     	}
     return n;
     }

Program to find whether the binary tree is BST ?

A binary tree is binary search tree (BST) if :

If the left subtree nodes value is less than the given node.
If the right subtree nodes value is greater than the give node
Both the left and right subtrees are BST.


public class BinaryTreeIsBST {

	public boolean IsBST(TreeNode node, int max, int min){

		if(node == null)
			return true;
		if(min < node.value && node.value > max){
			return IsBST(node.left,min,node.value) &&
                         IsBST(node.right,node.value,max);
		}
		return false;
	}
}

Write a program to find whether a binary tree is a balanced ?

As per wikipedia

A balanced binary tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less.

A binary tree can be considered as balanced if

The Left subtree is balanced
The right subtree is balanced
For a node the difference between height of left subtree and right subtree is not more than 1.

One approach to check balance condition for a node is by calculating height of left and right subtree and satisy the 3rd condition,then traverse down the tree to check for each child and keep continuing till you reach the leaf node. If condition is not satisfied for a node return false;

public class IsTreeBalance {


public boolean isBalance(TreeNode root){


if(root == null)

return true;

if (Math.abs(height(root.left)-height(root.right)) >1)

return false;

return isBalance(root.left) && isBalance(root.right);



}

  public int height(TreeNode node){


    if (node == null)

       return 0;
 
    return 1 + Math.max(height(node.left), height(node.right));

  }
}

So far so good. But the problem with this approach is that we visit each node (except root) more than once and hence not the best approach doing top-down check.

Opposite of top-down is bottom-up which is more efficient in this case. We start with leaf node and traverse up the tree. This way a node is visited only once.

public int isBalance1(TreeNode root){

if(root == null)

return 0;

int leftHeight = isBalance1(root.left);

int rightHeight = isBalance1(root.right);

if(Math.abs(leftHeight- rightHeight) > 1)

return -1;

return 1+Math.max(leftHeight, rightHeight);

&nbsp;

}
<pre>

Uninformed Search – BFS and DFS

Breadth first search is a strategy in which root node is expanded first and then all successors are expanded. It means that all the nodes at a given depth are expanded before any other node at the next depth level can be expanded. While expanding the nodes the information of the successors needs to be stored in the memory so that in the next iteration those particular nodes can be expanded.

For the given tree the BFS expansion will be :

1 2 3 4 5 6 7 8 9 10 11 12

BFS guarantees to find a path in a tree/graph except for the following conditions:

The graph or tree is not cyclic i.e it doesn’t have a curve.
A give child node should not have infinite successors. If this happens then the algorithm will be expanding the child node forever.
Breadth-first search is complete. This means that if there is a solution breadth-first search will find it regardless of the kind of graph.

DFS(Dept First Search) always continue to expand the deepest node of a first successor till it reaches a leaf node. DFS needs to store only a single path from the root to a leaf node, along with remaining unexpanded sibling nodes for each node on the path. DFS doesn’t guarantee to find a shortest path , because it may happen that it has found a path by expanding the first child but there is an optimal path for some other child of a same parent.

For the given tree the DFS expansion will be:

1 2 5 9 10 6 3 7 11 12 8

Note: left node is given a priority to expand first.

DFS guarantees to find a path ina tree/graph except for the following conditions:

The graph or tree is not cyclic i.e it doesn’t have a curve.
A give child node should not have infinite successors. If this happens then the algorithm will be expanding the child node forever.

BFS and DFS are called uninformed search which means that it knows only the goal state and start state, to achieve or find the path it simply generates the successors only and doesn’t consider other information like at given time what is the current state, how far is the goal state and what is the heuristic for the goal state.

Advantage of BFS over DFS is :

BFS guarantee’s to give an optimal path for a given tree.
BFS generally proves faster than DFS

Advantage of DFS over BFS is :

The major advantage DFS has that it take less memory for finding a path than BFS.

	BFS	DFS
Time	O(b^(d+1))	O(b^m)
Space	O(b^(d+1))	O(bm)
Optimal	Yes	No
Complete	Yes	No

What is difference between iterator access and index access?

Ans) Index based access allow access of the element directly on the basis of index. The cursor of the datastructure can directly goto the ‘n’ location and get the element. It doesnot traverse through n-1 elements.

In Iterator based access, the cursor has to traverse through each element to get the desired element.So to reach the ‘n’th element it need to traverse through n-1 elements.

Insertion,updation or deletion will be faster for iterator based access if the operations are performed on elements present in between the datastructure.

Insertion,updation or deletion will be faster for index based access if the operations are performed on elements present at last of the datastructure.

Traversal or search in index based datastructure is faster.

ArrayList is index access and LinkedList is iterator access.