Construct Binary Search Tree from Preorder Traversal

-
Problem is here: https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val.  Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Note: 
  1. 1 <= preorder.length <= 100
  2. The values of preorder are distinct.

This is a relatively simple problem, although labeled as Medium. The definition of a binary search tree is even given in the problem description. A recursive solution does the trick: add the first node, then call recursively for the left by creating a sub-array with the smaller elements, and similar to the right. That should do it. Conversion of linked-lists to arrays in C# is not the most efficient operation, hence the execution time slows down a bit. Code is below, cheers, ACC.


public class Solution
{
 public TreeNode BstFromPreorder(int[] preorder)
 {
  if (preorder == null || preorder.Length == 0) return null;
  TreeNode tree = new TreeNode(preorder[0]);
  LinkedList left = new LinkedList();
  int i = 1;
  for (; i < preorder.Length && preorder[i] < preorder[0]; i++)
  {
   left.AddLast(preorder[i]);
  }
  LinkedList right = new LinkedList();
  for (; i < preorder.Length; i++)
  {
   right.AddLast(preorder[i]);
  }
  tree.left = BstFromPreorder(left.ToArray());
  tree.right = BstFromPreorder(right.ToArray());
  return tree;
 }
}

Comments

  1. TarasMay 7, 2019 at 7:50 PM

    Neat! I've used a very similar approach, which runs a lot faster on any non-C# languages it seems like (Python code below runs in 36s and beats 100% of other submissions) :) Seriously speaking though, I think the reason for the slow runtime of your submission is usage of LinkedList - I bet just by replacing it with ArrayList you'd get a significantly better performance. LinkedList has a terrible effect on caches (non-contiguous memory) and uses more memory (thanks to pointers). LinkedLists are so bad that many advocate for their removal from standard libraries :)

    class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
    if not preorder:
    return None
    root = TreeNode(preorder[0])
    first_right_child_idx = len(preorder)
    for idx, node in enumerate(preorder):
    if node > root.val:
    first_right_child_idx = idx
    break
    root.left = self.bstFromPreorder(preorder[1:first_right_child_idx])
    root.right = self.bstFromPreorder(preorder[first_right_child_idx:])
    return root


    https://gist.github.com/ttsugriy/849ae99d210ff775a0b094ec03beb361

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more