abhaybhu10 · February 19, 2016 13:22 · Oct 13, 2013 · Oct 11, 2013
diff --git a/TreeToDLLC.cpp b/TreeToDLLC.cpp
@@ -1,4 +1,3 @@
-
 //Circular DLL
 #include"Tree.h"
 Node *head=NULL,*prev=NULL;

diff --git a/WordBreakRec.cpp b/WordBreakRec.cpp
@@ -0,0 +1,46 @@
+#include<iostream>
+using namespace std;
+#include<stdio.h>
+#include<vector>
+#include<string.h>
+bool dictionaryContains(string word)
+{
+    string dictionary[] = {"mobile","samsung","sam","sung","man","mango",
+                           "icecream","and","go","i","like","ice","cream"};
+    int size = sizeof(dictionary)/sizeof(dictionary[0]);
+    for (int i = 0; i < size; i++)
+        if (dictionary[i].compare(word) == 0)
+           return true;
+    return false;
+}
+void WordBreak(string str,string ans)
+{
+        int n=str.size();
+        if(n==0)
+        {
+                cout<<ans<<endl;
+                return ; 
+         }
+        for(int i=0;i<n;i++)
+        {
+                string prefix=str.substr(0,i+1);
+                if(dictionaryContains(prefix))
+                        WordBreak(str.substr(i+1,n-i-1),ans+prefix+" ");                
+
+        }
+//        return false;
+}
+void wordBreak(string str)
+{
+         WordBreak(str,"");
+}
+int main()
+{
+      // wordBreak("ilikesamsung");
+       //wordBreak("iiiiiiii");
+       //wordBreak("");
+       //wordBreak("ilikelikeimangoiii");
+        //wordBreak("samsungandmango");
+        wordBreak("ilikesamsungandmango");
+        return 0;
+}
diff --git a/WordbreakDP.cpp b/WordbreakDP.cpp
@@ -0,0 +1,63 @@
+#include<iostream>
+using namespace std;
+#include<stdio.h>
+#include<vector>
+#include<string.h>
+bool dictionaryContains(string word)
+{
+    string dictionary[] = {"mobile","samsung","sam","sung","man","mango",
+                           "icecream","and","go","i","like","ice","cream"};
+    int size = sizeof(dictionary)/sizeof(dictionary[0]);
+    for (int i = 0; i < size; i++)
+        if (dictionary[i].compare(word) == 0)
+           return true;
+    return false;
+}
+void print(vector<vector<int> > v,string str,int position,int n,string ans)
+{
+        if(position==0)
+         {
+                cout<<ans<<endl;
+                return ;
+         }
+        for(int i=0;i<v[position].size();i++)
+        {
+                // ans= ans=ans+" "+ str.substr(v[position][i],position-v[position][i])+ " ";
+                  print(v,str,v[position][i],n, ans+(str.substr(v[position][i],position-v[position][i])+" "));
+
+        }
+
+}
+bool wordBreak(string str)
+{
+        bool dp[100]={true};
+        vector<vector<int> > pos(100);
+        int n=str.size();
+        for(int i=1;i<=n;i++)
+        {
+               if(dp[i-1])
+               {
+                        for(int j=i;j<=n;j++)
+                        {
+                                if(dictionaryContains(str.substr(i-1,j-i+1)))
+                                 {
+                                        dp[j]=true;
+                                        pos[j].push_back(i-1);//for printing
+                                 }
+                        }
+                }
+        }
+        string ans="";
+        print(pos,str,n,n,ans);
+        return dp[n];
+}
+int main()
+{
+      // wordBreak("ilikesamsung")? cout <<"Yes\n": cout << "No\n";
+     //   wordBreak("iiiiiiii")? cout <<"Yes\n": cout << "No\n";
+        //wordBreak("")? cout <<"Yes\n": cout << "No\n";
+       //wordBreak("ilikelikeimangoiii")? cout <<"Yes\n": cout << "No\n";
+        wordBreak("samsungandmango")? cout <<"Yes\n": cout << "No\n";
+        // wordBreak("samsungandmangok")? cout <<"Yes\n": cout << "No\n";
+        return 0;
+}
diff --git a/AddGreater.cpp b/AddGreater.cpp
@@ -0,0 +1,19 @@
+#include"Tree.h"
+void AddGreater(Node*& root, int &sum)
+{
+        if(!root)
+        return;
+        AddGreater(root->right,sum);
+        sum+=root->data;
+        root->data=sum;
+        AddGreater(root->left,sum);
+}
+int main()
+{
+        Node *root=BuildTree();
+        int sum=0;
+        Node *temp=root;
+        AddGreater(temp,sum);
+        InOrder(root);
+        return 0;
+}
diff --git a/AllPath.cpp b/AllPath.cpp
@@ -0,0 +1,32 @@
+//print all root to leaf path
+#include"Tree.h"
+
+void PrintArray(int *a,int len)
+{
+        for(int i=0;i<len;i++)
+        printf("%d ",a[i]);
+        printf("\n");
+}
+
+void PrintAllPath(Node * root,int a[],int len)
+{
+        if(!root)
+                return;
+         a[len]=root->data;
+         len++;
+         if(root->left)
+                PrintAllPath(root->left,a,len);
+         if(root->right)
+                PrintAllPath(root->right,a,len);
+         if(!root->left && !root->right)
+               PrintArray(a,len);
+}
+
+
+
+int main()
+{
+        int a[50]={0};
+        Node *root=BuildTree();
+        PrintAllPath(root,a,0);
+}
diff --git a/BstToDLL.cpp b/BstToDLL.cpp
@@ -0,0 +1,34 @@
+//convert bst to dll inplace
+#include"Tree.h"
+#include<stdio.h>
+Node *Head=NULL;
+void BSTtoDLL(Node  *root,Node *&pre)
+{
+        if(!root)
+                return ;
+        BSTtoDLL(root->left,pre);
+        if(pre)
+        {
+                pre->right=root;
+                root->left=pre;
+        }
+        pre=root;
+        if(!Head)
+                Head=root;
+        BSTtoDLL(root->right,pre);
+}
+void PrintDLL(Node *root)
+{
+        if(!root)
+                return;
+        printf("%d ",root->data);
+        PrintDLL(root->right);
+}
+int main()
+{
+        Node *root=BuildTree();
+        Node *curr=NULL;
+        BSTtoDLL(root,curr);
+        PrintDLL(Head);
+        return 0;
+}
diff --git a/CheckBst.cpp b/CheckBst.cpp
@@ -0,0 +1,23 @@
+#include<stdio.h>
+#include"Tree.h"
+bool IsBST(Node *root,int min,int max)
+{
+        if(!root)
+                return true;
+        if(root->data >=min && root->data <=max)
+        {
+                 return (IsBST(root->left,min,root->data) && IsBST(root->right,root->data,max));
+        }
+
+        return false;
+}
+int main()
+{
+        Node *root=BuildTree();
+        if(IsBST(root,-99,999))
+        printf("BST\n");
+        else printf("Not BST\n");
+        Inorder(root);
+        return 0;
+
+}
diff --git a/CountLevelNode.cpp b/CountLevelNode.cpp
@@ -0,0 +1,20 @@
+//count node at each level
+#include"Tree.h"
+void CountLevelNode(Node *root,int a[],int level)
+{
+        if(!root)
+                return ;
+        a[level]++;
+        CountLevelNode(root->left,a,level+1);
+        CountLevelNode(root->right,a,level+1);
+}
+int main()
+{
+        Node *root=BuildTree();
+        int a[10]={0};
+        int h=Height(root);
+        CountLevelNode(root,a,0);
+        for(int i=0;i<h;i++)
+        printf("%d \n",a[i]);
+        return 0;
+}
diff --git a/DeleteLeave.cpp b/DeleteLeave.cpp
@@ -0,0 +1,25 @@
+//Delete all leaf node
+#include"Tree.h"
+bool DeleteLeaves(Node *&root)
+{
+        if(!root)
+        return true;
+        if(!root->left && !root->right)
+        {
+                return true;
+        }
+        if(DeleteLeaves(root->left))
+            root->left=NULL;
+        if(DeleteLeaves(root->right))
+                root->right=NULL;
+         return false;
+}
+int main()
+{
+        Node *root=BuildTree();
+        Preorder(root);
+        DeleteLeaves(root);
+        cout<<endl;
+        Preorder(root);
+        return 0;
+}
diff --git a/Height.cpp b/Height.cpp
@@ -0,0 +1,12 @@
+#include"Tree.h"
+int Height(Node *root)
+{
+        if(!root)
+                return 0;
+        return max(Height(root->left),Height(root->right))+1;
+}
+int main()
+{
+        Node *root=BuildTree();
+        printf("%d ",Height(root));
+}
diff --git a/InOrderSuccessor.cpp b/InOrderSuccessor.cpp
@@ -0,0 +1,34 @@
+#include"Tree.h"
+Node * InSuccessor(Node *root,Node *target)
+{
+        if(!root || !target)
+                return NULL;
+         Node *pre=NULL;
+        if(target->right)
+        {
+                pre=target->right;
+                while(pre->left)
+                pre=pre->left;
+        }
+        else
+        {
+                while(root!=target)
+                {
+                        if(root->data > target->data)
+                        {
+                               pre=root;
+                               root=root->left;
+                        }
+                        else root=root->right;
+                }
+        }
+        return pre;
+}
+int main()
+{
+        Node *root=BuildTree();
+        Node *target=root->left->right;
+        Node *temp=InSuccessor(root,target);
+        printf("%d %d\n",target->data,temp->data);
+        InOrder(root);
+}
diff --git a/LCA.cpp b/LCA.cpp
@@ -0,0 +1,19 @@
+#include"Tree.h"
+Node* LCA(Node *root,int a,int b)
+{
+        if(!root)
+                return NULL;
+         if(root->data==a || root->data==b)
+                return root;
+         Node *l=LCA(root->left,a,b);
+         Node *r=LCA(root->right,a,b);
+         if(l&&r)
+                return root;
+          return l?l:r;
+}
+int main()
+{
+        Node *root=BuildTree();
+        printf("LCA=%d\n",LCA(root,11,28)->data);
+
+}
diff --git a/MirrorBT.cpp b/MirrorBT.cpp
@@ -0,0 +1,31 @@
+#include"Tree.h"
+//Creates another Tree
+Node* Mirror(Node *root)
+{
+        if(!root)
+                return NULL;
+        Node *temp=new Node(root->data);
+        temp->left=Mirror(root->right);
+        temp->right=Mirror(root->left);
+        return temp;
+}
+//Inplace i.e same tree is mirrored
+void MirrorInplace(Node *&root)
+{
+        if(!root)
+        return;
+        MirrorInplace(root->left);
+        MirrorInplace(root->right);
+        swap(root->left,root->right);
+}
+int main()
+{
+        Node *root=BuildTree();
+       Node *m= Mirror(root);
+       Preorder(root);
+       printf("\n");
+       Preorder(m);
+       printf("\n");
+       MirrorInplace(root);
+       Preorder(root);
+}
diff --git a/PostOrder.cpp b/PostOrder.cpp
@@ -0,0 +1,43 @@
+//Leet
+#include"Tree.h"
+#include<stack>
+void PostOrder(Node *root)
+{
+        if(!root)
+                return;
+        stack<Node * > s;
+        s.push(root);
+        Node *pre=NULL;
+        while(!s.empty())
+        {
+                Node *curr=s.top();
+                if(!pre || pre->left==curr || pre->right==curr)
+                {
+                        if(curr->left)
+                        s.push(curr->left);
+                        else if(curr->right)
+                         s.push(curr->right);
+                }
+                else 
+                {
+
+                        if(curr->right && curr->left==pre)
+                                 s.push(curr->right);
+                        else
+                        {
+                                s.pop();
+                                printf("%d ",curr->data);
+                        }
+
+                }
+                pre=curr;
+        }
+}
+int main()
+{
+        Node *root=BuildTree();
+        PostOrder(root);
+        printf("\n");
+        Postorder(root);
+        return 0;
+}
diff --git a/PostOrder2.cpp b/PostOrder2.cpp
@@ -0,0 +1,34 @@
+//Post Order Traversal using two stack(Leet)
+ #include"Tree.h"
+ #include<stack>
+ void PostOrder(Node *root)
+ {
+        if(!root)
+                return;
+        stack<Node * > s1,s2;
+        s1.push(root);
+        while(!s1.empty())
+        {
+                Node *curr=s1.top();
+                s1.pop();
+                s2.push(curr);
+                if(curr->left)
+                        s1.push(curr->left);
+                 if(curr->right)
+                        s1.push(curr->right);
+        }
+        while(!s2.empty())
+        {
+                printf("%d ",s2.top()->data);
+                s2.pop();
+        }
+ }
+ int main()
+ {
+        Node *root=BuildTree();
+        PostOrder(root);
+        printf("\n");
+        Postorder(root);
+        return 0;
+ }
+
diff --git a/PreINtoBST.cpp b/PreINtoBST.cpp
@@ -0,0 +1,37 @@
+#include"Tree.h"
+int findInd(int a[],int start,int end,int data)
+{
+        while(start<=end)
+        {
+                if(a[start]==data)
+                        return start;
+                start++;
+        }
+}
+Node *Func(int lvl[],int in[],int start,int end)
+{
+        if(end<start)
+                return NULL; 
+
+        static int k=0;
+        Node *root=new Node(lvl[k++]);
+        if(start==end)
+         return root;
+        int i=findInd(in,start,end,root->data);
+        root->left=Func(lvl,in,start,i-1);
+        root->right=Func(lvl,in,i+1,end);
+        return root;
+}
+int main()
+{
+        int in[20],lvl[20];
+        int n;
+        scanf("%d",&n);
+        for(int i=0;i<n;i++)
+        scanf("%d",&lvl[i]);
+        for(int i=0;i<n;i++)
+        scanf("%d",&in[i]);
+        Node *root=Func(lvl,in,0,n-1);
+        InOrder(root);
+        return 0;
+}
diff --git a/PreOrder.cpp b/PreOrder.cpp
@@ -0,0 +1,25 @@
+#include"Tree.h"
+#include<stack>
+void Preorder(Node *root)
+{
+        if(!root)
+                return;
+        stack<Node *> s;
+        s.push(root);
+        while(!s.empty())
+        {
+                Node *cur=s.top();
+                s.pop();
+                printf("%d ",cur->data);
+                if(cur->right)
+                       s.push(cur->right);
+                if(cur->left)
+                        s.push(cur->left);
+        }
+}
+int main()
+{
+
+        Node *root=BuildTree();
+        Preorder(root);
+}
diff --git a/PrintAncestor.cpp b/PrintAncestor.cpp
@@ -0,0 +1,21 @@
+//Print All ancestor of a given node
+#include"Tree.h"
+bool PrintAncesters(Node *root,int key)
+{
+        if(!root)
+                return false;
+        if(root->data==key)
+                return true;
+       if(PrintAncesters(root->left,key) || PrintAncesters(root->right,key))
+        {
+                printf("%d ",root->data);
+                return true;
+        }
+      return false;
+}
+int main()
+{
+        Node *root=BuildTree();
+        PrintAncesters(root,11);
+        return 0;
+}
diff --git a/PrintRange.cpp b/PrintRange.cpp
@@ -0,0 +1,24 @@
+//Printf all node in a given range in BST
+#include"Tree.h"
+void printRange(Node *root,int l,int h)
+{
+        if(!root)
+                return;
+        if(root->data < l)
+                printRange(root->right,l,h);
+        else if(root->data>h)
+                printRange(root->left,l,h);
+        else 
+        {
+                printf("%d ",root->data);
+                printRange(root->left,l,h);
+                printRange(root->right,l,h);
+        }
+}
+int main()
+{
+        Node * root=BuildTree();
+        InOrder(root);
+        printRange(root,25,76);
+
+}
diff --git a/PrintfAllPathSUmGreaterK.cpp b/PrintfAllPathSUmGreaterK.cpp
@@ -0,0 +1,25 @@
+#include"Tree.h"
+void printPath(int a[],int n)
+{
+        for(int i=0;i<=n;i++)
+        printf("%d ",a[i]);
+        printf("\n");
+}
+void PrintAllPath(Node *root,int sum,int pathlen,int path[])
+{
+        if(!root)
+                return ;
+         path[pathlen]=root->data;
+         sum=sum-root->data;
+         if(sum<=0 && !root->left && !root->right)
+                  printPath(path,pathlen);
+         PrintAllPath(root->left,sum ,pathlen+1,path);
+         PrintAllPath(root->right , sum,pathlen+1,path);      
+}
+int main()
+{
+        Node *root=BuildTree();
+        int a[100];
+        PrintAllPath(root,101,0,a);
+        return 0;
+}
diff --git a/RemovePathSumGreaterK.cpp b/RemovePathSumGreaterK.cpp
@@ -0,0 +1,26 @@
+//Remove all nodes which don’t lie in any path with sum>= k
+#include"Tree.h"
+bool RemoveNode(Node *&root,int sum)
+{
+        if(sum<=0)
+                return true;
+        if(!root)
+                return false;
+        bool l=RemoveNode(root->left,sum - root->data);
+        bool r=RemoveNode(root->right,sum - root->data);
+        if(!l)
+             root->left=NULL;
+         if(!right)
+                root->right=NULL;
+         if(!l && !r)
+                delete(root);
+         return (l||r);   
+}
+int main()
+{
+        Node *root=BuildTree();
+        PreOrder(root);
+        RemoveNode(root,105);
+        PreOrder(root);
+        return 0;
+}
diff --git a/STructuralIdentical.cpp b/STructuralIdentical.cpp
@@ -0,0 +1,19 @@
+#include"Tree.h"
+bool isIdentical(Node *root1,Node *root2)
+{
+        if(!root1 && !root2)
+                return true;
+         if(!root1 || !root2)
+                return false;
+         return (isIdentical(root1->left,root2->left) && isIdentical(root1->right,root2->right));
+}
+int main()
+{
+      Node *root1=BuildTree();
+      Node *root2=BuildTree();
+      root2->right->left=NULL;
+      InOrder(root1);
+      InOrder(root2);
+      printf("%d\n",isIdentical(root1,root2));
+      return 0;  
+}
diff --git a/SameBst.cpp b/SameBst.cpp
@@ -0,0 +1,42 @@
+//Check for Identical BSTs without building the trees
+//Given two arrays which represent a sequence of keys. Imagine we make a Binary Search Tree (BST) from each array. We need to //tell whether two BSTs will be identical or not without actually constructing the tree.
+#include<stdio.h>
+#include<iostream>
+#include<climits>
+#define size 100
+using namespace std;
+bool checkSameBst(int a[],int b[],int n,int i1,int i2,int min,int max)
+{
+        int i=i1,j=i2;
+        for(;i<n;i++) 
+                if(a[i]<max && a[i]>min)
+                break;
+        for(;j<n;j++)
+                if(b[j]<max && b[j]>min)
+                        break;
+        if(i==n && j==n)
+                return true;
+        if(j==n ^ i==n || a[i]!=b[j])
+                return false;
+         return checkSameBst(a,b,n,i+1,j+1,min,a[i]) && checkSameBst(a,b,n,i+1,j+1,a[i],max); 
+}
+
+void input(int p[],int n)
+{
+        for(int i=0;i<n;i++)
+        scanf("%d",&p[i]);
+}
+int main()
+{
+        int a[size],b[size];
+        int n;
+        scanf("%d",&n);
+        input(a,n);
+        input(b,n);
+        bool k=checkSameBst(a,b,n,0,0,INT_MIN,INT_MAX);
+        if(k)
+        printf("Same Bst\n");
+        else printf("Not same\n");
+        return 0;
+
+}
diff --git a/Tree.h b/Tree.h
@@ -0,0 +1,74 @@
+#include<stdio.h>
+#include<iostream>
+using namespace std;
+struct Node
+{
+       int data;
+       struct Node* left;
+       struct Node* right;
+       Node(int x)       
+       {
+             left=NULL;
+             right=NULL;
+             data =x;
+        }
+
+};
+Node* BuildTree(void)
+{
+
+        Node *root=new Node(69);
+        root->left=new Node(20);
+        root->right=new Node(78);
+        root->left->left=new Node(11);
+        root->left->right=new Node(25);
+        root->left->right->right=new Node(28);
+        root->right->left=new Node(76);
+        return root;
+
+}
+void Preorder(Node *root)
+{
+        if(!root)
+                return;
+        printf("%d ",root->data);
+        Preorder(root->left);
+        Preorder(root->right);
+}
+void PreOrder(Node *root)
+{
+        Preorder(root);
+        cout<<endl;
+}
+void Postorder(Node *root)
+{
+        if(!root)
+                return;
+        Postorder(root->left);
+        Postorder(root->right);
+        printf("%d ",root->data);
+}
+void PostOrder(Node *root)
+{
+        Postorder(root);
+        cout<<endl;
+}
+void Inorder(Node * root)
+{
+        if(!root)
+                return;
+        Inorder(root->left);
+        printf("%d ",root->data);
+        Inorder(root->right);
+}
+void InOrder(Node *root)
+{
+        Inorder(root);
+        cout<<endl;
+}
+ int Height(Node *root)
+{
+        if(!root)
+                return 0;
+        return max(Height(root->left),Height(root->right))+1;
+}       
diff --git a/TreeToDLLC.cpp b/TreeToDLLC.cpp
@@ -0,0 +1,44 @@
+
+//Circular DLL
+#include"Tree.h"
+Node *head=NULL,*prev=NULL;
+void ConvertToDll(Node *root)
+{
+        if(!root)
+        return;
+        ConvertToDll(root->left);
+         if(!head)
+        {
+                head=root;
+                prev=root;
+                return;
+        }
+          Node *temp=root->right;
+                root->left=prev;
+                prev->right=root;
+                prev=root;
+                root->right=head;
+
+        ConvertToDll(temp);
+
+}
+void print()
+{
+        Node *temp=head;
+        if(!head)
+        return;
+        do
+        {
+                printf("%d ",temp->data);
+                temp=temp->right;
+        }while(temp!=head);
+}
+int main()
+{
+    Node *root=BuildTree();
+    Inorder(root);
+    cout<<endl;
+   ConvertToDll(root);
+   print();
+    return 0;    
+}
diff --git a/TwoNodeSum.cpp b/TwoNodeSum.cpp
@@ -0,0 +1,61 @@
+//find two node whose sum equal K
+#include"Tree.h"
+#include<stack>
+void findSum(Node* root,int key)
+{
+        int val1=0,val2=1;
+        Node *curr1,*curr2,*pre1=NULL,*pre2=NULL;
+        stack<Node *> s1,s2;
+        if(!root)
+                return;
+        s1.push(root);
+        s2.push(root);
+        do
+        {
+                curr1=s1.top();
+                curr2=s2.top();
+                if(curr1->left && (!pre1 || pre1->left==curr1))
+                 {
+                        pre1=curr1;
+                        s1.push(curr1->left);
+                 }
+                else if(curr2->right && (!pre2 || pre2->right==curr2))
+                 {
+                        pre2=curr2;
+                        s2.push(curr2->right);
+                 }
+                else
+                {
+                        val1=curr1->data;
+                        val2=curr2->data;
+                       if(val1 +val2 >key)
+                       {
+                                curr2=s2.top();
+                                 s2.pop();
+                                if(curr2->left)
+                                        s2.push(curr2->left);
+
+                       }       
+                      else if(val1 +val2 <key)
+                      {
+                                curr1=s1.top();
+                                s1.pop();
+                                if(curr1->right)
+                                        s1.push(curr1->right);
+
+                      }
+                      else
+                      {
+                             printf("%d + %d= %d \n",val1,val2,key);
+                             return;
+                      }
+
+                }
+
+        }while(val1<val2);
+}
+int main()
+{
+        Node *root=BuildTree();
+        findSum(root,96);
+}
diff --git a/ZigZag.cpp b/ZigZag.cpp
@@ -0,0 +1,51 @@
+#include"Tree.h"
+#include<queue>
+#include<stack>
+void ZigZag(Node *root)
+{
+        stack<Node * > s1,s2;
+        if(!root)
+                return;
+        s1.push(root);
+        bool lr=true;
+        while(!s1.empty() || !s2.empty())
+        {
+                if(lr)
+                {
+                        Node *curr=s1.top();
+                        printf("%d ",curr->data);
+                        if(curr->left)
+                                s2.push(curr->left);
+                        if(curr->right)
+                                s2.push(curr->right);
+                        s1.pop();
+                        if(s1.empty())
+                        {
+                                lr=false;
+                                printf("\n");
+                        }
+                }
+                else
+                {
+                        Node *curr=s2.top();
+                        printf("%d ",curr->data);
+                        if(curr->right)
+                                s1.push(curr->right);
+                        if(curr->left)
+                                s1.push(curr->left);
+                        s2.pop();
+                        if(s2.empty())
+                        {
+                                lr=true;
+                                printf("\n");
+                        }
+                }
+        }
+
+}
+int main()
+{
+        Node *root=BuildTree();
+        ZigZag(root);
+        return 0;
+}