K nearest Element in BST

K nearest Element in BST

  July 05, 2022    

---

Idea is to use a queue in inorder fashion which will make sure that the output is in sorted order

If queue size>=k which means we have to chek if first of the queue is not nearer to the current root element then poll from the queue and add current

 

 

 void KnearestElement(Node root, int k, int x, Queue<Integer> q)  {
    if(root == null)
    return ;
    KnearestElement(root.left, k, x, q);
    if(root.data !=x) {
    if(q.size()<k)
    q.add(root.data);
    else if(Math.abs(q.peek()-x)>Math.abs(root.data-x)) {
    q.poll();
    q.add(root.data);
    }}
    KnearestElement(root.right, k, x, q);
    }

Read More

Reverse LinkedList in group of K

Reverse LinkedList in group of K

  May 09, 2022    

---

Idea is to use recursion and reverse K list iteratively and use recursive method to link k diff. reversed linkedList

 

Solution :

public static Node reverse(Node head, int k)
    {
        if(head == null) return head;
        int cur = 0;
    Node itr = head;
    Node next = null;
    Node prev = null;
    while(cur<k && itr!=null) {
        next = itr.next;
        itr.next = prev;
        prev = itr;
        itr = next;
        ++cur;
    }
    head.next = reverse(itr, k);
    return prev;
  }

Read More

Sum of Nodes with Even-Valued Grandparent Java Solution

Sum of Nodes with Even-Valued Grandparent Java Solution

  May 03, 2022    

---

Problem:

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent

 

 Solution: 

public int sumEvenGrandparent(TreeNode root) {
        ArrayList<TreeNode> list = new ArrayList<>();
        fillList(root, list);
        int res = 0;
        for(TreeNode node: list) {
            res+= getSumOfGrandChild(node, 2);
        }
        return res;
    }
    public void fillList(TreeNode root, ArrayList<TreeNode> list) {
        if(root == null) return;
        if(root.val%2==0)
            list.add(root);
        fillList(root.left, list);
        fillList(root.right, list);
    }
    public int getSumOfGrandChild(TreeNode root, int depth) {
        if(root == null ) return 0;
        if(depth == 0) return root.val;
        if(depth < 0) return 0;
        return getSumOfGrandChild(root.left, depth-1) + getSumOfGrandChild(root.right, depth-1);
    }

Read More

Deepest Leaves Sum Java Solution

Deepest Leaves Sum Java Solution

  May 03, 2022    

---

Problem:

Given the root of a binary tree, return the sum of values of its deepest leaves.

 

Solution:

 Idea is to use BFS/ Level order Traversal

public int deepestLeavesSum(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        int curSum = 0;
        int maxSum = Integer.MIN_VALUE;
        q.add(root);
        q.add(null);
        while(!q.isEmpty()) {
            TreeNode node = q.poll();
            if(node == null) {
                maxSum = curSum;
                curSum = 0;
                if(q.isEmpty()) break;
                q.add(null);
                continue;
            }
            curSum+=node.val;
            if(node.left!=null)
            q.add(node.left);
            if(node.right!=null)
            q.add(node.right);
        }
        return maxSum;
    }

Read More

Corresponding Node of a Binary Tree in a Clone Tree Solution

Corresponding Node of a Binary Tree in a Clone Tree Solution

  May 03, 2022    

---

Problem:

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

 

 Solution:

public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if(original == null) return null;
        if(original.val == target.val) return cloned;
        TreeNode left = getTargetCopy(original.left, cloned.left, target);
        TreeNode right = getTargetCopy(original.right, cloned.right, target);
        return left!=null?left:right;
    }

Read More

Remove Element Java Solution

Remove Element Java Solution

  May 02, 2022    

---

 Problem :

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k

Solution:

 public int removeElement(int[] nums, int val) {
        int count =0;
        int i =0;
        while(i<nums.length) {
            if(nums[i] != val) {
                nums[count++] = nums[i];
            }
            ++i;
        }
        return count;
    }

Read More

Valid Parentheses Java Solution

Valid Parentheses Java Solution

  May 02, 2022    

---

Problem:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

    Open brackets must be closed by the same type of close brackets.
    Open brackets must be closed in the correct order.
 

 

 Solution:

class Solution {
    public boolean isValid(String s) {
     Stack<Character> stack = new Stack<>();
        for(int i=0;i<s.length();++i) {
            if(openingBracket(s, i)) {
                stack.push(s.charAt(i));
            }
            else {
                if(stack.isEmpty()) return false;
                char element = stack.pop();
                if(!OpeningOf(element,s.charAt(i))) return false;
            }
        }
        return stack.isEmpty();
    }
    public boolean openingBracket(String s, int i) {
        char bracket = s.charAt(i);
        if(bracket == '[' || bracket == '(' || bracket == '{' )
            return true;
        return false;
    }
    public boolean OpeningOf(char x, char y) {
        switch(y) {
            case ']' : return x == '[';
            case ')' : return x == '(';
            case '}' : return x == '{';
        }
        return false;
    }
}

Read More