Tree Arithmetic

1)If a tree has N nodes, then how many are the edges?

Solution:Every node has a parent except the root.Each edge associates a node with its child.So the number of edges are N-1.

2)Prove that there exists only a single path from each node to the root?
Solution:If there are more than 1 paths from a node to the root,it means there are more than 1 parents for one of the ancestors of the node concerned, which is impossible in a tree.

3)Prove that the depth of a tree is always equal to the height of the tree?

Solution: Height of a tree is the height of the root.Depth of a tree is the depth of the deepest node, which is the number of edges from root to it.This should also be the node which defines the height of the root,otherwise we end up with a contradiction.

4)The structure of a typical tree is to have in each node ,besides it data, a pointer to each of its children.But this might be infeasible if there aren’t fixed number of children at each node.So how do modify this data structure to accommodate variable no of children at each node?


Solution:Well the answer to this is child sibling relationship.


5)What are the maximum and minimum depths of a binary search tree?

Solution:In a binary tree of N nodes,the maximum depth is N-1 when it develops only on 1 side and the minimum is floor(log(N)).


6)How many are the no of null pointers for a binary tree of N nodes?

Solution: Total no of pointer=2*N. And each edge is associated with 1 pointer.
So the no of null pointer is 2*N-(N-1)=N+1 .

7)Distinguish inorder , preorder and postorder traversals properly?
Solution: Inorder traversal:Left subtree is first processed ,followed by root and then by right subtree.

Preorder: root is first processed followed by left and right subtrees.There is no order defined between left and right children.Essentially left and right subtrees are traversed only after the root is traversed.

Postorder:Left and right children are traversed before traversing root.


8)How is a binary tree different from binary search tree?

Solution:In Binary search tree, all the elements in the left subtree are <= root and all the elements in the right subtree are >= root,which is not the case with all the binary trees.

9)Recursive calls have always been employed in the case of trees because of their recursive structural property.But linked lists aren’t that different .But why recursion is not that advisable in the case of lists?(A little theoretical …. Think in terms of limited stack size of your machine)

Solution:The depth of a well built tree of N nodes is log(N).So recursive calls are affordable most of the times as stack overflow is seldom possible.But if recursive calls are employed for lists, then the order of recursive call stack size is N which
is not feasible for large N.

10)What are the complexities of insertion,deletion on a binary search tree?

Solution:Insertion in a well built binary search tree is O(logN) and so is the deletion.This is under assumption that depth of tree is O(logN).


11)Show that the maximum number of nodes in a binary tree of height H is 2^(H+1) -1

Solution:In a binary tree of height H ,with maximum number of nodes,all the levels should be completely filled.At depth d, the number of nodes should be 2^d.
Therefore, the total number of nodes =1+2+4+....+2^H=2^(H+1)-1.