Title:

Symmetric Binary Tree - Strategy 2

Specification:

Given a binary tree, check whether it is a mirror of itself (i.e.; it is symmetric around its center.)

Examples:

Example 1:

This binary tree [1,2,2,3,4,4,3] is symmetric.

Example 2:

But the following [1,2,2,null,3,null,3] is not.

Initial Code and Signature:

public class SymmetryCheckerV3 {

public boolean isSymmetric(TreeNode root) {

}

}

Algorithm:

Recursive Version:

1. Divide the tree into Left-Tree and Right-Tree
2. Left Traverse Left Tree recursively
3. Right Traverse Right Tree recursively
4. Check whether the sequence obtained from both traversals are equal.
leftTraverse / rightTraverse:
1. Meet left child / Meet right child
2. Meet right child / Meet left child
3. Meet root / Meet root
or
1. Meet left child / Meet right child
2. Meet root / Meet root
3. Meet right child / Meet left child

Run-Time Analysis:

GitHub Project:

Code:

import java.util.*;
/**
*
* @since 2020-02-13
*
*/

public class SymmetryCheckerV3 implements SymmetryChecker  {
/**
* Symmetry Checker Version 3:
*
* Recursive Algorithm:
*
* 1- Divide the tree into Left-Tree and Right-Tree
* 2- Left Traverse Left Tree recursively
* 3- Right Traverse Right Tree recursively
* 4- Check whether the sequence obtained from both traversals are equal.
*
*
* leftTraverse / rightTraverse:
*
* 1-meet left child / meet right child
* 2-meet right child / meet left child
* 3-mild root / meet root
*
* or
*
* 1-meet left child / meet right child
* 2-meet root / meet root
* 3-meet right child / meet left child
*/

List lTResult;
List rTResult;

public boolean isSymmetric(TreeNode root) {

lTResult = new ArrayList();
rTResult = new ArrayList();

TreeNode lr, rr;

if ( root == null)
return true;

else {
lr = root.getLeftChild();
rr = root.getRightChild();

if (lr == null) {
if (rr == null)
return true;

else
return false;
}

else if (rr == null) {
if (lr == null)
return true;

else
return false;
}

else if (lr.getValue() != rr.getValue())
return false;

else {
leftTraverse(lr);
rightTraverse(rr);

return isEqual(lTResult, rTResult);
}
}

}

public boolean isEqual(List l1, List l2) {

if (l1.size() != l2.size())
return false;
else {
for (int i = 0; i < l1.size(); i++)
if (l1.get(i) != l2.get(i))
return false;
}

return true;
}

public void leftTraverse(TreeNode root) {

if (root == null)

else if (isLeaf(root))

else {
TreeNode lc = root.getLeftChild();

if (lc != null)
leftTraverse(lc);
else

TreeNode rc = root.getRightChild();

if (rc != null)
leftTraverse(rc);
else

}

}

public void rightTraverse(TreeNode root) {

if (root == null)

else if (isLeaf(root))

else {
TreeNode rc = root.getRightChild();

if (rc != null)
rightTraverse(rc);
else

TreeNode lc = root.getLeftChild();

if (lc != null)
rightTraverse(lc);
else