GitHub Account Google Scholar Account LinkedIn Account Twitter Account flickr Account vialab Research Group Profile Page

Determining if a Tree is Symmetric

Date: May 21, 2016
This algorithm works for binary trees as well as for trees with more than two children.
import java.util.LinkedList;

public class SymmetricTree {

    public static void main(String[] args) {

        Node root = new Node(0);
        setupTree(root);

        boolean flag = isSymmetric(root);
        System.out.println("Tree is symmetric?: " + flag);
    }

    public static boolean isSymmetric(Node root) {
        return isSymmetric(root, root);
    }

    public static boolean isSymmetric(Node nodeLeft, Node nodeRight) {

        if (nodeLeft == null && nodeRight == null) {
            return true;

        } else if (nodeLeft == null || nodeRight == null
            || (nodeLeft.children.size() != nodeRight.children.size())) {

            return false;

        } else if (nodeLeft.value == nodeRight.value) {

            int num = nodeLeft.children.size();
            boolean flag = true;

            for (int i = 0, j = num - 1; i < j; i++, j--) {

                Node left = nodeLeft.children.get(i);
                Node right = nodeRight.children.get(j);

                flag = flag && isSymmetric(left, right);

                if (!flag) {
                    return false;
                }
            }

            if (num % 2 != 0) {

                int index = num / 2;
                Node midLeft = nodeLeft.children.get(index);
                Node midRight = nodeRight.children.get(index);

                flag = flag && isSymmetric(midLeft, midRight);
            }

            return flag;
        }

        return false;
    }

    public static void setupTree(Node root) {

        Node leftChild = new Node(1);
        Node midChild = new Node(2);
        Node rightChild = new Node(1);

        root.children.add(leftChild);
        root.children.add(midChild);
        root.children.add(rightChild);

        leftChild.children.add(new Node(3));
        leftChild.children.add(new Node(4));

        midChild.children.add(new Node(5));
        midChild.children.add(new Node(5));

        rightChild.children.add(new Node(4));
        rightChild.children.add(new Node(3));
    }

    public static class Node {

        int value;
        LinkedList<Node> children;

        public Node(int value) {

            this.value = value;
            children = new LinkedList<Node>();
        }
    }
}