Boundary traversal of a binary tree

Problem: Given a binary tree, print boundary nodes of the binary tree anti-clockwise starting from the root.

Solution: Problem can be solved using three steps:

1. Print the left boundary in top-down manner.
2. Print all leaf nodes from left to right (sorted according to their horizontal distance).
3. Print the right boundary in bottom-up manner.

All of these steps can be achieved by tweaking leftView, printLeaves and rightView of a binary tree.

Implementation:

#define mapIntToIntVect std::map<int, std::vector<int>>

void BSTree::printLeavesWithHD(Node* node, int hd, mapIntToIntVect& mapDistToNodeVect)

{

if(node)

{

printLeavesWithHD(node->left, hd - 1, mapDistToNodeVect);

if(!node->left && !node->right)

mapDistToNodeVect[hd].push_back(node->data);

printLeavesWithHD(node->right, hd + 1, mapDistToNodeVect);

}

}

void BSTree::printLeavesWithHD()

{

if(!root)

return;

mapIntToIntVect mapDistToNodeVect;

printLeavesWithHD(root, 0, mapDistToNodeVect);

for(mapIntToIntVect::iterator it = mapDistToNodeVect.begin(); it != mapDistToNodeVect.end(); ++it)

{

for(int i = 0; i < it->second.size(); ++i)

{

std::cout<<it->second[i]<<'\t';

}

}

}

void BSTree::leftBoundaryWithNoLeaves(Node* node)

{

std::queue<Node*> q[2];

bool turn = 0;

q[turn].push(node);

while(!q[turn].empty())

{

if(q[turn].front()->left || q[turn].front()->right)

std::cout<<q[turn].front()->data<<'\t';

while(!q[turn].empty())

{

Node* temp = q[turn].front();

if(temp->left)

q[!turn].push(temp->left);

if(temp->right)

q[!turn].push(temp->right);

q[turn].pop();

}

turn = !turn;

}

}

void BSTree::rightBoundaryWithNoLeavesAndRoot(Node* node)

{

std::queue<Node*> q[2];

std::stack<int> st;

bool turn = 0;

q[turn].push(node);

while(!q[turn].empty())

{

int dataToPrint = 0;

bool printRightBoundary = false;

while(!q[turn].empty())

{

Node* temp = q[turn].front();

if(temp->left)

q[!turn].push(temp->left);

if(temp->right)

q[!turn].push(temp->right);

q[turn].pop();

if(temp->left || temp->right)

printRightBoundary = true;

else

printRightBoundary = false;

dataToPrint = temp->data;

}

if(printRightBoundary)

{

st.push(dataToPrint);

}

turn = !turn;

}

while(st.size() > 1)

{

std::cout<<st.top()<<'\t';

st.pop();

}

}

void BSTree::boundaryTraversal()

{

if(!root)

return;

leftBoundaryWithNoLeaves(root);

printLeavesWithHD();

rightBoundaryWithNoLeavesAndRoot(root);

}

Complexity: O(n)