Validate Binary Search Tree O(1) Space

Validate Binary Search Tree O(1) Space

  November 02, 2026    

---

 

We know that inorder traversal of the BST is strictly increasing and we can put inorder traversal in the array and compare it. 

You can actually do this in O(1) space. You don't need the whole array.

you just need to track the last visited node and compare it to the current one as you traverse.

The main edge case to watch out for is the starting value. If you initialize lastVisited to Integer.MIN_VALUE, your code will fail on test cases where the tree actually contains Integer.MIN_VALUE. The cleanest fix is throwing in an isFirstFound boolean to skip the comparison on the very first node.

 

 

Code: 

int lastVisited = Integer.MIN_VALUE; //This arbitary value is part of test case so we need to identify the first value of the Tree;

boolean isFirstFound = false;

public boolean isValidBST(TreeNode root) {

if(root==null) return true;

boolean left = isValidBST(root.left);

if(isFirstFound && lastVisited>=root.val) return false;

isFirstFound = true;

lastVisited = root.val;

return left && isValidBST(root.right);

}  

Read More

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