Grind75 Notes
  • README
  • week-1
    • Two Sum
    • Valid Parentheses
    • Merge Two Sorted Lists
    • Best Time to Buy and Sell Stock
    • Valid Palindrome
    • Invert Binary Tree
    • Valid Anagram
    • Binary Search
    • Flood Fill
    • Lowest Common Ancestor of a Binary Search Tree
    • Balanced Binary Tree
    • Linked List Cycle
    • Implement Queue using Stacks
  • week-2
    • First Bad Version
    • Ransom Note
    • Climbing Stairs
    • Longest Palindrome
    • Reverse Linked List
    • Majority Element
    • Add Binary
    • Diameter of Binary Tree
    • Middle of the Linked List
    • Maximum Depth of Binary Tree
    • Contains Duplicate
    • Maximum Subarray
  • week-3
    • Insert Interval
    • 01 Matrix
    • K Closest Points to Origin
    • Longest Substring Without Repeating Characters
    • 3Sum
    • Binary Tree Level Order Traversal
    • Clone Graph
    • Evaluate Reverse Polish Notation
  • week-4
    • Course Schedule
    • Implement Trie (Prefix Tree)
    • Coin Change
    • Product of Array Except Self
    • Min Stack
    • Validate Binary Search Tree
    • Number of Islands
    • Rotting Oranges
  • week-5
    • Search in Rotated Sorted Array
    • Combination Sum
    • Permutations
    • Merge Intervals
    • Lowest Common Ancestor of a Binary Tree
    • Time Based Key-Value Store
    • Accounts Merge
    • Sort Colors
  • week-6
    • Word Break
    • Partition Equal Subset Sum
    • String to Integer (atoi)
    • Spiral Matrix
    • Subsets
    • Binary Tree Right Side View
    • Longest Palindromic Substring
    • Unique Paths
    • Construct Binary Tree from Preorder and Inorder Traversal
  • week-7
    • Container With Most Water
    • Letter Combinations of a Phone Number
    • Word Search
    • Find All Anagrams in a String
    • Minimum Height Trees
    • Task Scheduler
    • LRU Cache
  • week-8
    • Kth Smallest Element in a BST
    • Minimum Window Substring
    • Serialize and Deserialize Binary Tree
    • Trapping Rain Water
    • Find Median from Data Stream
    • Word Ladder
    • Basic Calculator
    • Maximum Profit in Job Scheduling
    • Merge k Sorted Lists
    • Largest Rectangle in Histogram
Powered by GitBook
On this page
  • Problem
  • Pseudocode
  • Solution
  • Time and Space Complexity
  1. week-6

Construct Binary Tree from Preorder and Inorder Traversal

PreviousUnique PathsNextweek-7

Last updated 2 years ago

Problem

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary 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]

Pseudocode

- piece together information from two outputs
    - preorder shows left branch first
    - inorder shows left-root-right

Solution

// from solutions, much clearer
var buildTree = function (preorder, inorder) {
  const inorderMap = {};
  let currPreorder = 0;

  inorder.forEach((el, idx) => {
    if (!(el in inorderMap)) {
      inorderMap[el] = idx;
    }
  });

  console.log(inorderMap);

  function dfs(left, right) {
    if (left > right) return null;

    // take currVal

    const currVal = preorder[currPreorder];
    currPreorder++;
    //   console.log(currVal, `indexOf ${preorder.indexOf(currVal)}, ${currPreorder}`)
    const node = new TreeNode(currVal);

    // find idx in inordermap and assign - 1 and + 1 for left and right node respectively
    node.left = dfs(left, inorderMap[currVal] - 1);
    node.right = dfs(inorderMap[currVal] + 1, right);

    return node;
  }

  return dfs(0, inorder.length - 1);
};

Time and Space Complexity

Time

  • What did the code do

  • Total -

Space

  • What did the code do

  • Total -

Loading...LeetCode
Logo