tag:blogger.com,1999:blog-4228859841453048938.post3127994696404278109..comments2024-03-29T15:50:59.980+08:00Comments on Coding Interview Questions: No. 46 - Nodes with Sum in a Binary Search TreeHarry Hehttp://www.blogger.com/profile/10363303096963693183noreply@blogger.comBlogger26125tag:blogger.com,1999:blog-4228859841453048938.post-18916429728410640952022-06-12T00:57:18.711+08:002022-06-12T00:57:18.711+08:00To see working code always feels good.
Give it a ...To see working code always feels good.<br /><br />Give it a try before looking into it ;)Guru Prasath Balakrishnanhttps://www.blogger.com/profile/07043656860493151307noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-75505410130686080712022-06-12T00:54:05.538+08:002022-06-12T00:54:05.538+08:00import java.util.*;
class TreeNode{
int val;
...import java.util.*;<br />class TreeNode{<br /> int val;<br /> TreeNode left, right;<br /> public TreeNode(int val){<br /> this.val=val;<br /> this.left=this.right=null;<br /> }<br />}<br /><br />class Solution{<br /> public static void main(String[] args){<br /> TreeNode root=new TreeNode(32);<br /> root.left=new TreeNode(24);<br /> root.right=new TreeNode(41);<br /> root.left.left=new TreeNode(21);<br /> root.left.left.left=new TreeNode(14);<br /> root.left.right=new TreeNode(28);<br /> root.left.right.left=new TreeNode(25);<br /> root.left.right.right=new TreeNode(31);<br /> root.right.left=new TreeNode(36);<br /> root.right.right=new TreeNode(47);<br /> root.right.left.right=new TreeNode(39); <br /> <br /> Stack stack=new Stack();<br /> <br /> System.out.println(checkSum(root,56));<br /> <br /><br /> System.out.println("Success");<br /> }<br /> <br /> public static boolean checkSum(TreeNode root,int checkSum){<br /> Stack nextNodes=new Stack();<br /> Stack prevNodes=new Stack();<br /> <br /> buildNextNodes(root,nextNodes);<br /> buildPrevNodes(root,prevNodes);<br /> <br /> TreeNode pNext=getNextNode(nextNodes);<br /> TreeNode pPrev=getPrevNode(prevNodes);<br /> <br /> while(pNext!=null && pPrev!=null && pNext!=pPrev){<br /> int curr_sum= pNext.val+pPrev.val;<br /> if(curr_sum==checkSum){<br /> System.out.println("TRUE pNext.val=>"+pNext.val+"pPrev.val=>"+pPrev.val);<br /> return true;<br /> }<br /> else if(curr_sum"+pNext.val+"pPrev.val=>"+pPrev.val);<br /> pNext=getNextNode(nextNodes);<br /> }<br /> else{<br />System.out.println("CURR MORE pNext.val=>"+pNext.val+"pPrev.val=>"+pPrev.val);<br /> pPrev=getPrevNode(prevNodes);<br /> }<br /><br /> }<br /> <br /> return false;<br /> }<br /> <br /> public static void buildNextNodes(TreeNode root, Stack stack){<br /> TreeNode node=root;<br /> while(node!=null){<br /> stack.push(node);<br /> node=node.left;<br /> }<br /> }<br /> <br /> public static void buildPrevNodes(TreeNode root, Stack stack){<br /> TreeNode node=root;<br /> while(node!=null){<br /> stack.push(node);<br /> node=node.right;<br /> }<br /> }<br /> <br /> <br /><br />public static TreeNode getNextNode(Stack stack){<br /> TreeNode next=null;<br /> if(!stack.empty()){<br /> next=stack.peek();<br /> stack.pop();<br /> TreeNode right=next.right;<br /> while(right!=null){<br /> stack.push(right);<br /> right=right.left;<br /> }<br /> }<br /> return next;<br /> }<br /> <br /> public static TreeNode getPrevNode(Stack stack){<br /> TreeNode prev=null;<br /> if(!stack.empty()){<br /> prev=stack.peek();<br /> stack.pop();<br /> TreeNode left=prev.left;<br /> while(left!=null){<br /> stack.push(left);<br /> left=left.right;<br /> }<br /> }<br /> return prev;<br /> }<br /> <br />}<br /><br />java -cp /tmp/AyIgrKmLoG Solution<br />CURR MORE pNext.val=>14pPrev.val=>47<br />CURR LESS pNext.val=>14pPrev.val=>41<br />CURR MORE pNext.val=>21pPrev.val=>41<br />CURR MORE pNext.val=>21pPrev.val=>39<br />CURR MORE pNext.val=>21pPrev.val=>36<br />CURR LESS pNext.val=>21pPrev.val=>32<br />TRUE pNext.val=>24pPrev.val=>32<br />true<br />Success<br /><br /><br /><br /><br />Guru Prasath Balakrishnanhttps://www.blogger.com/profile/07043656860493151307noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-82405505313487038192020-03-31T23:58:18.560+08:002020-03-31T23:58:18.560+08:00My solution using a map: (Kotlin)
fun hasTwoNodes...My solution using a map: (Kotlin)<br /><br />fun hasTwoNodes(node: Node?, sum: Int, map: MutableMap): Boolean {<br /> if (node == null) {<br /> return false<br /> }<br /><br /> val diff = sum - node.value!!<br /><br /> if (map[diff] != null) {<br /> return true<br /> }<br /><br /> map[node.value!!] = node.value!!<br /><br /> val left = hasTwoNodes(node.left, sum, map)<br /> val right = hasTwoNodes(node.right, sum, map)<br /><br /> if (map[diff] != null) {<br /> return true<br /> }<br /><br /> return left || right<br />}mcmatanhttps://www.blogger.com/profile/14142426554157822184noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-63305961314604964882020-02-07T23:07:56.616+08:002020-02-07T23:07:56.616+08:00Thank you sharing wondefull Information
I also fo...<br />Thank you sharing wondefull Information <br />I also found Various useful links related to Devops, Docker & Kubernetes <br /><br /><br /><a href="http://linux.amitmaheshwari.in/2020/02/kubernetes-kubectl-commands-cheatsheet.html" rel="nofollow"> Kubernetes Kubectl Commands CheatSheet </a><br /><br /><a href="http://linux.amitmaheshwari.in/2020/02/introduction-to-kubernetes-networking.html" rel="nofollow"> Introduction to Kubernetes Networking </a><br /><br /><a href="http://linux.amitmaheshwari.in/2020/02/basic-concept-of-kubernetes.html" rel="nofollow"> Basic Concept of Kubernetes </a><br /><br /><a href="http://linux.amitmaheshwari.in/2019/11/kubernetes-interview-questions-and.html" rel="nofollow"> Kubernetes Interview Question and Answers </a><br /><br /><a href="http://linux.amitmaheshwari.in/2020/02/kubernetes-kubectl-commands-cheatsheet.html" rel="nofollow"> Kubernetes Sheetsheat </a><br /><br /><a href="http://linux.amitmaheshwari.in/2019/11/docker-interview-questions-and-answers.html" rel="nofollow"> Docker Interview Question and Answers </a><br /><br /><a href="http://linux.amitmaheshwari.in/2019/12/docker-basic-tutorial.html" rel="nofollow"> Docker Basic Tutorial </a><br />Editorhttps://www.blogger.com/profile/08032442576837072724noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-3182631280472425202018-06-05T18:15:19.579+08:002018-06-05T18:15:19.579+08:00Hi Bru,
Such vivid info on the ! Flabbergasted! ...Hi Bru,<br /><br /><br />Such vivid info on the ! Flabbergasted! Thank you for making the read a smooth sail!<br /><br /><br /><br /><br />The Make Public function in S3 is perfectly working these past few months and years I should say.<br />Just last week, we are experiencing failure in the "Make Public" function. Once I successfully upload a <a href="https://medium.com/freetraining/aws-596f86582865" rel="nofollow"> AWS Training </a> with multiple files) then Make Public the uploaded files, the notification below shows Failure<br /><br />Anyways great write up, your efforts are much appreciated.<br /><br /><br />ganesh,<br /><br />Anonymoushttps://www.blogger.com/profile/04859983121687046225noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-60362726380142813482018-06-01T19:19:35.649+08:002018-06-01T19:19:35.649+08:00Olà,
Interesting piece!Great to see someone writ...Olà,<br /><br /><br />Interesting piece!Great to see someone write No. 46 - Nodes with Sum in a Binary Search Tree who is not a fanatic or a complete skeptic.<br /><br />I have an rds database that I am connecting to from an ec2 instance in the same VPC. Someone told me that when ec2 instances connect to an rds instance in the same vpc, that it is over the private subnet. <a href="https://asha24.com/blog/aws-tutorials-training-certification-and-interview-qa/" rel="nofollow"> AWS Tutorial </a><br /><br /><br /><br /><br /><br /><br />I am so grateful for your blog. Really looking forward to read more.<br /><br /><br />Kind Regards,<br />Anonymoushttps://www.blogger.com/profile/11674257547961232200noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-13091724123313861582016-04-02T08:45:01.143+08:002016-04-02T08:45:01.143+08:00Opps, wrong gist: https://gist.github.com/pjrt/04e...Opps, wrong gist: https://gist.github.com/pjrt/04e7d67e6ec89c140f3768dd9bc24999 Pedro R.https://www.blogger.com/profile/09155622475973504857noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-83454313884774904872016-04-02T08:39:32.079+08:002016-04-02T08:39:32.079+08:00Here it is in Haskell:
https://gist.github.com/pj...Here it is in Haskell: <br />https://gist.github.com/pjrt/a3eb270101c40dce4047d14ec9bb15c2<br /><br />This is a pretty cool exercise. Pedro R.https://www.blogger.com/profile/09155622475973504857noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-65252570981879435462016-04-02T08:32:56.147+08:002016-04-02T08:32:56.147+08:00This comment has been removed by the author.Pedro R.https://www.blogger.com/profile/09155622475973504857noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-3238997983881118032016-04-02T08:30:37.495+08:002016-04-02T08:30:37.495+08:00This comment has been removed by the author.Pedro R.https://www.blogger.com/profile/09155622475973504857noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-13506933523776586802015-09-07T14:33:16.930+08:002015-09-07T14:33:16.930+08:00Here i am pasting recursion code. My thoughts are ...Here i am pasting recursion code. My thoughts are as below:<br />1) If sum is less than root then both the numbers will be left of the BST without root.<br />2) If sum is equals to the root then numbers will be at the root including root.<br />3) If sum is greater than root then there are 3 cases: a) Both are at right side b) Both at left side c) One is in left side and other is at side.<br /><br />After this decision we subtract the node value with the given sum and check whether the difference value present or not. Here is working code:<br /><br /><br />private Integer sum(LeftLeaningRedBlackTree.Node node,<br /> Integer number) {<br /> if (node == null) {<br /> return null;<br /> }<br /><br /> int cmp = number.compareTo(node.key);<br /> int nodeInt = node.key.intValue();<br /> int userInt = number.intValue();<br /><br /> if (cmp < 0) {<br /> if (node.left == null) {<br /> return null;<br /> }<br /> nodeInt = node.left.key.intValue();<br /><br /> int diff = nodeInt - userInt;<br /> Integer found = rbt.search(node.left, diff);<br /> if (found == null) {<br /> return sum(node.left, number);<br /> } else {<br /> System.out.println(nodeInt + " " + diff);<br /> return 0;<br /> }<br /> } else if (cmp > 0) {<br /> int diff = userInt - nodeInt;<br /> boolean found = rbt.search(diff);<br /> if (!found || diff == nodeInt) {<br /> return sum(node.right, number);<br /> } else {<br /> System.out.println(nodeInt + " " + diff);<br /> return 0;<br /> }<br /> } else {<br /> int diff = userInt - nodeInt;<br /> boolean found = rbt.search(diff);<br /> if (!found) {<br /> return sum(node.right, number);<br /> } else {<br /> System.out.println(nodeInt + " " + diff);<br /> return 0;<br /> }<br /> }<br /> }Tushar Goelhttps://www.blogger.com/profile/11713810101368115487noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-61461943668112170792014-06-06T13:31:28.202+08:002014-06-06T13:31:28.202+08:00Super useful, thanksSuper useful, thanksA. Thomas Tranhttps://www.blogger.com/profile/00206927766192684054noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-36880135078729083422014-02-19T18:18:26.808+08:002014-02-19T18:18:26.808+08:00you can do that , but again predecessor and succes...you can do that , but again predecessor and successor would take time , which would add to the time complexity( worst case - O(nlogn)<br />or if you wish to add a parent pointer to the data structure that would mean , adding O(n) space which would be greater than maintaining a parent pointer<br /><br /><br />One way to this in O(n) time and O(1) space would be to convert the BST into a doubly linked list in place(without using additional memory ) <br />and then do your thing with the sorted linked list , then convert back the linked list to bst <br />reference:-<br />http://cslibrary.stanford.edu/109/TreeListRecursion.htmlnikhilhttps://www.blogger.com/profile/04830920257970777283noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-47640494782732165542013-10-20T11:11:28.363+08:002013-10-20T11:11:28.363+08:00Here's simpler implementation. Just subtract t...Here's simpler implementation. Just subtract the sum from current value of the node and find <br />the node with remainder.<br /><br />boolean isSumOfTwo(Node node,int sum){<br /> if(node == null){<br /> return (sum==0);<br /> }<br /> <br /> int s = sum - node.mValue;<br /> boolean found = find(s);<br /> if ( found){<br /> return true;<br /> }<br /> boolean left = isSumOfTwo(node.mLeft,sum);<br /> boolean right = isSumOfTwo(node.mRight,sum);<br /> return (ml || mr);<br /> }<br /><br /> boolean find ( Node node, int value){<br /> if(node == null){<br /> return false;<br /> }<br /> if ( node.mValue == value){<br /> return true;<br /> }else if ( node.mValue < value){<br /> return find(node.mRight,value);<br /> }else{<br /> return find(node.mLeft,value);<br /> }<br /> }<br /> Unknownhttps://www.blogger.com/profile/16197153248542795629noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-30049904434791211572013-09-23T18:57:51.083+08:002013-09-23T18:57:51.083+08:00For those who interested, a Java code representati...For those who interested, a Java code representation:<br /><br />import java.util.Stack;<br /><br />/**<br /> * Created by Chernyshov Yuriy on 9/23/13<br /> */<br />public class BST_2sumFinder {<br /><br /> public boolean hasTwoNodes(BinaryTreeEntity pRoot, int sum) {<br /> Stack nextNodes = new Stack();<br /> Stack prevNodes = new Stack();<br /> buildNextNodes(pRoot, nextNodes);<br /> buildPrevNodes(pRoot, prevNodes);<br /><br /> BinaryTreeEntity pNext = getNextNode(nextNodes);<br /> BinaryTreeEntity pPrev = getPreviousNode(prevNodes);<br /> while (pNext != null && pPrev != null && pNext != pPrev) {<br /> int currentSum = pNext.getEntityValue() + pPrev.getEntityValue();<br /> if (currentSum == sum)<br /> return true;<br /> if (currentSum < sum)<br /> pNext = getNextNode(nextNodes);<br /> else<br /> pPrev = getPreviousNode(prevNodes);<br /> }<br /><br /> return false;<br /> }<br /><br /> void buildNextNodes(BinaryTreeEntity pRoot, Stack nodes) {<br /> BinaryTreeEntity pNode = pRoot;<br /> while (pNode != null) {<br /> nodes.push(pNode);<br /> pNode = pNode.getLeft();<br /> }<br /> }<br /><br /> void buildPrevNodes(BinaryTreeEntity pRoot, Stack nodes) {<br /> BinaryTreeEntity pNode = pRoot;<br /> while (pNode != null) {<br /> nodes.push(pNode);<br /> pNode = pNode.getRight();<br /> }<br /> }<br /><br /> private BinaryTreeEntity getNextNode(Stack nodes) {<br /> BinaryTreeEntity pNext = null;<br /> if (!nodes.empty()) {<br /> pNext = nodes.peek();<br /> nodes.pop();<br /> BinaryTreeEntity pRight = pNext.getRight();<br /> while (pRight != null) {<br /> nodes.push(pRight);<br /> pRight = pRight.getLeft();<br /> }<br /> }<br /><br /> return pNext;<br /> }<br /><br /> private BinaryTreeEntity getPreviousNode(Stack nodes) {<br /> BinaryTreeEntity pPrev = null;<br /> if (!nodes.empty()) {<br /> pPrev = nodes.peek();<br /> nodes.pop();<br /> BinaryTreeEntity pLeft = pPrev.getLeft();<br /> while (pLeft != null) {<br /> nodes.push(pLeft);<br /> pLeft = pLeft.getRight();<br /> }<br /> }<br /> return pPrev;<br /> }<br />}<br /><br />Here "BinaryTreeEntity" is an which represents a tree node. It has a pointers to the left and right children and a value of itself.<br /><br />Sorry for the code formatting, I have no idea how to format it here.Anonymoushttps://www.blogger.com/profile/01293836583988171412noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-39792066713721431962013-09-23T18:47:54.172+08:002013-09-23T18:47:54.172+08:00What if You do not have enough memory? Suppose a ...What if You do not have enough memory? Suppose a tree has a million of nodes and You develope some module for the car GPS system (with extreem low memory resources) ? You will get Out Of Memory very quick if You do data structure conversion for each operation.Anonymoushttps://www.blogger.com/profile/01293836583988171412noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-84628083760519509902013-09-10T09:13:46.182+08:002013-09-10T09:13:46.182+08:00If it's allowed to modify the input tree, your...If it's allowed to modify the input tree, your solution works.Harry Hehttps://www.blogger.com/profile/10363303096963693183noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-91983438049152330652013-08-13T14:24:35.732+08:002013-08-13T14:24:35.732+08:00great explanation thks a lot......
great explanation thks a lot......<br />Anonymoushttps://www.blogger.com/profile/00484048542967437954noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-42453805716850078052013-07-29T06:26:20.763+08:002013-07-29T06:26:20.763+08:00what you mean by predecessor and successor functio...what you mean by predecessor and successor functions? I am trying to use your idea to implement, thank you if you can give me some examplesjuniwayhttps://www.blogger.com/profile/05658116438141688298noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-63520954308735166242013-07-12T23:48:20.598+08:002013-07-12T23:48:20.598+08:00create a double linked list and use the same logic...create a double linked list and use the same logic which we used in sorted array....comment plez<br />?Anonymoushttps://www.blogger.com/profile/01309188027863832476noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-67009774494590462392013-07-11T02:01:32.943+08:002013-07-11T02:01:32.943+08:00For finding the previous and next nodes in BST, yo...For finding the previous and next nodes in BST, you can also use predecessor and successor functions, instead of using stack which has space complexity.Anonymoushttps://www.blogger.com/profile/00176028693071167073noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-37069014121349406422013-06-26T21:52:11.368+08:002013-06-26T21:52:11.368+08:00how will this solution work if both the nodes are ...how will this solution work if both the nodes are on the same side of the root node?wiseguyhttps://www.blogger.com/profile/04932441712825232822noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-16045959528688472882013-06-18T12:06:25.016+08:002013-06-18T12:06:25.016+08:00Throw in a hash and do in order traversal.
var i...Throw in a hash and do in order traversal. <br /><br />var io = function(bst, map, k){<br />if(!bst)return;<br /><br />io(bst.left, map,k);<br /><br />map[bst.data] = 0;<br /><br />if(map[k - bst.data]=== 0){<br />console.log("{"+(k - bst.data) +"}{"+bst.data+"}");<br />}<br /><br /><br />io(bst.right, map, k);<br /><br /><br />}virgiliohttps://www.blogger.com/profile/15438798139894817739noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-79077171741299795122013-05-10T01:25:46.894+08:002013-05-10T01:25:46.894+08:00@Dmitry converting to array takes O(n) space. Here...@Dmitry converting to array takes O(n) space. Here it would take O(logn) space if tree is balanced. very good logic! The way you simulate the next and prev pointer of an array is awesome.Ajayahttps://www.blogger.com/profile/17148082105056755969noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-86779049747170560402013-04-24T11:38:18.261+08:002013-04-24T11:38:18.261+08:00Too much of traversal and convoluted logic. Simply...Too much of traversal and convoluted logic. Simply convert to array and approach from both sides - waaay simpler.Anonymoushttps://www.blogger.com/profile/05426440330658398930noreply@blogger.com