Boundary Traversal of binary tree OR
Print Circumference of Binary Tree OR
Given a Binary Tree, Print its Perimeter OR
Print outside nodes of Binary Tree OR
Print Edge nodes of Binary Tree OR
Print Boundary of Binary Tree.
We have to print the boundary nodes of given Binary Tree in anti-clockwise starting from the root.
Let us first understand what we want to achieve? what is the input and what will be the expected output?
Algorithm
- Print Left boundary Nodes.
- Print Leaf Nodes.
- Print Right boundary Nodes in Bottom up fashion.
Print Left Boundary Nodes
While traversing the Left side of Tree, you can meet either of following condition,
Node has Left child
If Node has left child then print the node and visit its left child.
Node 100 has left child, so print 100 and traverse the left Node of 100.
Node 50 has left child, so print 50 and traverse the left of Node 50.
Node doesn't has Left child
If Node doesn't has left child then its Right child will form a boundary, So print Right child and visit its Left child(as we are interested in Left boundary) if exist or Repeat step 2 if Left child doesn't exist.
Node 25 doesn't has left child but has right child present, So Right child 30 will be part of boundary.
Print Node 25 and visit its Right child 30.
Node 30 doesn't has Left child, So print 30 and visit its Right child 35.
Node doesn't has Left child and Right Child present.
If Left Node and Right Node is not present for a Node then it is sure that Node is a Leaf Node.
So, don't print it in current traversal as in current traversal we are printing only Nodes on Left Boundaries.
Node 35 doesn't has left child and right child, so it is Leaf Node and we will ignore it in Left boundary Traversal as it is going to get cover when we visit all Leafs.
Print Leaf Nodes
This is simple, when you found any node, whose Left and Right child is not present then it is a Leaf Node.
Nodes 35 70 80 140 200 are leaf nodes in our example.
Print Right Boundary Nodes in Bottom Up fashion
As we need to travel the Right side of a Tree in Bottom Up fashion, So we will start reading the Right side of tree from Top, but will not print the node data as we encounter it because we need node values to be printed in bottom up fashion.
We will print Node values at last, what I mean by last is, we will print Node when our recursive call stack returns back.
While traversing the Right side of Tree, you can meet either of following condition,
Node has Right child
If Node has Right child then visit its right child. Remember we will not print at this time but this node will be printed at last.
Node 100 has right child, so traverse the right of Node 100.
Node 150 has right child, so traverse the right of Node 150.
Node doesn't has Right child
If Node doesn't has Right child then its Left child will form a boundary, So visit its Left child and for left child, Check its Right child exist. Repeat step 2 if Right child doesn't exist. In our example, we don't have this case.
Node doesn't has Left child and Right Child present
If Left Node and Right Node is not present for a Node then it is sure that Node is a Leaf Node. So, don't print it in current traversal as in current traversal we are printing only Nodes on Right Boundaries.
Node 200 doesn't has left child and right child, so it is Leaf Node and we will ignore it in Right boundary Traversal as it is covered while we visit all Leafs.
One important thing if you notice here is Node 100, that is Root Node is repeated twice which we need to print only once.
As we included root node in both the cases, while printing Left boundaries and Right boundaries,
that is why it got repeated twice.
So what we can do is first print the rootNode separately and then for,
Left boundaries we will start from rootNode.left that is ignoring Root Node.
Right boundaries we will start from rootNode.right that is ignoring Root Node.
in this way we will print Root Node only once.
Java Program for Boundary Traversal of binary tree.
PrintBoundaryOfBinaryTree.java
package javabypatel.tree;
public class PrintBoundaryOfBinaryTree {
private Node rootNode=null;
public static void main(String[] args) {
new PrintBoundaryOfBinaryTree();
}
public PrintBoundaryOfBinaryTree(){
addNode(rootNode, 100);
addNode(rootNode, 50);
addNode(rootNode, 150);
addNode(rootNode, 25);
addNode(rootNode, 75);
addNode(rootNode, 140);
addNode(rootNode, 142);
addNode(rootNode, 30);
addNode(rootNode, 70);
addNode(rootNode, 80);
addNode(rootNode, 35);
printBoundary(rootNode);
}
private void printBoundary(Node rootNode) {
if(rootNode!=null){
printRoot(rootNode);
if(rootNode.getLeft()!=null)
printLeft(rootNode.getLeft());
printLeaf(rootNode);
if(rootNode.getRight()!=null)
printRight(rootNode.getRight());
}
}
private void printRoot(Node rootNode) {
System.out.print(rootNode.getData() + " ");
}
private void printLeft(Node rootNode){
if(rootNode==null){
return;
}
if(rootNode.getLeft()==null && rootNode.getRight()==null){
return;
}
System.out.print(rootNode.getData() + " ");
if(rootNode.getLeft()==null){
printLeft(rootNode.getRight());
}else{
printLeft(rootNode.getLeft());
}
}
private void printLeaf(Node rootNode){
if(rootNode==null){
return;
}
if(rootNode.getLeft()==null && rootNode.getRight()==null){
System.out.print(rootNode.getData() + " ");
return;
}
printLeaf(rootNode.getLeft());
printLeaf(rootNode.getRight());
}
private void printRight(Node rootNode){
if(rootNode==null){
return;
}
if(rootNode.getLeft()==null && rootNode.getRight()==null){
return;
}
if(rootNode.getRight()==null){
printRight(rootNode.getLeft());
System.out.print(rootNode.getData() + " ");
}else{
printRight(rootNode.getRight());
System.out.print(rootNode.getData() + " ");
}
}
private void addNode(Node rootNode, int data){
if(rootNode==null){
Node temp1 = new Node(data);
this.rootNode=temp1;
}else{
addNodeInProperPlace(rootNode, data);
}
}
private void addNodeInProperPlace(Node rootNode, int data){
if(data>rootNode.getData()){
if(rootNode.getRight()!=null){
addNode(rootNode.getRight(), data);
}else{
Node temp1 = new Node(data);
rootNode.setRight(temp1);
}
}else if(data<rootNode.getData()){
if(rootNode.getLeft()!=null){
addNode(rootNode.getLeft(), data);
}else{
Node temp1 = new Node(data);
rootNode.setLeft(temp1);
}
}
}
}
Node.java
package javabypatel.tree;
public class Node{
private int data;
private Node left;
private Node right;
public Node(int data) {
this.data=data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
You may also like to see
Traverse a Binary Tree in Pre Order, Post Order and Level Order Traversal
Zig Zag/Spiral Traversal of Binary Tree
Top Binary tree interview questions in Java
Find Kth SMALLEST element in BST(Binary Search Tree)
Check whether Binary Tree is foldable or not.
Check if two nodes are cousins in a Binary Tree.
Get Level/Height of node in binary tree
Print nodes at K distance from Leaf node in Binary tree.
Construct a Binary Tree from In-order and Post-order traversals.
Print Nodes in Top View of Binary Tree.
Zig Zag Traversal of Binary Tree.
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment