Boundary Traversal Of Binary Tree
Introduction
It is suggested that you read this article first then you should be familiar with the concepts of recursion and tree. Understanding different traversal techniques will help you, and a good foundation of recursion is a must. Today we’ll see different type of traversal i.e., boundary traversal of a binary tree.
Understanding of Tree
We've all spent our childhoods watching trees. Roots, stems, branches, and leaves make up this plant. Long ago, it was discovered that each leaf of a tree follows its own path back to the base. As a result, tree structure was utilised to explain hierarchical relationships, such as family trees and animal kingdom categorization, among other things.
In computer science, this hierarchical tree structure is utilised as an abstract data type for numerous purposes such as data storage, search, and sort algorithms. Let's take a closer look at this data type.
A tree is a type of hierarchical data structure that is made up of nodes. Value is represented by nodes, which are connected by edges. The following are the characteristics of a tree:
- The root node is the only node in the tree. This is where the tree comes from, so it doesn't have any parents.
- Each node has just one parent, but several children.
- Each node has an edge that connects it to its offspring.
Types of Tree
The amount of children a node has determines the kind of tree. There are two main types of trees:
- A General tree is one in which the number of offspring a node can have is not limited. Family tree and Folder Structure are two examples.
- In a binary tree, each node can have no more than two offspring, left and right. B and D are left children, whereas C, E, and F are right children in the figure below.
Based on their use, binary trees are further classified into a variety of sorts.
- The term "complete binary tree" refers to a tree in which each node has either 0 or 2 offspring. Because node C only has a right child, the tree in the figure is not a full binary tree.
- It's a binary tree with all inner nodes having two offspring and all leaves having the same depth or level.
l = 2h and n = 2h+1 – 1 in a perfect complete binary tree, where n is the number of nodes, h is the tree's height, and l is the number of leaf nodes. Because h is 2 in the picture above, leaves will be 4 and nodes will be 23 – 1 = 7.
- A balanced tree is one in which the heights of the left and right subtrees at every node vary by no more than one.
- Binary Search Tree: This is a binary tree having the property of binary search. The value or key of the left node is less than its parent, while the value or key of the right node is higher than its parent, according to the binary search feature. This applies to all nodes.
Various searching and sorting techniques employ binary search trees. Binary search trees come in a variety of shapes and sizes, such as the AVL tree, B-tree, Red-black tree, and so on.
Problem Description
Before reading the solution, It is recommended that you try out Boundary traversal of a binary tree.
Print the binary tree's border nodes anti-clockwise, starting at the root, given a binary tree. Without duplicate nodes, the boundary contains the left, leaves, and right boundaries in that sequence. (There's a chance the node values are still duplicated.)
The left boundary is the path from the root to the farthest left node. The right boundary is the path from the root to the right-most node. If the root has no left or right subtrees, the root is either left or right boundary. It's worth noting that this definition only applies to the input binary tree, not any of its subtrees.
The left-most node is a leaf node that may be reached by first traveling to the left subtree if one exists. If not, go to the appropriate subtree. Continue this process until you reach a leaf node.
The right-most node is defined in the same way as the left-most node, with left and right swapped.
Node:
One thing to keep in mind is that nodes should not be printed again. The leftmost node, for example, is also the tree's leaf node.
Following is the implementation based on the scenarios above:
You just need to complete the traverseBoundary function here.To print the boundary traversal of a binary tree The structure and input of data in the binary tree are taken care of.
Template of the TreeNode:
template <typename T>
class TreeNode {
public :
T data;
TreeNode<T> *left;
TreeNode<T> *right;
TreeNode(T data) {
this -> data = data;
left = NULL;
right = NULL;
}
~TreeNode() {
if(left)
delete left;
if(right)
delete right;
}
};Method 1:
Algorithm for boundary traversal of a binary tree:
We divide the problem into three parts:
- Print the left border from the top down.
- Print all leaf nodes from left to right, which can be divided into two sections:
2.1 From left to right, print all leaf nodes of the left sub-tree.
2.2 From left to right, print all leaf nodes of the right subtree.
- Print the right border from the bottom up.
To avoid publishing duplicates, the solution should handle the following edge cases:
- Both the left and right boundary traversals print the root node. Printing the root node first and doing the left boundary traversal on the root's left child and the right boundary traversal on the right child will prevent this.
- The binary tree's leftmost and rightmost nodes are known as leaf nodes. When printing the leaf nodes, they will be printed during the traversal of the left and correct bounds. Skip the leaf nodes when traversing the left and right bounds to get around this.
// C++ program for the above approach
void leftVeiw(TreeNode<int> * root , vector<int>&ans){
if(root == NULL){
return ;
}
if(root -> left == NULL and root -> right == NULL ){
return ;
}
ans.push_back(root -> data) ;
leftVeiw(root -> left , ans) ;
if(root -> left == NULL ){
leftVeiw(root -> right , ans ) ;
return ;
}
return ;
}
void leafNodes(TreeNode<int> * root , vector<int> & ans){
if(root == NULL){
return ;
}
if(root -> left == NULL and root -> right == NULL){
ans.push_back(root->data) ;
return ;
}
leafNodes(root -> left , ans) ;
leafNodes(root -> right , ans) ;
return ;
}
void rightVeiw(TreeNode<int> * root , vector<int> & ans){
if(root == NULL){
return ;
}
if(root->right == NULL and root -> left == NULL){
return ;
}
rightVeiw(root -> right, ans) ;
if(root -> right == NULL){
rightVeiw(root -> left , ans) ;
}
ans.push_back(root -> data) ;
return ;
}
vector<int> traverseBoundary(TreeNode<int>* root){
vector<int> ans;
if(!root){
return ans ;
}
ans.push_back(root -> data) ;
if(root -> left){
leftVeiw(root->left , ans) ;
}
leafNodes(root->left, ans) ;
leafNodes(root -> right , ans) ;
if(root -> right){
rightVeiw(root -> right , ans ) ;
}
return ans ;
}