SHARE
TWEET

Untitled

a guest Sep 18th, 2019 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Code assembles a Binary Tree using depth first traversal, taking in the inorder and postorder of the tree to create it
  2. //Definition of a Tree Node
  3. //function TreeNode(val) {
  4. //    this.val = val;
  5. //    this.right = this.left = null;
  6. //}
  7.  
  8. const buildTree = function(inorder, postorder) {
  9.   let hashmap = [];
  10.   let post_index = postorder.length - 1;
  11.   let in_left = 0;
  12.   let in_right = postorder.length - 1;
  13.   for(let val in inorder) {
  14.     hashmap.push(inorder[val]);
  15.  
  16.   return helper(in_left, in_right);
  17.  
  18.   function helper(in_left, in_right) {
  19.     if(in_left > in_right) return null;
  20.    
  21.     //Find the value of the node, create the new node
  22.     let root_val = postorder[post_index];
  23.     let root = new TreeNode(root_val);
  24.    
  25.     let index = hashmap.indexOf(root_val);
  26.    
  27.     //Recursively use the helper function to add nodes to the tree.
  28.     //Base case above will return null because the length of the array won't exist
  29.     post_index--;
  30.     //right first because of post order
  31.     root.right = helper(index + 1, in_right);
  32.     root.left = helper(in_left, index - 1);
  33.     //Root returns the first root so we can observe the tree
  34.     return root;
  35.  }
  36.  
  37. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top