Validate a BST in Python Leetcode

Question

I was attempting to solve Validate Binary Search Tree in Leetcode.

My approach was to do a inOrder Traversal , and add the data to a list. Now I will try to sort the list and compare with the original list to check if the BST is valid or not.

However while running the code in leet code even though my logic is correct and works properly in Jupiter Notebook, the same logic doesn't seem to work in Leetcode.

My code :

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root:
            stk = self.inOrder(root,[])
            old_stk = stk
            print(old_stk)
            stk.sort()
            print(stk)
            for i,j in zip(old_stk,stk):
                if i!= j:
                    print('{} :: {}'.format(i,j))
                    return False
                else:
                     print('{} :: {}'.format(i,j))
        return True
            
            
    def inOrder(self,root,trav):
        
        if root:
            trav = self.inOrder(root.left,trav)
            trav.append(root.val)
            trav = self.inOrder(root.right,trav)
        return trav

STD OP for old_stk and stk:

[1, 5, 3, 4, 6]
[1, 3, 4, 5, 6]
1 :: 1
3 :: 3
4 :: 4
5 :: 5
6 :: 6

It is clear that both the list or not same, I tried using return stk == old_stk and also iterating element by element, but I am getting the wrong output.

Is my logic correct , or can anyone point out where I have gone wrong ?

Thanks !

user_7769239 · Answer

The problem lies in the shallow copy of the list, specifically old_stk = stk this line.

With your current implementation, if you print the old_stk after the sort, it should be changed as well.

       if root:
            stk = self.inOrder(root,[])
            old_stk = stk 
            print(old_stk)               # [1, 5, 3, 4, 6]
            stk.sort()
            print(stk)                   # [1, 3, 4, 5, 6]
            print(old_stk)               # [1, 3, 4, 5, 6]
            .......
            .......
        return True

So, deep copying the list should generate the correct output for the following input [5,1,4,null,null,3,6].

class Solution(object):
    
    def isValidBST(self, root):
        if root:
            stk = self.inOrder(root,[])
            old_stk = stk[:]   # Deep copy
            stk.sort()
            for i,j in zip(old_stk, stk):
                if i!= j:
                    return False
        return True
            
    def inOrder(self, root, trav):
        if root:
            trav = self.inOrder(root.left,trav)
            trav.append(root.val)
            trav = self.inOrder(root.right,trav)
        return trav

With that portion solved, when answering,

Is my logic correct?

Actually still, it is incorrect. For input, [2, 2, 2] will give the wrong value. Checking the left value is always smaller, and the right value is always bigger should fix it. Plenty of solutions are available.

Validate a BST in Python Leetcode

1 Answers