Question on Check Valid Sequence in a Binary Tree from root to leaf
jjaganna
268

I have come up with a non-recursive solution, but it was accepted for only 55 out of 63 cases.
I would like to know why it failed. Here is my code:

'''

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

class Solution:
def isValidSequence(self, root: TreeNode, arr: List[int]) -> bool:
if not arr and not root:
return(True)
elif not arr:
return(False)
elif not root:
return(False)

    n = len(arr)
    if arr[0] != root.val:
        return(False)

    for i in range(1, n):
        if root.left and arr[i] == root.left.val:
            root = root.left
        elif root.right and arr[i] == root.right.val:
            root = root.right
        else:  # root has no child but arr has an element
            return(False)
        
    # We have reached the end of arr. Check if the root is a leaf
    if root.left == None and root.right == None:
        return(True)
    
    return(False)

'''

Comments (2)