{"id":27674,"date":"2017-09-06T00:32:07","date_gmt":"2017-09-05T19:02:07","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27674"},"modified":"2017-09-06T00:32:07","modified_gmt":"2017-09-05T19:02:07","slug":"check-identical-bsts-without-building-trees","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/check-identical-bsts-without-building-trees\/","title":{"rendered":"C Programming – Check for Identical BSTs without building the trees"},"content":{"rendered":"

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.<\/span><\/p>\n

\u00a0<\/p>\n[ad type=\u201dbanner\u201d]\n

Examples
\nFor example, the input arrays are {2, 4, 3, 1} and {2, 1, 4, 3} will construct the same tree<\/p>\n

 Let the input arrays be a[] and b[]\r\n\r\nExample 1:\r\na[] = {2, 4, 1, 3} will construct following tree.\r\n   2\r\n \/  \\\r\n1    4\r\n    \/\r\n   3\r\nb[] = {2, 4, 3, 1} will also also construct the same tree.\r\n   2\r\n \/  \\\r\n1    4\r\n    \/\r\n   3 \r\nSo the output is \"True\"\r\n\r\nExample 2:\r\na[] = {8, 3, 6, 1, 4, 7, 10, 14, 13}\r\nb[] = {8, 10, 14, 3, 6, 4, 1, 7, 13}\r\n\r\nThey both construct the same following BST, so output is \"True\"\r\n            8\r\n         \/    \\\r\n       3       10\r\n     \/  \\        \\\r\n    1     6       14\r\n        \/   \\     \/\r\n       4     7   13  \r\n<\/pre>\n
\u00a0<\/p>\n[ad type=\u201dbanner\u201d]\n
Solution:<\/strong>
\nAccording to BST property, elements of left subtree must be smaller and elements of right subtree must be greater than root.
\nTwo arrays represent sane BST if for every element x, the elements in left and right subtrees of x appear after it in both arrays. And same is true for roots of left and right subtrees.
\nThe idea is to check of if next smaller and greater elements are same in both arrays. Same properties are recursively checked for left and right subtrees. The idea looks simple, but implementation requires checking all conditions for all elements. Following is an interesting recursive implementation of the idea.<\/p>\n
\u00a0<\/p>\n[ad type=\u201dbanner\u201d]\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20A%20C%20program%20to%20check%20for%20Identical%20BSTs%20without%20building%20the%20trees%0A%23include%3Cstdio.h%3E%0A%23include%3Climits.h%3E%0A%23include%3Cstdbool.h%3E%0A%20%0A%2F*%20The%20main%20function%20that%20checks%20if%20two%20arrays%20a%5B%5D%20and%20b%5B%5D%20of%20size%20n%20construct%0A%20%20same%20BST.%20The%20two%20values%20\u2019min\u2019%20and%20\u2019max\u2019%20decide%20whether%20the%20call%20is%20made%20for%0A%20%20left%20subtree%20or%20right%20subtree%20of%20a%20parent%20element.%20The%20indexes%20i1%20and%20i2%20are%0A%20%20the%20indexes%20in%20(a%5B%5D%20and%20b%5B%5D)%20after%20which%20we%20search%20the%20left%20or%20right%20child.%0A%20%20Initially%2C%20the%20call%20is%20made%20for%20INT_MIN%20and%20INT_MAX%20as%20\u2019min\u2019%20and%20\u2019max\u2019%0A%20%20respectively%2C%20because%20root%20has%20no%20parent.%0A%20%20i1%20and%20i2%20are%20just%20after%20the%20indexes%20of%20the%20parent%20element%20in%20a%5B%5D%20and%20b%5B%5D.%20*%2F%0Abool%20isSameBSTUtil(int%20a%5B%5D%2C%20int%20b%5B%5D%2C%20int%20n%2C%20int%20i1%2C%20int%20i2%2C%20int%20min%2C%20int%20max)%0A%7B%0A%20%20%20int%20j%2C%20k%3B%0A%20%0A%20%20%20%2F*%20Search%20for%20a%20value%20satisfying%20the%20constraints%20of%20min%20and%20max%20in%20a%5B%5D%20and%20%0A%20%20%20%20%20%20b%5B%5D.%20If%20the%20parent%20element%20is%20a%20leaf%20node%20then%20there%20must%20be%20some%20%0A%20%20%20%20%20%20elements%20in%20a%5B%5D%20and%20b%5B%5D%20satisfying%20constraint.%20*%2F%0A%20%20%20for%20(j%3Di1%3B%20j%3Cn%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20if%20(a%5Bj%5D%3Emin%20%26%26%20a%5Bj%5D%3Cmax)%0A%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20for%20(k%3Di2%3B%20k%3Cn%3B%20k%2B%2B)%0A%20%20%20%20%20%20%20if%20(b%5Bk%5D%3Emin%20%26%26%20b%5Bk%5D%3Cmax)%0A%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%0A%20%20%20%2F*%20If%20the%20parent%20element%20is%20leaf%20in%20both%20arrays%20*%2F%0A%20%20%20if%20(j%3D%3Dn%20%26%26%20k%3D%3Dn)%0A%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%2F*%20Return%20false%20if%20any%20of%20the%20following%20is%20true%0A%20%20%20%20%20%20a)%20If%20the%20parent%20element%20is%20leaf%20in%20one%20array%2C%20but%20non-leaf%20in%20other.%0A%20%20%20%20%20%20b)%20The%20elements%20satisfying%20constraints%20are%20not%20same.%20We%20either%20search%0A%20%20%20%20%20%20%20%20%20for%20left%20child%20or%20right%20child%20of%20the%20parent%20element%20(decinded%20by%20min%0A%20%20%20%20%20%20%20%20%20and%20max%20values).%20The%20child%20found%20must%20be%20same%20in%20both%20arrays%20*%2F%0A%20%20%20if%20(((j%3D%3Dn)%5E(k%3D%3Dn))%20%7C%7C%20a%5Bj%5D!%3Db%5Bk%5D)%0A%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%2F*%20Make%20the%20current%20child%20as%20parent%20and%20recursively%20check%20for%20left%20and%20right%0A%20%20%20%20%20%20subtrees%20of%20it.%20Note%20that%20we%20can%20also%20pass%20a%5Bk%5D%20in%20place%20of%20a%5Bj%5D%20as%20they%0A%20%20%20%20%20%20are%20both%20are%20same%20*%2F%0A%20%20%20return%20isSameBSTUtil(a%2C%20b%2C%20n%2C%20j%2B1%2C%20k%2B1%2C%20a%5Bj%5D%2C%20max)%20%26%26%20%20%2F%2F%20Right%20Subtree%0A%20%20%20%20%20%20%20%20%20%20isSameBSTUtil(a%2C%20b%2C%20n%2C%20j%2B1%2C%20k%2B1%2C%20min%2C%20a%5Bj%5D)%3B%20%20%20%20%2F%2F%20Left%20Subtree%0A%7D%0A%20%0A%2F%2F%20A%20wrapper%20over%20isSameBSTUtil()%0Abool%20isSameBST(int%20a%5B%5D%2C%20int%20b%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20return%20isSameBSTUtil(a%2C%20b%2C%20n%2C%200%2C%200%2C%20INT_MIN%2C%20INT_MAX)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20int%20a%5B%5D%20%3D%20%7B8%2C%203%2C%206%2C%201%2C%204%2C%207%2C%2010%2C%2014%2C%2013%7D%3B%0A%20%20%20int%20b%5B%5D%20%3D%20%7B8%2C%2010%2C%2014%2C%203%2C%206%2C%204%2C%201%2C%207%2C%2013%7D%3B%0A%20%20%20int%20n%3Dsizeof(a)%2Fsizeof(a%5B0%5D)%3B%0A%20%20%20printf(%22%25s%5Cn%22%2C%20isSameBST(a%2C%20b%2C%20n)%3F%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%22BSTs%20are%20same%22%3A%22BSTs%20not%20same%22)%3B%0A%20%20%20return%200%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
\u00a0<\/p>\n[ad type=\u201dbanner\u201d]\n
\u00a0<\/strong><\/p>\n
Output:<\/strong><\/p>\n
BSTs are same<\/pre>\n","protected":false},"excerpt":{"rendered":"
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) <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[82509],"tags":[82528,82529,82527,82122,82526,82530],"class_list":["post-27674","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree-2","tag-add-all-greater-values-to-every-node-in-a-given-bst","tag-check-if-two-binary-search-trees-are-identical-given-their-array-representations","tag-get-mode-array-updates","tag-given-two-binary-trees","tag-symmetric-binary-tree-geeksforgeeks","tag-write-a-function-to-check-if-they-are-equal-or-not"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27674","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27674"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27674\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27674"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27674"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27674"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}