Trees

Trees:

Tree is a non-linear data structure. A tree is a data structure similar to linked list but instead of pointing simply to the next node in a linear fashion, each node points to a number of nodes.

Binary Trees: A tree is called binary tree if each node has two or less children.
Strict Binary Tree: A binary tree is called strict binary tree if each node has exactly two children or no children.
 Full Binary Tree: A binary tree is called full binary tree if each node has exact two children and all leaf nodes are at the same level.
Complete binary tree: A binary tree is complete binary tree is all leaf nodes are the height h or h-1 and also without any missing numbers in the sequence.

types:

• N-ary Tree
• Balanced Tree
• Binary search Tree
• AVL Tree
• Red Black Tree
• 2-3 tree

Problems:
 1. Give an algorithm for finding maximum elements in binary tree.
 2. Give an algorithm for finding the maximum elements in binary tree with out recursion.
 3. Give an algorithm for searching an element in binary tree.
 4. Give an algorithm for searching an element in binary tree without recursion.
 5. Give an algorithm for inserting an element into binary tree.
 6. Give an algorithm for finding the size of the binary tree.
 7. Give an algorithm for finding the size of the binary tree without recursion.
 8. Give an algorithm for printing the level order data in reverse order. For example the tree should be 4,5,6,7,2,3,1.
 9. Give an algorithm for deleting the tree.
10. Give an algorithm for finding the height (of depth) of the binary tree.
11. Give an algorithm for finding the height of the binary tree without recursion.
12. Give an algorithm for finding the deepest node of the binary tree.
13. Give an algorithm for deleting an element from binary tree.
14. Give an algorithm for finding the number of leaves in the binary tree without using recursion.
15. Give an algorithm for finding the number of full nodes in the binary tree with out using recursion.
16. Give an algorithm for finding the number of half nodes (nodes with only one child) in the binary tree without using recursion.
17. Given two binary trees, return if they are structurally identical.
18. Give an algorithm for finding the diameter of the binary tree. The diameter of a tree (sometime called the width) is the number of nodes on the longest path between two leaves in the tree.
19. Give an algorithm for finding the level that has the maximum sum in the binary tree.
20. Given a binary tree, print out all its root to leaf path.
21. Give a algorithm for checking the existence of path with given sum. That means, given sum, check whether there exist a path from root to any of the nodes.
22. Give an algorithm for finding the sum of all elements in binary tree.
23. Give an algorithm for finding the sum of all elements in binary tree without recursion.
24. Give an algorithm for converting a tree to its mirror.
25. Given two trees, give an algorithm for checking whether they are mirror of each other.
26. Give an algorithm for finding LCA (Least Common Ancestor) of two nodes in a binary tree.
27. Give an algorithm for constructing binary tree from given In-order and pre-order traversal.
28. If we have given two traversal sequence, can we construct the binary tree uniquely.
29. Give an algorithm for printing all the ancestors of a node in a binary tree.
30. Give an algorithm for traversing the tree in Zigzag order. For example the output of the tree traversal should be 1324567.
31. Give an algorithm for finding the vertical sum of a binary tree.
32. How many different binary trees are possible with n nodes.
33. Given a tree with special property where leaves are presented with 'L' and internal nodes with 'I'. Also, assume that each node has either 0 or 2 children. Given pre-order traversal of this tree, construct the tree.
34. Given a binary tree with three pointers (left, right and leftSibling), give an algorithm for filling    the nextSubling pointers assuming they are NULL initially.
35. Give another way to solve the above problem.

Generic Trees (N-ary tree)