Friday, January 16, 2015

Validate Binary Search Tree (LeetCode Tree)

Question: Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a 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.

Idea: In order traversal. If the previous node is larger or equal to the current node, return false and terminate the traversal.

Time: O(n) Space: O(lgn)

Code:
 public class Solution {  
   int prev;  
   boolean firstNode;  
   public boolean isValidBST(TreeNode root) {  
     firstNode=true;  
     return inorder(root);  
   }  
   public boolean inorder(TreeNode cur)  
   {  
     if(cur==null)  
       return true;  
     if(inorder(cur.left)==false)  
       return false;  
     if(!firstNode&&prev>=cur.val)  
       return false;  
     prev=cur.val;  
     firstNode=false;  
     if(inorder(cur.right)==false)  
       return false;  
     return true;  
   }  
 }  

No comments:

Post a Comment