Teaching Kids Programming – Revisit the Symmetric Binary Tree by Using Clone and Invert Algorithm


Teaching Kids Programming: Videos on Data Structures and Algorithms

We know how to invert a binary tree. We also learned how to check if a binary tree is symmetric. Today, we are going to take another look by using the Clone, Invert algorithms to check if a binary tree is symmetric.

A Binary Tree is Symmetric if and only if its Inverse is the same.

symmetric-binary-tree Teaching Kids Programming - Revisit the Symmetric Binary Tree by Using Clone and Invert Algorithm algorithms python Recursion teaching kids programming youtube video

Clone a Binary Tree

A Clone aka Copy returns a deep copy of a binary tree. We can do this recursively in O(N) time and O(N) space. Compared to Deep Copy, a Shallow Copy is like Creating an alias i.e. modifying the alias still modifies the original content.

1
2
3
4
5
6
7
def cloneBinaryTree(root):
  if root is None:
    return None
  newRoot = Tree(root.val)
  newRoot.left = cloneBinaryTree(root.left)
  newRoot.right = cloneBinaryTree(root.right)
  return newRoot
def cloneBinaryTree(root):
  if root is None:
    return None
  newRoot = Tree(root.val)
  newRoot.left = cloneBinaryTree(root.left)
  newRoot.right = cloneBinaryTree(root.right)
  return newRoot

Process of cloning a Tree: Create a Tree Node with the current root’s value, clone recursively its left and right tree. Then assign them to the New Node, and Return it.

Checking Equality of Two Binary Trees

Similar to cloning a binary tre, we can recursively check every node and every subtrees are the same:

1
2
3
4
5
def equalTree(a, b):
  if a is None and b is None:
    return True
  return a.val == b.val and equalTree(a.left, b.left) and \
         equalTree(a.right, b.right)
def equalTree(a, b):
  if a is None and b is None:
    return True
  return a.val == b.val and equalTree(a.left, b.left) and \
         equalTree(a.right, b.right)

Time complexity O(N). Space complexity is O(N).

Checking a Binary Tree is Symmetric

We then can clone the binary tree, and invert it, then check if it is the same as the original tree.

1
2
3
4
def isBinaryTreeSymmetric(root):
  copyTree = cloneBinaryTree(root)
  copyTree = invert(copyTree)
  return equalTree(copyTree, root)  
def isBinaryTreeSymmetric(root):
  copyTree = cloneBinaryTree(root)
  copyTree = invert(copyTree)
  return equalTree(copyTree, root)  

We can also do this without cloning the binary tree (if we allow modification of the binary tree): Just need to check the inverse of right sub tree is the same as left sub tree.

1
2
3
4
def isBinaryTreeSymmetric(root):
  if root is None:
    return True
  return equalTree(root.left, invert(root.right))
def isBinaryTreeSymmetric(root):
  if root is None:
    return True
  return equalTree(root.left, invert(root.right))

O(N) time, but should be slower than one-pass algorithm: Teaching Kids Programming – Recursive Algorithm to Determine if a Binary Tree is Symmetric

Algorithms to Check if a Binary Tree is Symmetric

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
728 words
Last Post: Math Algorithm to Count Substrings With All 1s
Next Post: Linked List Delete Last Occurrence of Value

The Permanent URL is: Teaching Kids Programming – Revisit the Symmetric Binary Tree by Using Clone and Invert Algorithm

Leave a Reply