"""Leetcode 100. Same Tree
Easy

URL: https://leetcode.com/problems/same-tree/

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and
the nodes have the same value.

Example 1:
Input:     1         1
          / \       / \
         2   3     2   3
        [1,2,3],  [1,2,3]
Output: true

Example 2:
Input:     1         1
          /           \
         2             2
        [1,2],    [1,null,2]
Output: false

Example 3:
Input:     1         1
          / \       / \
         2   1     1   2
        [1,2,1],  [1,1,2]
Output: false
"""

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


class SolutionPreorderRecur(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool

        Time complexity: O(n).
        Space complexity: O(n).
        """
        # Apply recursive preorder traversal to check same tree.
        if not p and not q:
            return True

        if not p or not q:
            return False

        if p.val != q.val:
            return False

        return (self.isSameTree(p.left, q.left) and
                self.isSameTree(p.right, q.right))


class SolutionPreorderIter(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool

        Time complexity: O(n).
        Space complexity: O(n).
        """
        # Apply iterative preorder traversal to check same tree.
        stack = [(p, q)]

        while stack:
            cur_p, cur_q = stack.pop()

            if not cur_p and not cur_q:
                # Since there may be other node pairs to check.
                continue

            if not cur_p or not cur_q:
                return False

            if cur_p.val != cur_q.val:
                return False

            stack.append((cur_p.right, cur_q.right))
            stack.append((cur_p.left, cur_q.left))

        return True


def main():
    # Input:     1         1
    #           / \       / \
    #          2   3     2   3
    #         [1,2,3],  [1,2,3]
    # Output: true
    p = TreeNode(1)
    p.left = TreeNode(2)
    p.right = TreeNode(3)
    q = TreeNode(1)
    q.left = TreeNode(2)
    q.right = TreeNode(3)
    print SolutionPreorderRecur().isSameTree(p, q)
    print SolutionPreorderIter().isSameTree(p, q)

    # Input:     1         1
    #           /           \
    #          2             2
    #         [1,2],    [1,null,2]
    # Output: false
    p = TreeNode(1)
    p.left = TreeNode(2)
    q = TreeNode(1)
    q.right = TreeNode(2)
    print SolutionPreorderRecur().isSameTree(p, q)    
    print SolutionPreorderIter().isSameTree(p, q)

    # Input:     1         1
    #           / \       / \
    #          2   1     1   2
    #         [1,2,1],  [1,1,2]
    # Output: false
    p = TreeNode(1)
    p.left = TreeNode(2)
    p.right = TreeNode(1)
    q = TreeNode(1)
    q.left = TreeNode(1)
    q.right = TreeNode(2)
    print SolutionPreorderRecur().isSameTree(p, q)
    print SolutionPreorderIter().isSameTree(p, q)

    # Input: [10,5,15], [10,5,null,null,15]
    p = TreeNode(10)
    p.left = TreeNode(5)
    p.right = TreeNode(15)
    q = TreeNode(10)
    q.left = TreeNode(5)
    q.left.right = TreeNode(15)
    print SolutionPreorderRecur().isSameTree(p, q)
    print SolutionPreorderIter().isSameTree(p, q)


if __name__ == '__main__':
    main()

@@ -956,32 +956,96 @@
   :rtype: bool%0A%0A
+        Apply recursive preorder traversal to check same tree.%0A%0A
         Time com
@@ -1117,61 +1117,38 @@
   # 
-Apply recursive preorder traversal to check same tree
+Check if both root don't exist
 .%0A  
@@ -1194,24 +1194,68 @@
 eturn True%0A%0A
+        # Check if just one of roots exits.%0A
         if n
@@ -1287,32 +1287,91 @@
   return False%0A%0A
+        # If both exist, check their values are the same. %0A
         if p.val
@@ -1399,32 +1399,81 @@
   return False%0A%0A
+        # Recursively check left/right subtrees.%0A
         return (
@@ -1707,32 +1707,96 @@
   :rtype: bool%0A%0A
+        Apply iterative preorder traversal to check same tree.%0A%0A
         Time com
@@ -1858,73 +1858,8 @@
 %22%22%22%0A
-        # Apply iterative preorder traversal to check same tree.%0A
     
@@ -1957,40 +1957,53 @@
     
+# Check 
 if 
-not cur_p and not cur_q:%0A    
+both root don't exist, continue, %0A
     
@@ -2012,17 +2012,17 @@
       # 
-S
+s
 ince the
@@ -2074,21 +2074,109 @@
     
-    continue%0A
+if not cur_p and not cur_q:%0A                continue%0A%0A            # Check if just one of roots exits.
 %0A   
@@ -2233,32 +2233,95 @@
   return False%0A%0A
+            # If both exist, check their values are the same. %0A
             if c
@@ -2365,32 +2365,108 @@
   return False%0A%0A
+            # Add root's right and then left to stack, since stack is FILO.%0A
             stac

Add descriptive comments