We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Practice
  2. Tutorials
  3. Cracking the Coding Interview
  4. Trees: Is This a Binary Search Tree?
  5. Discussions

Trees: Is This a Binary Search Tree?

Problem
Submissions
Leaderboard
Discussions
Editorial

    You are viewing a single comment's thread. Return to all comments →

  • GhostlyMowgli 3 years ago+ 0 comments

    I never know if I'm supposed to/"allowed" to create secondary functions to use within the function they want me to define.

    I love the simplicity of using just the maximum and minimum of earlier parent nodes; I'm not 100% sure there wouldn't be any issues, but conceptually/theoretically (as far as I can see/think) it makes sense.

    Since I took a somewhat different approach to anything I've seen here, I thought I'd include it here for anyone interested. I also welcome feedback, if anyone has anything to point out about what could be improved.

        parents = []
        sides = []
        def checkBST(root):
                # compare current node to all the parents 
                # (don't forget we can't have equal nodes either!)
                for i in range(len(parents)):
                        if sides[i] == 'left':
                                if root.data >= parents[i].data:
                                        return False
                        else:
                                if root.data <= parents[i].data:
                                        return False
    
                # compare current node to its children & go deeper
                status = True
                # I use this to check the left side and only return False
                # if we know it's not a BST, but if it is so far,
                # we want to continue and look on the right side
                if root.left:
                        if root.left.data < root.data:
                                parents.append(root)
                                sides.append('left')
                                status = checkBST(root.left)
                                parents.pop()
                                sides.pop()
                                if status == False:
                                        return status
                        else:
                                return False
                if root.right:
                        if root.right.data > root.data:
                                parents.append(root)
                                sides.append('right')
                                status = checkBST(root.right)
                                parents.pop()
                                sides.pop()
                        else:
                                return False
    
                return status
    

    The idea is to note which direction I've gone down from a parent, so I know whether that node needs to be larger/smaller than each respective parent. I think the overall time complexity should be n * log n...right? (n from going through each node, and log n from each node's looking at the parents.) Again, I welcome any feedback on this approach.

    0|
    ParentPermalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature