{"id":1130,"date":"2020-12-06T10:26:53","date_gmt":"2020-12-06T10:26:53","guid":{"rendered":"https:\/\/blog.samarthya.me\/wps\/?p=1130"},"modified":"2020-12-06T10:26:54","modified_gmt":"2020-12-06T10:26:54","slug":"building-a-tree-from-traversal","status":"publish","type":"post","link":"https:\/\/blog.samarthya.me\/wps\/2020\/12\/06\/building-a-tree-from-traversal\/","title":{"rendered":"Building a tree from Traversal."},"content":{"rendered":"\n

What good is an software engineer if he can’t keep revisiting the DS problems. It is like a pill for my laziness that keeps crawling ever so often.<\/p>\n\n\n\n

The problem I am talking about is mentioned in this cool portal exercism.io<\/a><\/code> that I use almost on a weekly basis.<\/p><\/blockquote>\n\n\n\n

The problem was to construct a tree from the inorder and preorder traversal.<\/p>\n\n\n\n

In Order = LVR<\/p>

Pre Order = VLR<\/p>Where L = Left, V = Vertex and R = Right<\/cite><\/blockquote><\/figure>\n\n\n\n

The complexity is basically recursively finding the root of the tree\/subtree and the left and right subtree and managing the relations downwards or upwards.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

The Logic is a multi step process<\/p>\n\n\n\n

  1. Identify the root
    • The first element in the preorder traveral is always the root.<\/li><\/ul><\/li>
    • Identify the left and the right subtree.
      • The elements from left to the index of root in the inorder are the left subtree<\/li>
      • The elements from the right of the index of the root in the inorder are the right subtree.<\/li><\/ul><\/li>
      • Identify the root of the subsequent subtree.<\/li><\/ol>\n\n\n\n

        Let’s look at our example<\/p>\n\n\n\n

            private Node buildNodes(List<Character> preOrder, List<Character> inOrder) {\n\n        \/\/ If any of the tree is empty return null.\n        if(preOrder.isEmpty() || inOrder.isEmpty()){\n            return null;\n        }\n\n        \/\/ Root is always the first element in InOrder\n        Node root = new Node(preOrder.get(0).charValue());\n       \n\n        \/\/ The Index of the root i identifies the Left and Right Subtree\n        \/\/ 0 - i-1 is left and i+1 - n is the Right subtree\n        int iRoot = inOrder.indexOf(preOrder.get(0));\n\n        \n\n        \/\/ Build the left tree first\n        root.left = buildNodes(preOrder.subList(1, preOrder.size()), inOrder.subList(0, iRoot));\n\n        \/\/ Build the right tree\n        root.right = buildNodes(preOrder.subList(iRoot + 1, preOrder.size()), inOrder.subList(iRoot+1, inOrder.size()));\n\n        return root;\n    }<\/code><\/pre>\n\n\n\n
        What do you think what more can I optimise?<\/p>\n","protected":false},"excerpt":{"rendered":"
        What good is an software engineer if he can’t keep revisiting the DS problems. It is like a pill for my laziness that keeps crawling ever so often. The problem I am talking about is mentioned in this cool portal exercism.io that I use almost on a weekly basis. The problem was to construct a […]<\/p>\n","protected":false},"author":2,"featured_media":1132,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"image","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[34],"tags":[121,116,125],"class_list":["post-1130","post","type-post","status-publish","format-image","has-post-thumbnail","hentry","category-technical","tag-java","tag-technical","tag-tree","post_format-post-format-image"],"_links":{"self":[{"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/posts\/1130","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/comments?post=1130"}],"version-history":[{"count":0,"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/posts\/1130\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/media\/1132"}],"wp:attachment":[{"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/media?parent=1130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/categories?post=1130"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/tags?post=1130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}