BST from Preorder and Inorder Traversals

Construct Binary tree from given preorder and inorder traversals of the tree.

Example 1:

 Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Solution:

   function TreeNode(val, left, right) {
       this.val = (val===undefined ? 0 : val)
       this.left = (left===undefined ? null : left)
       this.right = (right===undefined ? null : right)
   }

 var buildTree = function(preorder, inorder) {
     
     if(preorder.length==0)return null;
     
     var root = new TreeNode(preorder[0]);
     
     var inPos = inorder.indexOf(preorder[0]);
     root.left = buildTree(preorder.slice(1, inPos+1), inorder.slice(0, inPos));
     root.right = buildTree(preorder.slice(1+inPos), inorder.slice(inPos+1));
     
     return root;
 };

BST Construction: Link

Sample tree:

           5
        /     \
       2       9
    /     \      \
    1     3       10

Given traversals:

In order: [1, 2, 3, 5, 9, 10]
Pre order: [5, 2, 1, 3, 9, 10]

Recursive:

var inorderTraversal = [1, 2, 3, 5, 9, 10];
var preorderTraversal = [5, 2, 1, 3, 9, 10];

function createNode(inorder, preorder) {
  if (inorder.length == 0) return null;

  var inorderPosition = inorder.indexOf(preorder[0]);

  var node = new TreeNode(preorder[0]);
  node.left = createNode(
    inorder.slice(0, inorderPosition),
    preorder.slice(0, inorderPosition)
  );
  node.right = createNode(
    inorder.slice(inorderPosition),
    preorder.slice(inorderPosition)
  );

  return node;
}

var root = createNode(inorderTraversal, preorderTraversal);

Written by Gagandeep Rangi who likes to talk about himself in third person. Twitter Instagram