Validate Binary Search Tree

 Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.


Not a valid Binary tree as 4 is less than 5.

Largest element in left subtree < root.val < Smallest element in left sub tree

Binary Tree Inorder traversal gives sorted elements.



Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

To solve this we will apply Depth First Search.

Code

class Solution {

    public TreeNode prev = null;

    public boolean isValidBST(TreeNode root) {               

        if(root==null) return true;        

        if(!isValidBST(root.left)) return false;        

        if(prev!=null && prev.val >= root.val) return false;        

        prev = root;                

        if(!isValidBST(root.right)) return false;        

        return true;

    }

}





Comments

Post a Comment

Popular posts from this blog

Java 8 : Find the number starts with 1 from a list of integers

  List<Integer> list = List. of ( 12 , 32 , 14 , 15 , 56 ); //Result->12,14,15 List<String> listString = list.stream().map(String::valueOf).collect(Collectors.toList()); List<String> result1 = listString.stream().filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result1-->" +result1); List<String> result2 = list.stream().map(x->x+ "" ).filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result2-->" +result2);
Read more

Junit Mockito and Power Mockito

Mock vs Spy Both can be used to mock methods or fields. The difference is that  in mock, you are creating a complete mock or fake object while in spy, there is the real object and you just spying or stubbing specific methods of it . Mock vs InjectMock @Mock  creates a mock.  @InjectMocks  creates an instance of the class and injects the mocks that are created with the  @Mock  (or  @Spy ) annotations into this instance. Unit Testing Void Methods with Mockito and JUnit How to Test Void Methods  As we already know that our aim is to test void methods in a class. But it is also really important to understand why we test void methods.  Whenever we write unit test cases for any method, we expect a return value from the method. Generally, we use assert for checking if the method returns the value that we expect it to return, but in the case of void methods, they do not return any value. So how do we check if our method is functioning properly? Let’s...
Read more

Important Linux Commands

  ls -lrt → command lists the contents of the directory with all the details, in reverse order of their modification time (older files will be displayed first) ls -lrth → This will list the contents of the current directory showing more information and sorting them so the most recently modified file will be displayed last. The h flag makes the file sizes more human friendly! chmod 755 <name> → chmod 755 sets the 755 permission for a file. 755 means full permissions for the owner and read and execute permission for others. ln -s 14.9.0-SNAPSHOT current → Create a current tag and mapped to current version. To link files in the same directory Update Any File → sed -i 's/10.46.87.148/10.46.87.115/g' journal.sch textToFind → 10.46.87.148 replaceText → 10.46.87.115 FileName → journal.sch . SED is a text stream editor used on Unix systems to edit files quickly and efficiently Untar a tar file → tar -xvzf filename.tar Rmove a folder → rm -r folderName netstat -anpe | grep ...
Read more