Construct Binary Tree from Preorder & Inorder

Construct Binary Tree from Preorder and Inorder Traversal

You are given two integer arrays preorder and inorder.

• preorder is the preorder traversal of a binary tree
• inorder is the inorder traversal of the same tree
• Both arrays are of the same size and consist of unique values.

Rebuild the binary tree from the preorder and inorder traversals and return its root.

Example 1:

Input: preorder = [1,2,3,4], inorder = [2,1,3,4]

Output: [1,2,3,null,null,null,4]

Example 2:

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

Output: [1]

One thing i've come to the conclusion is that, after solving these many leetcode question. Every problem can be solved with a solution that is elegant and intuitive i.e easy to comprehend. Code can be written in a level that could a poem to the reader.

For example this question ask us to build a binary tree. A tree has a node that has left node and right node at each node. So based on this we can solve the problem.

Here we can already sense that it's a recursive problem.

function buildTree(preOrder, inOrder){
 const myNode = new Node()
 myNode.left = buildTree()
 myNode.right = buildTree()
}

Now, the question is how can we utilize our PreOrder and InOrder to solve this question?

1. 0th index of preOrder is always our root node
2. Next we search where our rootNode lies in the inorder
3. which gives use all the nodes to the left of the root i,e left sub tree
4. gives the right sub tree array

Here in the image: we are given preOrder and inOrder, we see 3 is the root node.

1. we find our leftTree Node and right Tree Node of our root

The key is: At each step, preorder tells us the root, and inorder tells us what's left and right of that root.

function build(preOrder, inOrder){
  if(!preOrder.length || !inOrder.length){
    return null
   }
  let node =  new TreeNode(preOrder[0])
  let mid = inOrder.indexOf(preOrder[0])

   node.left = build(
    preOrder.slice(1 , mid + 1),
    inOrder.slice(0, mid)
   )
   node.right = build(
    preOrder.slice(mid + 1),
    inOrder.slice(mid + 1)
   )
   return node
}

A simple point to be noted here even if just

  if(!preOrder.length || !inOrder.length){
    return null
   }

vs

  if(!preOrder.length || !inOrder.length){
    return  
   }

Most of the nodes constructor expects null not undefined if we the node does not exist.