We shall solve boundary traversal of binary tree in this tutorial.
Problem Statement:
Given a binary tree, list all the nodes that come in the boundary.
Consider the tree as below:
So the boundary traversal will be as below:
a b d h c g l i j f k
So how did we arrive at this solution?
To get the boundary traversal we need to list down these 3 nodes.
- Left Boundary nodes
- Right Boundary nodes
- Leaf Nodes
First we shall list our left boundary as highlighted:
a, b, d, h
List out the right boundary as highlighted:
a, c, g, l
Next, list out all the leaf nodes as highlighted:
H, i, j, f, k, l
Now combine all the nodes:
a, b, d, h, a, c, g, l, h, i, j, f, k, l
As you can see that there are multiple nodes with the same names. Remove the nodes with same name to arrive at the result.
a, b, d, h, c, g, l, i, j, f, k
Solution in C
#include <stdio.h> #include <stdlib.h> // node of a binary tree struct node { int data; struct node *left, *right; }; // helper function to create a new node struct node* create_new_node(int data) { struct node* temp = (struct node*)malloc(sizeof(struct node)); temp->data = data; temp->left = temp->right = NULL; return temp; } // function to print leaf nodes of a binary tree void print_leaf_nodes(struct node* root) { if (root == NULL) return; print_leaf_nodes(root->left); // Print it if it is a leaf node if (!(root->left) && !(root->right)) printf("%d ", root->data); print_leaf_nodes(root->right); } //print left boundary except leaf node as top down approach void print_left_boundary(struct node* root) { if (root == NULL) return; if (root->left) { printf("%d ", root->data); print_left_boundary(root->left); } else if (root->right) { printf("%d ", root->data); print_left_boundary(root->right); } } //print right boundary except leaf node as bottom up approach void print_right_boundary(struct node* root) { if (root == NULL) return; if (root->right) { print_right_boundary(root->right); printf("%d ", root->data); } else if (root->left) { print_right_boundary(root->left); printf("%d ", root->data); } } // function to perform boundary traversal of a given binary tree void boundary_traversal(struct node* root) { if (root == NULL) return; //print root node printf("%d ", root->data); // print left side boundary print_left_boundary(root->left); // print all leaf nodes print_leaf_nodes(root->left); print_leaf_nodes(root->right); // print left side boundary as bottom up print_right_boundary(root->right); } int main() { struct node* root = create_new_node(3); root->left = create_new_node(1); root->left->left = create_new_node(2); root->left->right = create_new_node(4); root->left->right->left = create_new_node(7); root->left->right->right = create_new_node(9); root->right = create_new_node(34); boundary_traversal(root); return 0; }
Output:
3 1 2 7 9 34