sminfo
BAN USERThe side doesn't let me to paste my dotnetfiddle link here, but you can still check it out, the id is /nchavf.
// C# code:
using System;
using System.Collections.Generic;
namespace PracticeProgrammingPack
{
public partial class Program
{
// This method first creates the list of left child nodes by visting them in a VLR fashion,
// Then, creates the list of right child nodes by visting them in a VRL fashion (mirrored),
// Finally compares the 2 above lists to see if they're equal.
// The algorithm runs in O(n)
private static bool IsMirroredBinaryTree(BinaryTree<int> tree)
{
if (tree == null || tree.Root == null)
{
return false;
}
List<int> leftChildren = new List<int>();
List<int> rightChildren = new List<int>();
TraverseLeftVLR(tree.Root.LeftChild, leftChildren);
TraverseRightVRL(tree.Root.RightChild, rightChildren);
if (leftChildren.Count != rightChildren.Count)
{
return false;
}
for (int i = 0; i < leftChildren.Count; i++)
{
if (leftChildren[i] != rightChildren[i])
{
return false;
}
}
return true;
}
// a depth first traverse, in a Visit-Right-Left fashion
private static void TraverseRightVRL(BinaryTreeNode<int> node, List<int> rightChildren)
{
if (node == null)
{
return;
}
rightChildren.Add(node.Value);
TraverseRightVRL(node.RightChild, rightChildren);
TraverseRightVRL(node.LeftChild, rightChildren);
}
// a depth first traverse, in a Visit-Left-Right fashion
private static void TraverseLeftVLR(BinaryTreeNode<int> node, List<int> leftChildren)
{
if (node == null)
{
return;
}
leftChildren.Add(node.Value);
TraverseLeftVLR(node.LeftChild, leftChildren);
TraverseLeftVLR(node.RightChild, leftChildren);
}
public static void Main()
{
// Pardon me for this stupid initialization, but I didn't want to spend time developing a perfect BinaryTree data structure
BinaryTreeNode<int> n1 = new BinaryTreeNode<int> { Value = 60 };
BinaryTreeNode<int> n2 = new BinaryTreeNode<int> { Value = 30 };
BinaryTreeNode<int> n3 = new BinaryTreeNode<int> { Value = 30 };
BinaryTreeNode<int> n4 = new BinaryTreeNode<int> { Value = 20 };
BinaryTreeNode<int> n5 = new BinaryTreeNode<int> { Value = 50 };
BinaryTreeNode<int> n6 = new BinaryTreeNode<int> { Value = 50 };
BinaryTreeNode<int> n7 = new BinaryTreeNode<int> { Value = 20 };
BinaryTreeNode<int> n8 = new BinaryTreeNode<int> { Value = 15 };
BinaryTreeNode<int> n9 = new BinaryTreeNode<int> { Value = 15 };
BinaryTree<int> tree = new BinaryTree<int>();
tree.Root = n1;
tree.Root.LeftChild = n2;
tree.Root.RightChild = n3;
tree.Root.LeftChild.LeftChild = n4;
tree.Root.LeftChild.RightChild = n5;
tree.Root.LeftChild.RightChild.LeftChild = n8;
tree.Root.RightChild.LeftChild = n6;
tree.Root.RightChild.LeftChild.RightChild = n9;
tree.Root.RightChild.RightChild = n7;
Console.WriteLine(IsMirroredBinaryTree(tree));
}
}
public class BinaryTreeNode<T>
{
public T Value { get; set; }
public BinaryTreeNode<T> LeftChild { get; set; }
public BinaryTreeNode<T> RightChild { get; set; }
}
public class BinaryTree<T>
{
public BinaryTreeNode<T> Root { get; set; }
}
}
Here is the C# code with explanation:
- sminfo March 12, 2017