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.
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
- Teaching Kids Programming – Iterative Algorithm to Check if a Binary Tree is Symmetric
- Teaching Kids Programming – Revisit the Symmetric Binary Tree by Using Clone and Invert Algorithm
- Teaching Kids Programming – Recursive Algorithm to Determine if a Binary Tree is Symmetric
- How to Check Symmetric Tree in C++ (Iterative and Recursion)?
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Math Algorithm to Count Substrings With All 1s
Next Post: Linked List Delete Last Occurrence of Value