using System.Collections.Generic;
public static void Main()
CalculateNodeRight(ref root);
if (ValidateTreeStructure(root)) {
Console.WriteLine("Tree Built Successfully");
Console.WriteLine("Tree NOT Built Successfully");
if (ValidateTreeRights(root)) {
Console.WriteLine("Tree Rights Found Successfully");
Console.WriteLine("Tree Rights NOT Found Successfully");
private static void CalculateNodeRight(ref Node root) {
Queue<Node> nodesToVisit = new Queue<Node>();
nodesToVisit.Enqueue(root);
Queue<int> nodeLevels = new Queue<int>();
while(nodesToVisit.Count > 0) {
Node currentNode = nodesToVisit.Dequeue();
int depth = nodeLevels.Dequeue();
if (nodesToVisit.Count > 0) {
if (depth == nodeLevels.Peek()) {
Console.WriteLine(currentNode.Id.ToString() + " " + nodesToVisit.Peek().Id.ToString());
currentNode.Right = nodesToVisit.Peek();
if (currentNode.Children != null) {
for(int i = 0; i < currentNode.Children.Length; i++) {
nodesToVisit.Enqueue(currentNode.Children[i]);
nodeLevels.Enqueue(depth + 1);
private static void PrintNodes(Node root) {
string right = root.Right == null ? "NONE": root.Right.Id.ToString();
Console.WriteLine("Id " + root.Id + "\tRight " + right);
if (root.Children != null) {
for(int i = 0; i < root.Children.Length; i++) {
Console.WriteLine("\t Child " + root.Children[i].Id);
for(int i = 0; i < root.Children.Length; i++) {
PrintNodes(root.Children[i]);
Console.WriteLine("\t No Children");
private static bool ValidateTreeStructure(Node root) {
Queue<Node> nodesToVisit = new Queue<Node>();
nodesToVisit.Enqueue(root);
List<int> visitedIds = new List<int>();
while (nodesToVisit.Count > 0) {
Node temp = nodesToVisit.Dequeue();
if (temp.Children != null) {
for(int i = 0; i < temp.Children.Length; i++) {
nodesToVisit.Enqueue(temp.Children[i]);
if (visitedIds.Count != 7) {
for(int i = 1; i <= 7; i++) {
if (visitedIds[i-1] != i) {
private static bool ValidateTreeRights(Node root) {
List<int> nodeRights = new List<int>();
Queue<Node> nodesToCheck = new Queue<Node>();
nodesToCheck.Enqueue(root);
while(nodesToCheck.Count > 0) {
Node currentNode = nodesToCheck.Dequeue();
if (currentNode.Right == null) {
if (nodeRights[currentNode.Id - 1] != -1) {
} else if (nodeRights[currentNode.Id - 1] != currentNode.Right.Id) {
if (currentNode.Children != null) {
for(int i = 0; i < currentNode.Children.Length; i++) {
nodesToCheck.Enqueue(currentNode.Children[i]);
private static Node BuildTree() {
root.Children = new Node[3];
left.Children = new Node[2];
Node middle = new Node();
middle.Children = new Node[0];
right.Children = new Node[1];
root.Children[1] = middle;
root.Children[2] = right;
Node leftLeft = new Node();
Node leftRight = new Node();
left.Children[0] = leftLeft;
left.Children[1] = leftRight;
Node rightLeft = new Node();
right.Children[0] = rightLeft;