Spiral Order Traversal of a Tree [Binary Tree Zigzag Level Order Traversal]

Problem statement:
Write a function to print spiral order traversal of a tree. 
For example.

Input - 
10
J
H
I
A
C
D
F
E
B
G
where 10 is the number of elements in the input array.

Output -
A
BC
FED
GHIJ

How do you create tree data structure ?

Problem statement: How will you create tree in java?

1. /* Class containing left and right child of current
2. node and data value*/
3. class Node
4. {
5. int data;
6. Node left, right;
7. 
   
8. public Node(int data1)
9. {
10. data = data1;
11. left = right = null;
12. }
13. }
14. 
    
15. // A Java program to introduce Binary Tree
16. class BinaryTree
17. {
18. // Root of Binary Tree
19. Node root;
20. 
    
21. // Constructors
22. BinaryTree(int data1)
23. {
24. root = new Node(data1);
25. }
26. 
    
27. BinaryTree()
28. {
29. root = null;
30. }
31. 
    
32. public static void main(String[] args)
33. {
34. BinaryTree tree = new BinaryTree();
35. 
    
36. /*create root*/
37. tree.root = new Node(1);
38. 
    
39. /* following is the tree after above statement
40.  
41.               1
42.             /   \
43.           null  null     */
44. 
    
45. tree.root.left = new Node(2);
46. tree.root.right = new Node(3);
47. 
    
48. /* 2 and 3 become left and right children of 1
49.                1
50.              /   \
51.             2      3
52.           /    \    /  \
53.         null null null null  */
54. 
    
55. 
    
56. tree.root.left.left = new Node(4);
57. tree.root.left.left.right = new Node(9);
58.         /* 4 becomes left child of 2
59.                     1
60.                 /       \
61.                2          3
62.              /   \       /  \
63.             4    null  null  null
64.            /   \
65.           null 9
66.          */
67. System.out.println(tree.root.right.data);
68. }
69. }

Output: 3

How do you check whether given trees are isomorphic to each other or not?

Problem statement: Given two trees how do we check whether the trees are isomorphic or not !!

Two binary trees root1 & root2 are isomorphic if they are the same structure. The values of nodes does not affect whether two trees are isomorphic or not.  

1. int IsIsometric(TreeNode root1, TreeRoot root2){
2. f(root1 == null && root2 == null)
3. return 1;
4. if((root1 == null && root2 != null) || (root1 !=null && root2 == null)) return 0;
5. return (IsIsometric(root1.getLeft(), root2.getLeft()) && IsIsometric(root1.getRight(), root2.getRight()));
6. }

Time complexity: O(n), Space complexity: O(n)

How many different binary trees are possible with n nodes?

Problem statement: what do you say, how many different binary trees are possible with n nodes?

• In general, 

1. if there are n nodes,
2. then there exist 2ⁿ - n different trees

• example - 

1. number of node = 3
2. then different trees = 2³ - 3 = 8 - 3 = 5

Tree Data structure Implementation

1. 
   
2. class Node {
3. 
   
4. int data;
5. Node left;
6. Node right;
7. 
   
8. Node(int data) {
9. this.data = data;
10. 
    
11. }
12. }
13. 
    
14. public class BaseTree {
15. public static void main(String[] args) {
16. Node root=new Node(1);
17. 
    
18. Node a1=new Node(2);
19. Node a2=new Node(3);
20. Node a3=new Node(4);
21. Node a4=new Node(5);
22. Node a5=new Node(6);
23. Node a6=new Node(7);
24. 
    
25. 
    
26. root.left=a1;
27. root.right=a2;
28. 
    
29. a1.left=a3;
30. a1.right=a4;
31. 
    
32. a2.left=a5;
33. a2.right=a6;
34. 
    
35. 
    
36. System.out.println(height(root)-1);
37. //preOrder(root);
38. //inOrder(root);
39. //postOrder(root);
40. //System.out.println(root.left.right.data);
41. //System.out.println(root.data);
42. //System.out.println(root.left.data);
43. //System.out.println(root.left.left.data);
44. //System.out.println(root.left.right.data);
45. //System.out.println(root.right.left.data);
46. //System.out.println(root.right.right.data);
47. }
48. 
    
49. public static void preOrder(Node root){
50. if(root==null){
51. return;
52. }
53. System.out.println(root.data);
54. preOrder(root.left);// root=root.left;root=root.left.left;
55. preOrder(root.right);
56. }
57. public static void inOrder(Node root){
58. if(root==null){
59. return;
60. }
61. preOrder(root.left);
62. System.out.println(root.data);
63. preOrder(root.right);
64. }
65. public static void postOrder(Node root){
66. if(root==null){
67. return;
68. }
69. preOrder(root.left);
70. preOrder(root.right);
71. System.out.println(root.data);
72. }
73. 
    
74. 
    
75. public static int height(Node root){
76. if(root==null){
77. return 0;
78. }
79. else
80.     {
81.         int lDepth = height(root.left);
82.         int rDepth = height(root.right);
83. 
    
84.         if (lDepth > rDepth)
85.             return (lDepth + 1);
86.          else
87.             return (rDepth + 1);
88.     }
89. }

}