Teaching Kids Programming – Recursive Algorithm to Determine if a Binary Tree is Symmetric

ACMer

4 years ago

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the root to a binary tree root, return whether it is symmetric.

Constraints
n ≤ 100,000 where n is the number of nodes in root

Recursive Algorithm to Check if A Binary Tree is Symmetric

One way of thinking a binary tree is symmetric is that its left and right sub trees are mirrored. Then, we can define a recursive function to check if two sub trees are symmetric.

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetricTree(self, root):
        if root is None:
            return True
        def symmetric(a, b):
            if a is None and b is None:
                return True
            if a is None or b is None:
                return False
            return a.val == b.val and symmetric(a.left, b.right) and symmetric(a.right, b.left)
        return symmetric(root.left, root.right)

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetricTree(self, root):
        if root is None:
            return True
        def symmetric(a, b):
            if a is None and b is None:
                return True
            if a is None or b is None:
                return False
            return a.val == b.val and symmetric(a.left, b.right) and symmetric(a.right, b.left)
        return symmetric(root.left, root.right)

Time complexity is O(N) where N is the number of the nodes in the given binary tree.

Algorithms to Check if a Binary Tree is Symmetric

–EOF (The Ultimate Computing & Technology Blog) —

449 words
Last Post: Depth First Search Algorithm to Perform Phone Number Permutations
Next Post: Math Algorithm to Count Substrings With All 1s

The Permanent URL is: Teaching Kids Programming – Recursive Algorithm to Determine if a Binary Tree is Symmetric (AMP Version)

Recursive Algorithm to Check if A Binary Tree is Symmetric

Algorithms to Check if a Binary Tree is Symmetric

Related posts: