Perform boundary traversal on a binary tree
Given a binary tree, perform the boundary traversal on it.
The solution should print the boundary nodes starting from the tree’s root, in an anti-clockwise direction, without any duplicates. For example, the following binary tree’s boundary traversal is 1, 2, 4, 8, 12, 13, 10, 6, 14, 11, 7, 3:
The idea is to split the problem into 3 parts:
- Print the left boundary in a top-down fashion.
- Print the leaf nodes in the same order as in the inorder traversal.
- Print the right boundary in a bottom-up fashion.
This approach looks simple, but there are several edge cases the solution should handle to avoid printing duplicates:
- Both the left boundary and the right boundary traversal prints the root node. We can avoid this by printing the root node first and performing the left boundary traversal on the root’s left child and the right boundary traversal on the root’s right child.
- The leftmost and the rightmost node of the binary tree are leaf nodes. They will get printed while performing the left boundary and the right boundary traversal while printing the leaf nodes. To avoid it, exclude the leaf nodes while doing the left boundary and the right boundary traversal.
Following is the pictorial representation of the above logic:
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
#include <iostream> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } public: // Utility function to check if a given node is a leaf node bool isLeaf() { return this->left == nullptr && this->right == nullptr; } }; // Recursive function to print the left boundary of the given binary tree // in a top-down fashion, except for the leaf nodes void printLeftBoundary(Node* root) { // base case: root is empty if (!root) { return; } Node* node = root; // do for all non-leaf nodes while (!node->isLeaf()) { // print the current node cout << node->data << ' '; // next process, the left child of `root` if it exists; // otherwise, move to the right child node = (node->left) ? node->left: node->right; } } // Recursive function to print the right boundary of the given binary tree // in a bottom-up fashion, except for the leaf nodes void printRightBoundary(Node* root) { // base case: root is empty, or root is a leaf node if (!root || root->isLeaf()) { return; } // recur for the right child of `root` if it exists; // otherwise, recur for the left child printRightBoundary(root->right ? root->right: root->left); // To ensure bottom-up order, print the value of the nodes // after recursion unfolds cout << root->data << ' '; } // Recursive function to print the leaf nodes of the given // binary tree in an inorder fashion void printLeafNodes(Node* root) { // base case if (root == nullptr) { return; } // recur for the left subtree printLeafNodes(root->left); // print only leaf nodes if (root->isLeaf()) { cout << root->data << ' '; } // recur for the right subtree printLeafNodes(root->right); } // Function to perform the boundary traversal on a given tree void performBoundaryTraversal(Node* root) { // base case if (root == nullptr) { return; } // print the root node cout << root->data << ' '; // print the left boundary (except leaf nodes) printLeftBoundary(root->left); // print all leaf nodes if (!root->isLeaf()) { printLeafNodes(root); } // print the right boundary (except leaf nodes) printRightBoundary(root->right); } int main() { // construct a binary tree as per the above diagram Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); root->left->left->left = new Node(8); root->left->left->right = new Node(9); root->left->right->right = new Node(10); root->right->right->left = new Node(11); root->left->left->right->left = new Node(12); root->left->left->right->right = new Node(13); root->right->right->left->left = new Node(14); performBoundaryTraversal(root); return 0; } |
Output:
1 2 4 8 12 13 10 6 14 11 7 3
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 |
// A class to store a binary tree node class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = this.right = null; } // Utility function to check if a given node is a leaf node boolean isLeaf() { return this.left == null && this.right == null; } } class Main { // Recursive function to print the left boundary of the given binary tree // in a top-down fashion, except for the leaf nodes public static void printLeftBoundary(Node root) { // base case: root is empty if (root == null) { return; } Node node = root; // do for all non-leaf nodes while (!node.isLeaf()) { // print the current node System.out.print(node.data + " "); // next process, the left child of `root` if it exists; // otherwise, move to the right child node = (node.left != null) ? node.left: node.right; } } // Recursive function to print the right boundary of the given binary tree // in a bottom-up fashion, except for the leaf nodes public static void printRightBoundary(Node root) { // base case: root is empty, or root is a leaf node if (root == null || root.isLeaf()) { return; } // recur for the right child of `root` if it exists; // otherwise, recur for the left child printRightBoundary(root.right != null ? root.right: root.left); // To ensure bottom-up order, print the value of the nodes // after recursion unfolds System.out.print(root.data + " "); } // Recursive function to print the leaf nodes of the given // binary tree in an inorder fashion public static void printLeafNodes(Node root) { // base case if (root == null) { return; } // recur for the left subtree printLeafNodes(root.left); // print only leaf nodes if (root.isLeaf()) { System.out.print(root.data + " "); } // recur for the right subtree printLeafNodes(root.right); } // Function to perform the boundary traversal on a given tree public static void performBoundaryTraversal(Node root) { // base case if (root == null) { return; } // print the root node System.out.print(root.data + " "); // print the left boundary (except leaf nodes) printLeftBoundary(root.left); // print all leaf nodes if (!root.isLeaf()) { printLeafNodes(root); } // print the right boundary (except leaf nodes) printRightBoundary(root.right); } public static void main(String[] args) { // construct a binary tree as per the above diagram Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.right = new Node(10); root.right.right.left = new Node(11); root.left.left.right.left = new Node(12); root.left.left.right.right = new Node(13); root.right.right.left.left = new Node(14); performBoundaryTraversal(root); } } |
Output:
1 2 4 8 12 13 10 6 14 11 7 3
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
# A class to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Utility function to check if a given node is a leaf node def isLeaf(self): return self.left is None and self.right is None # Recursive function to print the left boundary of the given binary tree # in a top-down fashion, except for the leaf nodes def printLeftBoundary(root): # base case: root is empty if root is None: return node = root # do for all non-leaf nodes while not node.isLeaf(): # print the current node print(node.data, end=' ') # next process, the left child of `root` if it exists; # otherwise, move to the right child node = node.left if node.left else node.right # Recursive function to print the right boundary of the given binary tree # in a bottom-up fashion, except for the leaf nodes def printRightBoundary(root): # base case: root is empty, or root is a leaf node if root is None or root.isLeaf(): return # recur for the right child of `root` if it exists; # otherwise, recur for the left child printRightBoundary(root.right if root.right else root.left) # To ensure bottom-up order, print the value of the nodes # after recursion unfolds print(root.data, end=' ') # Recursive function to print the leaf nodes of the given # binary tree in an inorder fashion def printLeafNodes(root): # base case if root is None: return # recur for the left subtree printLeafNodes(root.left) # print only leaf nodes if root.isLeaf(): print(root.data, end=' ') # recur for the right subtree printLeafNodes(root.right) # Function to perform the boundary traversal on a given tree def performBoundaryTraversal(root): # base case if root is None: return # print the root node print(root.data, end=' ') # print the left boundary (except leaf nodes) printLeftBoundary(root.left) # print all leaf nodes if not root.isLeaf(): printLeafNodes(root) # print the right boundary (except leaf nodes) printRightBoundary(root.right) if __name__ == '__main__': # construct a binary tree as per the above diagram root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) root.left.left.left = Node(8) root.left.left.right = Node(9) root.left.right.right = Node(10) root.right.right.left = Node(11) root.left.left.right.left = Node(12) root.left.left.right.right = Node(13) root.right.right.left.left = Node(14) performBoundaryTraversal(root) |
Output:
1 2 4 8 12 13 10 6 14 11 7 3
The time complexity of the above solution is O(n), where n is the total number of nodes in the tree. The auxiliary space required by the program is O(h) for the call stack, where h is the height of the tree.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)