added first number greater than k

david-legend · david-legend · commit fdfda1cecc17 · 2022-08-04T11:24:25.000Z
diff --git a/EPI_prep/src/binary_search_trees/2_find_first_key_greater_than_a_value_in_bst/README.md b/EPI_prep/src/binary_search_trees/2_find_first_key_greater_than_a_value_in_bst/README.md
@@ -0,0 +1,12 @@
+# Find the First Key Greater Than A Given Value In A BST
+
+<br>
+
+- Write a program that takes as input a BST and a value, and retums the first key that would appear in an inorder traversal which is greater than the input value. 
+For example, when applied to the BST in the Figure below, you should return 29 for input 23.
+
+### Example 1
+Input: tree, 23
+Output: 29
+
+![Binary Search Tree](../../../assets/bst.png)
diff --git a/EPI_prep/src/binary_search_trees/2_find_first_key_greater_than_a_value_in_bst/find_first_greater_than_k.py b/EPI_prep/src/binary_search_trees/2_find_first_key_greater_than_a_value_in_bst/find_first_greater_than_k.py
@@ -0,0 +1,56 @@
+# Best Case: Time O(n) | Space O(h)
+# 
+# Worst Case: Time O(n) | Space O(n)
+class TreeNode:
+    def __init__(self, val=None, left=None, right=None):
+        self.val = val
+        self.left = left
+        self.right = right
+
+def find_first_greater_than_than_k(tree, k):
+    subtree, first_so_far = tree, None
+    while subtree:
+        if subtree.val > k:
+            first_so_far, subtree = subtree, subtree.left
+        else:
+            subtree = subtree.right
+
+    return first_so_far
+
+
+    
+
+bst = TreeNode(19)
+bst_1 = TreeNode(7)
+bst_2 = TreeNode(43)
+bst_3 = TreeNode(3)
+bst_4 = TreeNode(11)
+bst_5 = TreeNode(23)
+bst_6 = TreeNode(47)
+bst_7 = TreeNode(2)
+bst_8 = TreeNode(5)
+bst_9 = TreeNode(17)
+bst_10 = TreeNode(37)
+bst_11 = TreeNode(53)
+bst_12 = TreeNode(13)
+bst_13 = TreeNode(29)
+bst_14 = TreeNode(41)
+bst_15 = TreeNode(31)
+
+bst.left, bst.right = bst_1, bst_2
+# Left Subtree
+bst_1.left, bst_1.right = bst_3, bst_4
+bst_3.left, bst_3.right = bst_7, bst_8
+bst_9.left, bst_4.right = bst_12, bst_9
+
+# Right Subtree
+bst_2.left, bst_2.right = bst_5, bst_6
+bst_5.right = bst_10
+bst_10.left, bst_10.right = bst_13, bst_14
+bst_13.right = bst_15
+bst_6.right = bst_11
+
+
+print(find_first_greater_than_than_k(bst, 2).val) # 3
+print(find_first_greater_than_than_k(bst, 23).val) # 29
+print(find_first_greater_than_than_k(bst, 53)) # None
diff --git a/EPI_prep/src/binary_search_trees/README.md b/EPI_prep/src/binary_search_trees/README.md
@@ -26,4 +26,8 @@ With a BST you can iterate through elements in sorted order in time O(n) (regard
 In this section we will solve common binary search tree questions that will help you understand the data structure very well. This will in turn give you the ability to solve other binary search questions
 
 * [Search Binary Tree](0_search_bst/search_bst.py)
+* [Check If Binary Search Tree Satisfies BST Property](1_check_if_bst_satisfies_bst_property/is_bst.py)
+    * [Check If Binary Search Tree Satisfies BST Property - Solution 2](1_check_if_bst_satisfies_bst_property/is_bst_2.py)
+* [Find the First Key Greater Than A Given Value In A BST](2_find_first_key_greater_than_a_value_in_bst/find_first_greater_than_k.py)
+
     
diff --git a/patterns/src/2_two_pointers/dutch_national_flag/README.md b/patterns/src/2_two_pointers/dutch_national_flag/README.md
@@ -8,7 +8,7 @@ red, white and blue; and since our input array also consists of
 three different numbers that is why it is called Dutch National Flag problem.
 
 ### Example 1
-nput: [1, 0, 2, 1, 0]
+Input: [1, 0, 2, 1, 0]
 Output: [0, 0, 1, 1, 2]
 
 
