Introducation
After playing with data structures I found the following algorithm that performs boundary item detection of a binary tree. We even have many algorithms but special logic in this algorithm makes this more effective.
The algorithm
For the binary tree, the boundary item should be a part of the following scenario.
The scenarios are:
- In global left child or
- In global right child or
- Or having left and right children are null.
If a child meets any of the preceding scenarios then it will be a boundary element.
Algorithm
reachedBottom <- false
Add(Root)
GlobalLeftIteration(Tree node)
{
if (not reachedBottom)
Add (node)
if (node.Left not null)
GlobalLeftIteration(node.Left)
else
if (node.Left is null && node.Right is null and reachedBottom)
items.Add(node.Node)
return
reachedBottom = true
if (node.Right not null)
RightIteration(node.Right)
}
RightIteration(Tree node)
{
if (node.Left not null)
GlobalLeftIteration(node.Left)
else
reachedBottom <- true
if (node.Left is null && node.Right is null)
Add(node)
return;
if (node.Right not null)
RightIteration(node.Right)
}
GlobalRightIteration(Tree node)
{
if (not reachedBottom)
items.Add(node.Node)
if (node.Right not null)
GlobalRightIteration(node.Right)
else
if (node.Left is null && node.Right is null and reachedBottom)
Add(node)
return;
reachedBottom <- true
if (node.Left not null)
LeftIteration(node.Left)
}
LeftIteration(Tree node)
{
if (node.Right not null)
GlobalRightIteration(node.Right)
else
reachedBottom <- true
if (node.Left is null && node.Right is null)
items.Add(node.Node);
return;
if (node.Left not null)
RightIteration(node.Left)
}
In our proposed algorithm we use the followingprocedure:
- Add the root node in boundary items collection.
- Pass a root node left for global left iteration, and add if the iteration has not reached the end of the global left child
- Recursively call the left iteration.
- Once we have reached the end of the global left child it recursively iterates to the right children and its corresponding left children to find the boundary item by checking if its left and right children are null.
- Use a similar process to iterate for Global Right iteration except the reverse of the preceding
Code snippet
namespace BoundaryNodes
{
public class Tree
{
public string Node { get; set; }
public Tree Left { get; set; }
public Tree Right { get; set; }
}
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
Tree ANode = new Tree(); ANode.Node = "A";
Tree BNode = new Tree(); BNode.Node = "B";
Tree CNode = new Tree(); CNode.Node = "C";
Tree DNode = new Tree(); DNode.Node = "D";
Tree ENode = new Tree(); ENode.Node = "E";
Tree FNode = new Tree(); FNode.Node = "F";
Tree GNode = new Tree(); GNode.Node = "G";
Tree HNode = new Tree(); HNode.Node = "H";
Tree INode = new Tree(); INode.Node = "I";
ANode.Left = BNode;
ANode.Right = ENode;
BNode.Left = CNode;
BNode.Right = DNode;
DNode.Left = INode;
ENode.Left = FNode;
ENode.Right = GNode;
GNode.Left = HNode;
items.Add(ANode.Node);
GlobalLeftIteration(ANode.Left);
reachedBottom = false;
GlobalRightIteration(ANode.Right);
string boundaryItems = string.Empty;
foreach (var s in items)
{
boundaryItems += (s + " ");
}
MessageBox.Show(boundaryItems);
}
List<String> items = new List<string>();
bool reachedBottom = false;
private void GlobalLeftIteration(Tree node)
{
if (!reachedBottom)
items.Add ( node.Node);
if (node.Left != null)
{
GlobalLeftIteration(node.Left);
}
else
{
if (node.Left == null && node.Right == null && reachedBottom)
{
items.Add(node.Node);
return;
}
reachedBottom = true;
}
if (node.Right != null)
{
RightIteration(node.Right);
}
}
private void RightIteration(Tree node)
{
if (node.Left != null)
{
GlobalLeftIteration(node.Left);
}
else
{
reachedBottom = true;
if (node.Left == null && node.Right == null)
{
items.Add(node.Node);
return;
}
}
if (node.Right != null)
{
RightIteration(node.Right);
}
}
private void GlobalRightIteration(Tree node)
{
if (!reachedBottom)
items.Add(node.Node);
if (node.Right != null)
{
GlobalRightIteration(node.Right);
}
else
{
if (node.Left == null && node.Right == null && reachedBottom)
{
items.Add(node.Node);
return;
}
reachedBottom = true;
}
if (node.Left != null)
{
LeftIteration(node.Left);
}
}
private void LeftIteration(Tree node)
{
if (node.Right != null)
{
GlobalRightIteration(node.Right);
}
else
{
reachedBottom = true;
if (node.Left == null && node.Right == null)
{
items.Add(node.Node);
return;
}
}
if (node.Left != null)
{
RightIteration(node.Left);
}
}
}
}
Output