advance tree questions

kunal-kushwaha · web-flow · commit da8252071bf7 · 2023-12-04T11:53:12.000+05:30
diff --git a/lectures/20-trees/code/Advance questions/KthSmallest.java b/lectures/20-trees/code/Advance questions/KthSmallest.java
@@ -0,0 +1,25 @@
+class KthSmallest {
+  public int kthSmallest(TreeNode root, int k) {
+    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
+    helper(root, minHeap, k);
+
+    // remove k elements
+    int ans = 0;
+    for(int i=0; i<k; i++) {
+      ans = minHeap.poll();
+    }
+    return ans;
+  }
+
+  private void helper(TreeNode node, PriorityQueue<Integer> minHeap, int k) {
+    if (node == null) {
+      return;
+    }
+
+    helper(node.left, minHeap, k);
+
+    minHeap.offer(node.val);
+    
+    helper(node.right, minHeap, k);
+  }
+}
diff --git a/lectures/20-trees/code/Advance questions/KthSmallest2.java b/lectures/20-trees/code/Advance questions/KthSmallest2.java
@@ -0,0 +1,26 @@
+class KthSmallest {
+  private int k;
+  private int ans;
+  
+  public int kthSmallest(TreeNode root, int k) {
+    this.k = k;
+    helper(root);
+    return ans;
+  }
+
+  private void helper(TreeNode node) {
+    if (node == null) {
+      return;
+    }
+
+    helper(node.left);
+
+    k--;
+    if(k==0) {
+      ans = node.val;
+      return;
+    }
+    
+    helper(node.right);
+  }
+}
diff --git a/lectures/20-trees/code/Advance questions/TwoSum.java b/lectures/20-trees/code/Advance questions/TwoSum.java
@@ -0,0 +1,17 @@
+class TwoSum {
+  public boolean findTarget(TreeNode root, int k) {
+    HashSet<Integer> set = new HashSet<>();
+    return helper(root, k, set);
+  }
+  private boolean helper(TreeNode node, int k, HashSet<Integer> set) {
+    if(node == null) {
+      return false;
+    }
+    if(set.contains(k - node.val)) {
+      return true;
+    }
+
+    set.add(node.val);
+    return helper(node.left, k, set) || helper(node.right, k , set);
+  }
+}
