Answers for Binary Tree Questions

26. Find height of a tree with or without recursion.
Int FindHeight ( struct node *root)
{
If ( !root) return 0;
Return ( 1+max (findHeight(root->left),findheight(root->right)));
}

Note: For a tree height and depth is same, but for an individual node its same. Root’s height is 1 while depth is 0.
Reader: Can any one post the algorithm for finding tree height without recursion.

27. Find the levels in tree and no of node at every level.
Use BFS.
Void levelorder( struct binarynode * root)
{
Enque(root);
While ( !emptyQ())
{
Temp = deque(q);
// Process node
If ( temp->left) enque(q,temp->left);
If ( temp->right) enque(q,temp->right);
}
}
Use the BFS and put the NULL after every deque give you a null.

28. No of leaves on tree.
Int countleaves( struct binarynode * root)
{
If ( !root) return 0;
If ( !root->left && !root->right) return 1;
Return ( countleaves(root->left) + countleaves(root->right));
}
Can anyone write the algorithm without recursion.

29. Find the diameter of tree. Longest distance between two same level nodes.
Need state management, can be solved by:
Static : multithreading problem
Global: data hiding problem
Pass as argument or use functor.
Int treeDiameter ( struct binarynode *root, int *pd)
{
Int left, right;
If ( !root) return 0;
Left = treeDiameter(root->left,pd);
right = treeDiameter(root->right,pd);
if ( left + right > *pd) * pd = left+right;
return max (left, right) +1;
}

30. Write pre/in/post order traversal with and without recursion.
Void preorder ( struct binarynode * root )
{
If ( root)
{
Processnode(root); //1
Preorder(root->left);//2
Preorder(root->right);//3
}
}
For preorder (1->2->3), inorder(2->1->3) and postorder ( 2->3->1).

31. Serialization of binary tree. Storing data/object in a file and then retrieving it back.
Sol: Store inorder and preorder traversal in file and retrieve the same and you can always build tree from preorder and inorder.
Int I = 0; int l =0; int r = n-1;
Struct binarynode *temp = new struct binarynode ();

Struct binarynode * buildtree( int in[], int pre[], int l, int r)
{
If ( l > r) return null;
Temp->element = pre[l];
Int p = search (in,l,r,pre[l++]);
Temp->left = buildtree(in,pre,l,p-1);
Temp->right = buildtree(in,pre,p+1,r);
Return temp;
}

32. Find the least common ancestor for any two given nodes from tree.
a) Get an inorder and preorder traversal. Find all element between two given nodes, and search for the first element in preorder
b) Struct binarynode * LCA ( struct binarynode *root, struct binarynode *p, struct binarynode * q)
{
If ( !root) return 0;
If ( root == p || root == q ) return root;
Left = LCA(root->left, p,q);
Right = LCA( root->right,p,q);
If ( left && right ) return root;
Else return( left?left”right);
}

33. Threaded binary tree and link inversion tree.

34. Find whether a given tree is BST or not.
a) Do a inorder traversal, and if elements are sorted then its binary tree.
b) int IsBST( struct BSTnode *root, int min, int max )
{
If ( !root) return 1;
Return ( root->element >min && root->element IsBST(root->left, min,root->element) &&
IsBST(root->right,root->element, max));
}

35. Write code for inorder successor. Link to parent node is available.
Struct BSTnode * inordersuccessor ( struct BSTnode *p )
{
If ( !p->right )
{
If ( p->parent->left == p ) return p->parent;
While ( p->parent->right == p ) p = p->parent;
Return p->parent;
}
Else
{
P = p->parent;
While ( p ->left)
P = p->left;
Return p;
}
}


36. Find the kth smallest element of BST.
a) Int count = 0;
Struct BSTnode *kthsmallest ( struct BSTNode *root, int k )
{
If ( !root) return NULL;
Left = kthSmallest ( root->left, k);
If ( left != NULL ) return left;
If ( ++count == K ) return root;
Return kthsmallest(root->right, k );
}
b) Without global variable : pass as an argument.
c) With augmented binary tree, store size of binary subtree with each node.

37. Convert BST to doubly link list.
Struct node * append ( struct node *first, struct node *last )
{
If ( first == NULL )
{
Last->left = last->right = last;
Return last;
}
Last->right = first;
Last->left = first->left;
First->left->right = last;
First->left = last;
Return first;
}
Void BSTtoDLL ( struct node *root, BSTnode *prev )
{
BSTnode *tmp;
If ( !root ) return;
BSTtoDLL( root->left,prev);
Temp = root->right;
*prev = append (*prev,root);
BSTtoDLL(tmp,prev);
}
Without prev variable
Struct node * BSTtoDLL( BSTNode * root )
{
If ( !root) return NULL;
Left = BSTtoDLL(root->left);
Right = BSTtoDLL(root->right);
Return append(left, right, root );
}

38. Is the given BST is AVL or not?
Int isbalance ( struct BSTnode *root )
{
Int left, right;
If ( !root ) return 0;
Left = isbalanced(root->left);
If ( left == -1 ) return -1;
Right = isbalanced(root->right);
If ( right == -1 ) return -1;
Return ( max(left,right)+1);
}