{"id":"af43730d-e106-4433-a6fb-9df5d82f3cb2","name":"Predecessor And Successor Of An Element","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to find the preorder predecessor and successor of a given element. Use the \"travel and change\" strategy explained in the earlier video. The static properties have been declared for you. You can declare more if you want.\r\n3. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"pred = None\r\nsucc = None\r\nclass Node:\r\n \r\n def __init__(self, data):\r\n self.data = data\r\n self.child = []\r\n \r\n # Utility function to create a new tree node\r\ndef newNode(data): \r\n temp = Node(data)\r\n return temp\r\n \r\ndef constructor(lst,n):\r\n root = None\r\n stack = []\r\n for i in range(0,n):\r\n if lst[i]==-1:\r\n stack.pop()\r\n else:\r\n t= Node(lst[i])\r\n if len(stack) > 0:\r\n stack[-1].child.append(t)\r\n \r\n else:\r\n root=t\r\n \r\n stack.append(t)\r\n return root\r\n\r\n \r\n\r\ndef prendsucc(node,data):\r\n #Write your code here\r\n\r\n \r\nlst = []\r\n# number of elements as input\r\nn = int(input())\r\n\r\nlst = list(map(int, input().split()))\r\n\r\n\r\nroot = constructor(lst,n) \r\ndata = int(input())\r\nprendsucc(root,data)\r\n\r\nif pred == None:\r\n print(\"Predecessor = Not found\")\r\nelse:\r\n print(\"Predecessor =\" , pred.data)\r\n \r\nif succ == None:\r\n print(\"Successor = Not found\")\r\nelse:\r\n print(\"Successor =\", succ.data)"},"java":{"code":"#include<bits/stdc++.h>\r\nusing namespace std;\r\n\r\n\r\n\r\nstruct Node{\r\n int data;\r\n vector<Node*>children;\r\n};\r\n\r\nNode *newNode(int key){\r\n\tNode *temp=new Node;\r\n\ttemp->data=key;\r\n\treturn temp;\r\n\r\n}\r\n\r\nNode *construct(int arr[],int n ){\r\n Node *root=NULL;\r\n stack<Node*>st;\r\n for(int i=0;i<n;i++){\r\n if(arr[i]==-1){\r\n st.pop();\r\n }else{\r\n Node *t=newNode(arr[i]);\r\n \r\n if(st.size()>0){\r\n st.top()->children.push_back(t);\r\n }else{\r\n root=t;\r\n }\r\n st.push(t);\r\n }\r\n }\r\n return root;\r\n}\r\n\r\nNode *pre ;\r\nNode *suc ;\r\nint state=0 ;\r\n\r\n\r\nvoid prnsc(Node *node, int data){\r\n //Write your code here\r\n \r\n}\r\n\r\nint main(){\r\n \r\n int n;\r\n cin>>n;\r\n \r\n int arr[n];\r\n for(int i=0;i<n;i++){\r\n cin>>arr[i];\r\n }\r\n int val;\r\n cin>>val;\r\n Node *root=construct(arr,n);\r\n prnsc(root,val);\r\n if(pre==NULL){\r\n cout<<\"Predecessor = Not found\"<<endl;\r\n } else {\r\n cout<<\"Predecessor = \"<< pre->data<<endl;\r\n }\r\n\r\n if(suc==NULL){\r\n cout<<\"Successor = Not found\";\r\n } else {\r\n cout<<\"Successor = \" << suc->data;\r\n }\r\n}"},"python":{"code":"pred = None\nsucc = None\nclass Node:\n \n def __init__(self, data):\n self.data = data\n self.child = []\n \n # Utility function to create a new tree node\ndef newNode(data): \n temp = Node(data)\n return temp\n \ndef constructor(lst,n):\n root = None\n stack = []\n for i in range(0,n):\n if lst[i]==-1:\n stack.pop()\n else:\n t= Node(lst[i])\n if len(stack) > 0:\n stack[-1].child.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\n\n \n\ndef prendsucc(node,data):\n #Write your code here\n\n \nlst = []\n# number of elements as input\nn = int(input())\n\nlst = list(map(int, input().split()))\n\n\nroot = constructor(lst,n) \ndata = int(input())\nprendsucc(root,data)\n\nif pred == None:\n print(\"Predecessor = Not found\")\nelse:\n print(\"Predecessor =\" , pred.data)\n \nif succ == None:\n print(\"Successor = Not found\")\nelse:\n print(\"Successor =\", succ.data)"}},"points":10,"difficulty":"easy","sampleInput":"24\r\n10 20 -50 -1 60 -1 -1 30 70 -1 -80 110 -1 -120 -1 -1 90 -1 -1 40 -100 -1 -1 -1\r\n-120","sampleOutput":"Predecessor = 110\r\nSuccessor = 90","questionVideo":"https://www.youtube.com/embed/vfNlLP-oOUg","hints":[],"associated":[{"id":"3acb1503-dcbe-4e84-abc3-9c97eb704d5f","name":"Which traversal is preferable in a question like this one?","slug":"which-traversal-is-preferable-in-a-question-like-this-one","type":4},{"id":"5b76f02e-7dd5-4874-b074-20811ab5457c","name":"What is the approach required to solve this problem called?","slug":"what-is-the-approach-required-to-solve-this-problem-called","type":4},{"id":"5bf1c7dd-097e-4d41-af9f-99d185f3b1f0","name":"What is the expected space complexity of \"Predecessor And Successor Of An Element\"?","slug":"what-is-the-expected-space-complexity-of-predecessor-and-successor-of-an-element","type":4},{"id":"a237dd04-8eec-49e1-b3a0-f9ec3dc69055","name":"If we find the given node, should we stop the search?","slug":"if-we-find-the-given-node-should-we-stop-the-search","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"b6a55c74-7dc3-45b6-a948-9dcbaebf9367","name":"Generic Tree For Beginners","slug":"generic-tree-for-beginners","type":0},{"id":"ff3d8afd-5921-4d68-a393-ca17b106b140","name":"Predecessor And Successor Of An Element","slug":"predecessor-and-successor-of-an-element","type":1}],"next":{"id":"eff5c874-de66-489f-930e-b6b4fab4e80f","name":"Predecessor and Successor of an Element","type":3,"slug":"predecessor-and-successor-of-an-element"},"prev":{"id":"bffe3e57-3c80-47c6-ac5b-570757411187","name":"Generic Tree - MultiSolver","type":0,"slug":"generic-tree-multisolver"}}}

Predecessor And Successor Of An Element

1. You are given a partially written GenericTree class. 2. You are required to find the preorder predecessor and successor of a given element. Use the "travel and change" strategy explained in the earlier video. The static properties have been declared for you. You can declare more if you want. 3. Input and Output is managed for you.

{"id":"af43730d-e106-4433-a6fb-9df5d82f3cb2","name":"Predecessor And Successor Of An Element","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to find the preorder predecessor and successor of a given element. Use the \"travel and change\" strategy explained in the earlier video. The static properties have been declared for you. You can declare more if you want.\r\n3. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"pred = None\r\nsucc = None\r\nclass Node:\r\n \r\n def __init__(self, data):\r\n self.data = data\r\n self.child = []\r\n \r\n # Utility function to create a new tree node\r\ndef newNode(data): \r\n temp = Node(data)\r\n return temp\r\n \r\ndef constructor(lst,n):\r\n root = None\r\n stack = []\r\n for i in range(0,n):\r\n if lst[i]==-1:\r\n stack.pop()\r\n else:\r\n t= Node(lst[i])\r\n if len(stack) > 0:\r\n stack[-1].child.append(t)\r\n \r\n else:\r\n root=t\r\n \r\n stack.append(t)\r\n return root\r\n\r\n \r\n\r\ndef prendsucc(node,data):\r\n #Write your code here\r\n\r\n \r\nlst = []\r\n# number of elements as input\r\nn = int(input())\r\n\r\nlst = list(map(int, input().split()))\r\n\r\n\r\nroot = constructor(lst,n) \r\ndata = int(input())\r\nprendsucc(root,data)\r\n\r\nif pred == None:\r\n print(\"Predecessor = Not found\")\r\nelse:\r\n print(\"Predecessor =\" , pred.data)\r\n \r\nif succ == None:\r\n print(\"Successor = Not found\")\r\nelse:\r\n print(\"Successor =\", succ.data)"},"java":{"code":"#include<bits/stdc++.h>\r\nusing namespace std;\r\n\r\n\r\n\r\nstruct Node{\r\n int data;\r\n vector<Node*>children;\r\n};\r\n\r\nNode *newNode(int key){\r\n\tNode *temp=new Node;\r\n\ttemp->data=key;\r\n\treturn temp;\r\n\r\n}\r\n\r\nNode *construct(int arr[],int n ){\r\n Node *root=NULL;\r\n stack<Node*>st;\r\n for(int i=0;i<n;i++){\r\n if(arr[i]==-1){\r\n st.pop();\r\n }else{\r\n Node *t=newNode(arr[i]);\r\n \r\n if(st.size()>0){\r\n st.top()->children.push_back(t);\r\n }else{\r\n root=t;\r\n }\r\n st.push(t);\r\n }\r\n }\r\n return root;\r\n}\r\n\r\nNode *pre ;\r\nNode *suc ;\r\nint state=0 ;\r\n\r\n\r\nvoid prnsc(Node *node, int data){\r\n //Write your code here\r\n \r\n}\r\n\r\nint main(){\r\n \r\n int n;\r\n cin>>n;\r\n \r\n int arr[n];\r\n for(int i=0;i<n;i++){\r\n cin>>arr[i];\r\n }\r\n int val;\r\n cin>>val;\r\n Node *root=construct(arr,n);\r\n prnsc(root,val);\r\n if(pre==NULL){\r\n cout<<\"Predecessor = Not found\"<<endl;\r\n } else {\r\n cout<<\"Predecessor = \"<< pre->data<<endl;\r\n }\r\n\r\n if(suc==NULL){\r\n cout<<\"Successor = Not found\";\r\n } else {\r\n cout<<\"Successor = \" << suc->data;\r\n }\r\n}"},"python":{"code":"pred = None\nsucc = None\nclass Node:\n \n def __init__(self, data):\n self.data = data\n self.child = []\n \n # Utility function to create a new tree node\ndef newNode(data): \n temp = Node(data)\n return temp\n \ndef constructor(lst,n):\n root = None\n stack = []\n for i in range(0,n):\n if lst[i]==-1:\n stack.pop()\n else:\n t= Node(lst[i])\n if len(stack) > 0:\n stack[-1].child.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\n\n \n\ndef prendsucc(node,data):\n #Write your code here\n\n \nlst = []\n# number of elements as input\nn = int(input())\n\nlst = list(map(int, input().split()))\n\n\nroot = constructor(lst,n) \ndata = int(input())\nprendsucc(root,data)\n\nif pred == None:\n print(\"Predecessor = Not found\")\nelse:\n print(\"Predecessor =\" , pred.data)\n \nif succ == None:\n print(\"Successor = Not found\")\nelse:\n print(\"Successor =\", succ.data)"}},"points":10,"difficulty":"easy","sampleInput":"24\r\n10 20 -50 -1 60 -1 -1 30 70 -1 -80 110 -1 -120 -1 -1 90 -1 -1 40 -100 -1 -1 -1\r\n-120","sampleOutput":"Predecessor = 110\r\nSuccessor = 90","questionVideo":"https://www.youtube.com/embed/vfNlLP-oOUg","hints":[],"associated":[{"id":"3acb1503-dcbe-4e84-abc3-9c97eb704d5f","name":"Which traversal is preferable in a question like this one?","slug":"which-traversal-is-preferable-in-a-question-like-this-one","type":4},{"id":"5b76f02e-7dd5-4874-b074-20811ab5457c","name":"What is the approach required to solve this problem called?","slug":"what-is-the-approach-required-to-solve-this-problem-called","type":4},{"id":"5bf1c7dd-097e-4d41-af9f-99d185f3b1f0","name":"What is the expected space complexity of \"Predecessor And Successor Of An Element\"?","slug":"what-is-the-expected-space-complexity-of-predecessor-and-successor-of-an-element","type":4},{"id":"a237dd04-8eec-49e1-b3a0-f9ec3dc69055","name":"If we find the given node, should we stop the search?","slug":"if-we-find-the-given-node-should-we-stop-the-search","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"b6a55c74-7dc3-45b6-a948-9dcbaebf9367","name":"Generic Tree For Beginners","slug":"generic-tree-for-beginners","type":0},{"id":"ff3d8afd-5921-4d68-a393-ca17b106b140","name":"Predecessor And Successor Of An Element","slug":"predecessor-and-successor-of-an-element","type":1}],"next":{"id":"eff5c874-de66-489f-930e-b6b4fab4e80f","name":"Predecessor and Successor of an Element","type":3,"slug":"predecessor-and-successor-of-an-element"},"prev":{"id":"bffe3e57-3c80-47c6-ac5b-570757411187","name":"Generic Tree - MultiSolver","type":0,"slug":"generic-tree-multisolver"}}}
plane

Editor

Loading...

Predecessor And Successor Of An Element

easy

1. You are given a partially written GenericTree class. 2. You are required to find the preorder predecessor and successor of a given element. Use the "travel and change" strategy explained in the earlier video. The static properties have been declared for you. You can declare more if you want. 3. Input and Output is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

24 10 20 -50 -1 60 -1 -1 30 70 -1 -80 110 -1 -120 -1 -1 90 -1 -1 40 -100 -1 -1 -1 -120

Sample Output

Predecessor = 110 Successor = 90

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode