{"id":3907,"date":"2021-11-19T11:34:28","date_gmt":"2021-11-19T06:04:28","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3907"},"modified":"2021-11-19T11:34:30","modified_gmt":"2021-11-19T06:04:30","slug":"construct-tree-from-inorder-and-preorder","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/construct-tree-from-inorder-and-preorder\/","title":{"rendered":"Construct Tree from Inorder and Preorder"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#approach-recursion\">Approach: Recursion<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faq\">FAQ<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p>Given two arrays <strong>inorder[] <\/strong>and <strong>preorder[]<\/strong>, which represents the inorder and the preorder traversal of a binary tree. The task is to construct the tree from the given order and return it.<\/p>\n\n\n\n<p><strong>Examples:Input: <br>preorder[] <\/strong>= {3,9,20,15,7}<br><strong>inorder[]<\/strong> = {9,3,15,20,7}<strong><br>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<\/strong><br><strong>Output:<\/strong> {3,9,20,null,null,15,7}<br><strong>Explanation:\u00a0<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"727\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"output\"  class=\"wp-image-4042 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-1-1024x727.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-1-1024x727.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-1-300x213.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-1-768x545.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-1-380x270.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-1-550x391.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-1-800x568.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-1-1160x824.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-1.png 1221w\" ><\/figure>\n\n\n\n<h2 id=\"approach-recursion\">Approach: Recursion<\/h2>\n\n\n\n<p><strong><br><\/strong>We already know that in <strong>Preorder <\/strong>traversal, we traverse from <strong>ROOT&nbsp; -&gt; LEFT -&gt; RIGHT<\/strong>. Therefore, we can easily determine the root of the resultant tree which is <strong>preorder[0]<\/strong>.<\/p>\n\n\n\n<p>Similarly, if you remember <strong>Inorder <\/strong>traversal, we traverse from <strong>LEFT -> ROOT -> RIGHT<\/strong>. So, if we can find the position of the <strong>Root <\/strong>in the <strong>inorder[]<\/strong>, we can recursively divide the <strong>left <\/strong>and the <strong>right <\/strong>subtrees.<br><br>Follow the below method:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1025\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"left and the right subtrees\"  class=\"wp-image-4043 pk-lazyload\"  data-pk-sizes=\"auto\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-and-the-right-subtrees.gif\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Initialise a hashmap to find the index of the root.<\/li><li>Maintain a variable which contains all the keys and value to be used in the final binary tree.<\/li><li>Construct a recursive function, which takes the inorder array as an argument and for each iteration, recursively built the left and right subtree by comparing the values with the position of the root.<\/li><\/ul>\n\n\n\n<p><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">struct Node * buildTree(char in [], char pre[], int inStrt,\n  int inEnd, unordered_map &amp;lt; char, int &amp;gt; &amp;amp; mp) {\n  static int preIndex = 0;\n \n  if (inStrt &amp;gt; inEnd)\n    return NULL;\n \n  char curr = pre[preIndex++];\n  struct Node * tNode = newNode(curr);\n \n  if (inStrt == inEnd)\n    return tNode;\n \n  int inIndex = mp[curr];\n \n  tNode -&amp;gt; left = buildTree( in , pre, inStrt, inIndex - 1, mp);\n  tNode -&amp;gt; right = buildTree( in , pre, inIndex + 1, inEnd, mp);\n \n  return tNode;\n}\n \nstruct Node * buldTreeWrap(char in [], char pre[], int len) {\n  unordered_map &amp;lt; char, int &amp;gt; mp;\n  for (int i = 0; i &amp;lt; len; i++)\n    mp[ in [i]] = i;\n \n  return buildTree( in , pre, 0, len - 1, mp);\n}\nvoid printInorder(struct Node * node) {\n  if (node == NULL)\n    return;\n  printInorder(node -&amp;gt; left);\n  printf(\"%c \", node -&amp;gt; data);\n  printInorder(node -&amp;gt; right);\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> class Tree {\n \n  public static Node root;\n  static HashMap &amp;lt; Character, Integer &amp;gt; mp = new HashMap &amp;lt; &amp;gt; ();\n  static int preIndex = 0;\n \n  public static Node buildTree(char[] in , char[] pre, int inStrt, int inEnd) {\n \n    if (inStrt &amp;gt; inEnd) {\n      return null;\n    }\n    char curr = pre[preIndex++];\n    Node tNode;\n    tNode = new Node(curr);\n    if (inStrt == inEnd) {\n      return tNode;\n    }\n    tNode.left = buildTree( in , pre, inStrt, inIndex - 1);\n    tNode.right = buildTree( in , pre, inIndex + 1, inEnd);\n    return tNode;\n  }\n  public static Node buldTreeWrap(char[] in , char[] pre, int len) {\n    for (int i = 0; i &amp;lt; len; i++) {\n      mp.put( in [i], i);\n    }\n    return buildTree( in , pre, 0, len - 1);\n  }\n  static void printInorder(Node node) {\n    if (node == null) {\n      return;\n    }\n    printInorder(node.left);\n    System.out.print(node.data + \" \");\n    printInorder(node.right);\n  }<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def buildTree(inn, pre, inStrt, inEnd):\n \n    global preIndex, mp\n \n    if inStrt &amp;gt; inEnd:\n        return None\n \n    curr = pre[preIndex]\n    preIndex += 1\n    tNode = Node(curr)\n \n    if inStrt == inEnd:\n        return tNode\n \n    inIndex = mp[curr]\n \n    tNode.left = buildTree(inn, pre, inStrt, inIndex - 1)\n    tNode.right = buildTree(inn, pre, inIndex + 1, inEnd)\n \n    return tNode\n \n \ndef buldTreeWrap(inn, pre, lenn):\n \n    global mp\n \n    for i in range(lenn):\n        mp[inn[i]] = i\n \n    return buildTree(inn, pre, 0, lenn - 1)\n \n \ndef prInorder(node):\n \n    if node == None:\n        return\n \n    prInorder(node.left)\n    print(node.data, end=\" \")\n    prInorder(node.right)<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N), where N is the size of the two arrays<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(N), as hashmap is used.<\/p>\n\n\n\n<p id=\"-practice-questions-\"><strong>Practice Questions:<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/construct-binary-tree-from-inorder-and-preorder\/\" target=\"_blank\" rel=\"noreferrer noopener\">Construct Binary Tree From Inorder And Preorder<\/a><\/p>\n\n\n\n<h2 id=\"faq\">FAQ<\/h2>\n\n\n\n<ul><li><strong>What are preorder, inorder and postorder traversals?<br><\/strong>These are three types of DFS traversals:<br>1. Preorder &#8211; Traverses from ROOT -> LEFT -> RIGHT<br>2. Inorder &#8211; Traverses from LEFT -> ROOT -> RIGHT<br>3. Postorder &#8211; Traverses from LEFT -> RIGHT -> ROOT<br><br><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Given two arrays inorder[] and preorder[], which represents the inorder and the preorder traversal of a binary tree.&hellip;\n","protected":false},"author":5,"featured_media":4040,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[584],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3907"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3907"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3907\/revisions"}],"predecessor-version":[{"id":4046,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3907\/revisions\/4046"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4040"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3907"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3907"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3907"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}