Given a binary tree, print boundary nodes of the binary tree Anti-Clockwise starting from the root.
The boundary includes
- left boundary (nodes on left excluding leaf nodes)
- leaves (consist of only the leaf nodes)
- right boundary (nodes on right excluding leaf nodes)
The left boundary is defined as the path from the root to the left-most node. The right boundary is defined as the path from the root to the right-most node. If the root doesn’t have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not apply to any subtrees.
The left-most node is defined as a leaf node you could reach when you always firstly travel to the left subtree if it exists. If not, travel to the right subtree. Repeat until you reach a leaf node.
The right-most node is also defined in the same way with left and right exchanged.
For example, boundary traversal of the following tree is “20 8 4 10 14 25 22”
This is how we write the traversal:
root : 20
left- boundary nodes: 8
leaf nodes: 4 10 14 25
right – boundary nodes: 22
We break the problem in 3 parts:
1. Print the left boundary in top-down manner.
2. Print all leaf nodes from left to right, which can again be sub-divided into two sub-parts:
…..2.1 Print all leaf nodes of left sub-tree from left to right.
…..2.2 Print all leaf nodes of right subtree from left to right.
3. Print the right boundary in bottom-up manner.
We need to take care of one thing that nodes are not printed again. e.g. The left most node is also the leaf node of the tree.
Based on the above cases, below is the implementation:
Implementation:
C++
#include <iostream>using namespace std;/* A binary tree node has data, pointer to left childand a pointer to right child */struct Node { int data; struct Node *left, *right;};// Utility function to create a new tree nodeNode* newNode(int data){ Node* temp = new Node; temp->data = data; temp->left = temp->right = nullptr; return temp;}// A simple function to print leaf nodes of a binary treevoid printLeaves(Node* root){ if (root == nullptr) return; printLeaves(root->left); // Print it if it is a leaf node if (!(root->left) && !(root->right)) cout << root->data << " "; printLeaves(root->right);}// A function to print all left boundary nodes, except a// leaf node. Print the nodes in TOP DOWN mannervoid printBoundaryLeft(Node* root){ if (root == nullptr) return; if (root->left) { // to ensure top down order, print the node // before calling itself for left subtree cout << root->data << " "; printBoundaryLeft(root->left); } else if (root->right) { cout << root->data << " "; printBoundaryLeft(root->right); } // do nothing if it is a leaf node, this way we avoid // duplicates in output}// A function to print all right boundary nodes, except a// leaf node Print the nodes in BOTTOM UP mannervoid printBoundaryRight(Node* root){ if (root == nullptr) return; if (root->right) { // to ensure bottom up order, first call for right // subtree, then print this node printBoundaryRight(root->right); cout << root->data << " "; } else if (root->left) { printBoundaryRight(root->left); cout << root->data << " "; } // do nothing if it is a leaf node, this way we avoid // duplicates in output}// A function to do boundary traversal of a given binary// treevoid printBoundary(Node* root){ if (root == nullptr) return; cout << root->data << " "; // Print the left boundary in top-down manner. printBoundaryLeft(root->left); // Print all leaf nodes printLeaves(root->left); printLeaves(root->right); // Print the right boundary in bottom-up manner printBoundaryRight(root->right);}// Driver program to test above functionsint main(){ // Let us construct the tree given in the above diagram Node* root = newNode(20); root->left = newNode(8); root->left->left = newNode(4); root->left->right = newNode(12); root->left->right->left = newNode(10); root->left->right->right = newNode(14); root->right = newNode(22); root->right->right = newNode(25); printBoundary(root); return 0;}// This code is contributed by Aditya Kumar (adityakumar129) |
C
/* C program for boundary traversal of a binary tree */#include <stdio.h>#include <stdlib.h>/* A binary tree node has data, pointer to left childand a pointer to right child */struct node { int data; struct node *left, *right;};// A simple function to print leaf nodes of a binary treevoid printLeaves(struct node* root){ if (root == NULL) return; printLeaves(root->left); // Print it if it is a leaf node if (!(root->left) && !(root->right)) printf("%d ", root->data); printLeaves(root->right);}// A function to print all left boundary nodes, except a leaf node.// Print the nodes in TOP DOWN mannervoid printBoundaryLeft(struct node* root){ if (root == NULL) return; if (root->left) { // to ensure top down order, print the node // before calling itself for left subtree printf("%d ", root->data); printBoundaryLeft(root->left); } else if (root->right) { printf("%d ", root->data); printBoundaryLeft(root->right); } // do nothing if it is a leaf node, this way we avoid // duplicates in output}// A function to print all right boundary nodes, except a leaf node// Print the nodes in BOTTOM UP mannervoid printBoundaryRight(struct node* root){ if (root == NULL) return; if (root->right) { // to ensure bottom up order, first call for right // subtree, then print this node printBoundaryRight(root->right); printf("%d ", root->data); } else if (root->left) { printBoundaryRight(root->left); printf("%d ", root->data); } // do nothing if it is a leaf node, this way we avoid // duplicates in output}// A function to do boundary traversal of a given binary treevoid printBoundary(struct node* root){ if (root == NULL) return; printf("%d ", root->data); // Print the left boundary in top-down manner. printBoundaryLeft(root->left); // Print all leaf nodes printLeaves(root->left); printLeaves(root->right); // Print the right boundary in bottom-up manner printBoundaryRight(root->right);}// A utility function to create a nodestruct node* newNode(int data){ struct node* temp = (struct node*)malloc(sizeof(struct node)); temp->data = data; temp->left = temp->right = NULL; return temp;}// Driver program to test above functionsint main(){ // Let us construct the tree given in the above diagram struct node* root = newNode(20); root->left = newNode(8); root->left->left = newNode(4); root->left->right = newNode(12); root->left->right->left = newNode(10); root->left->right->right = newNode(14); root->right = newNode(22); root->right->right = newNode(25); printBoundary(root); return 0;}// This code has been contributed by Aditya Kumar (adityakumar129) |
Java
// Java program to print boundary traversal of binary tree/* A binary tree node has data, pointer to left childand a pointer to right child */class Node { int data; Node left, right; Node(int item) { data = item; left = right = null; }}class BinaryTree { Node root; // A simple function to print leaf nodes of a binary tree void printLeaves(Node node) { if (node == null) return; printLeaves(node.left); // Print it if it is a leaf node if (node.left == null && node.right == null) System.out.print(node.data + " "); printLeaves(node.right); } // A function to print all left boundary nodes, except a leaf node. // Print the nodes in TOP DOWN manner void printBoundaryLeft(Node node) { if (node == null) return; if (node.left != null) { // to ensure top down order, print the node // before calling itself for left subtree System.out.print(node.data + " "); printBoundaryLeft(node.left); } else if (node.right != null) { System.out.print(node.data + " "); printBoundaryLeft(node.right); } // do nothing if it is a leaf node, this way we avoid // duplicates in output } // A function to print all right boundary nodes, except a leaf node // Print the nodes in BOTTOM UP manner void printBoundaryRight(Node node) { if (node == null) return; if (node.right != null) { // to ensure bottom up order, first call for right // subtree, then print this node printBoundaryRight(node.right); System.out.print(node.data + " "); } else if (node.left != null) { printBoundaryRight(node.left); System.out.print(node.data + " "); } // do nothing if it is a leaf node, this way we avoid // duplicates in output } // A function to do boundary traversal of a given binary tree void printBoundary(Node node) { if (node == null) return; System.out.print(node.data + " "); // Print the left boundary in top-down manner. printBoundaryLeft(node.left); // Print all leaf nodes printLeaves(node.left); printLeaves(node.right); // Print the right boundary in bottom-up manner printBoundaryRight(node.right); } // Driver program to test above functions public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node(20); tree.root.left = new Node(8); tree.root.left.left = new Node(4); tree.root.left.right = new Node(12); tree.root.left.right.left = new Node(10); tree.root.left.right.right = new Node(14); tree.root.right = new Node(22); tree.root.right.right = new Node(25); tree.printBoundary(tree.root); }} |
Python3
# Python3 program for binary traversal of binary tree# A binary tree nodeclass Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None# A simple function to print leaf nodes of a Binary Treedef printLeaves(root): if(root): printLeaves(root.left) # Print it if it is a leaf node if root.left is None and root.right is None: print(root.data), printLeaves(root.right)# A function to print all left boundary nodes, except a # leaf node. Print the nodes in TOP DOWN mannerdef printBoundaryLeft(root): if(root): if (root.left): # to ensure top down order, print the node # before calling itself for left subtree print(root.data) printBoundaryLeft(root.left) elif(root.right): print (root.data) printBoundaryLeft(root.right) # do nothing if it is a leaf node, this way we # avoid duplicates in output# A function to print all right boundary nodes, except# a leaf node. Print the nodes in BOTTOM UP mannerdef printBoundaryRight(root): if(root): if (root.right): # to ensure bottom up order, first call for # right subtree, then print this node printBoundaryRight(root.right) print(root.data) elif(root.left): printBoundaryRight(root.left) print(root.data) # do nothing if it is a leaf node, this way we # avoid duplicates in output# A function to do boundary traversal of a given binary treedef printBoundary(root): if (root): print(root.data) # Print the left boundary in top-down manner printBoundaryLeft(root.left) # Print all leaf nodes printLeaves(root.left) printLeaves(root.right) # Print the right boundary in bottom-up manner printBoundaryRight(root.right)# Driver program to test above functionroot = Node(20)root.left = Node(8)root.left.left = Node(4)root.left.right = Node(12)root.left.right.left = Node(10)root.left.right.right = Node(14)root.right = Node(22)root.right.right = Node(25)printBoundary(root)# This code is contributed by # Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program to print boundary traversal// of binary treeusing System;/* A binary tree node has data, pointer to left child and a pointer to right child */public class Node { public int data; public Node left, right; public Node(int item) { data = item; left = right = null; }}class GFG { public Node root; // A simple function to print leaf // nodes of a binary tree public virtual void printLeaves(Node node) { if (node == null) return; printLeaves(node.left); // Print it if it is a leaf node if (node.left == null && node.right == null) { Console.Write(node.data + " "); } printLeaves(node.right); } // A function to print all left boundary // nodes, except a leaf node. Print the // nodes in TOP DOWN manner public virtual void printBoundaryLeft(Node node) { if (node == null) return; if (node.left != null) { // to ensure top down order, print the node // before calling itself for left subtree Console.Write(node.data + " "); printBoundaryLeft(node.left); } else if (node.right != null) { Console.Write(node.data + " "); printBoundaryLeft(node.right); } // do nothing if it is a leaf node, // this way we avoid duplicates in output } // A function to print all right boundary // nodes, except a leaf node. Print the // nodes in BOTTOM UP manner public virtual void printBoundaryRight(Node node) { if (node == null) return; if (node.right != null) { // to ensure bottom up order, // first call for right subtree, // then print this node printBoundaryRight(node.right); Console.Write(node.data + " "); } else if (node.left != null) { printBoundaryRight(node.left); Console.Write(node.data + " "); } // do nothing if it is a leaf node, // this way we avoid duplicates in output } // A function to do boundary traversal // of a given binary tree public virtual void printBoundary(Node node) { if (node == null) return; Console.Write(node.data + " "); // Print the left boundary in // top-down manner. printBoundaryLeft(node.left); // Print all leaf nodes printLeaves(node.left); printLeaves(node.right); // Print the right boundary in // bottom-up manner printBoundaryRight(node.right); } // Driver Code public static void Main(string[] args) { GFG tree = new GFG(); tree.root = new Node(20); tree.root.left = new Node(8); tree.root.left.left = new Node(4); tree.root.left.right = new Node(12); tree.root.left.right.left = new Node(10); tree.root.left.right.right = new Node(14); tree.root.right = new Node(22); tree.root.right.right = new Node(25); tree.printBoundary(tree.root); }}// This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript program to print boundary // traversal of binary tree class Node { constructor(item) { this.left = null; this.right = null; this.data = item; } } let root; // A simple function to print leaf nodes of a binary tree function printLeaves(node) { if (node == null) return; printLeaves(node.left); // Print it if it is a leaf node if (node.left == null && node.right == null) document.write(node.data + " "); printLeaves(node.right); } // A function to print all left boundary nodes, // except a leaf node. // Print the nodes in TOP DOWN manner function printBoundaryLeft(node) { if (node == null) return; if (node.left != null) { // to ensure top down order, print the node // before calling itself for left subtree document.write(node.data + " "); printBoundaryLeft(node.left); } else if (node.right != null) { document.write(node.data + " "); printBoundaryLeft(node.right); } // do nothing if it is a leaf node, this way we avoid // duplicates in output } // A function to print all right boundary nodes, // except a leaf node // Print the nodes in BOTTOM UP manner function printBoundaryRight(node) { if (node == null) return; if (node.right != null) { // to ensure bottom up order, first call for right // subtree, then print this node printBoundaryRight(node.right); document.write(node.data + " "); } else if (node.left != null) { printBoundaryRight(node.left); document.write(node.data + " "); } // do nothing if it is a leaf node, this way we avoid // duplicates in output } // A function to do boundary traversal of a given binary tree function printBoundary(node) { if (node == null) return; document.write(node.data + " "); // Print the left boundary in top-down manner. printBoundaryLeft(node.left); // Print all leaf nodes printLeaves(node.left); printLeaves(node.right); // Print the right boundary in bottom-up manner printBoundaryRight(node.right); } root = new Node(20); root.left = new Node(8); root.left.left = new Node(4); root.left.right = new Node(12); root.left.right.left = new Node(10); root.left.right.right = new Node(14); root.right = new Node(22); root.right.right = new Node(25); printBoundary(root); </script> |
Output
20 8 4 10 14 25 22
Time Complexity: O(n) where n is the number of nodes in binary tree.
Auxiliary Space: O(n)
Clean Code with returning the traversal:
[No direct printing + Iterative Version of the code]
Algorithm:
- Right Boundary – Go Right Right until no Right. Dont Include Leaf nodes. (as it leads to duplication)
- Left Boundary – Go Left Left until no Left. Dont Include Leaf nodes. (as it leads to duplication)
- Leaf Boundary – Do inorder/preorder, if leaf node add to the List.
- We pass the array as reference, so its the same memory location used by all functions, to coordinate the result at one place.
CODE:
C++
#include <bits/stdc++.h>using namespace std; /* A binary tree node has data, pointer to left childand a pointer to right child */struct Node { int data; struct Node *left, *right;}; // Utility function to create a new tree nodeNode* newNode(int data){ Node* temp = new Node; temp->data = data; temp->left = temp->right = nullptr; return temp;}bool isLeaf(Node* node){ if(node->left == NULL && node->right==NULL){ return true; } return false;}void addLeftBound(Node * root, vector<int>& ans){ //Go left left and no left then right but again check from left root = root->left; while(root){ if(!isLeaf(root)) ans.push_back(root->data); if(root->left) root = root->left; else root = root->right; }}void addRightBound(Node * root, vector<int>& ans){ //Go right right and no right then left but again check from right root = root->right; //As we need the reverse of this for Anticlockwise //refer above picture for better understanding stack<int> stk; while(root){ if(!isLeaf(root)) stk.push(root->data); if(root->right) root = root->right; else root = root->left; } while(!stk.empty()){ ans.push_back(stk.top()); stk.pop(); }}//its kind of preordervoid addLeaves(Node * root, vector<int>& ans){ if(root==NULL){ return; } if(isLeaf(root)){ ans.push_back(root->data); //just store leaf nodes return; } addLeaves(root->left,ans); addLeaves(root->right,ans);}vector <int> boundary(Node *root){ //Your code here vector<int> ans; if(root==NULL) return ans; if(!isLeaf(root)) ans.push_back(root->data); // if leaf then its done by addLeaf addLeftBound(root,ans); addLeaves(root,ans); addRightBound(root,ans); return ans;}int main(){ // Let us construct the tree given in the above diagram Node* root = newNode(20); root->left = newNode(8); root->left->left = newNode(4); root->left->right = newNode(12); root->left->right->left = newNode(10); root->left->right->right = newNode(14); root->right = newNode(22); root->right->right = newNode(25); vector<int>ans = boundary(root); for(int v : ans){ cout<<v<<" "; } cout<<"\n"; return 0;}//Code done by Balakrishnan R (rbkraj000) |
Java
// Java program to print boundary traversal of binary treeimport java.io.*;import java.util.*;class BinaryTree { Node root; /* A binary tree node has data, pointer to left childand a pointer to right child */ static class Node { int data; Node left, right; Node(int d) { data = d; left = null; right = null; } } private boolean isLeaf(Node node) { if (node.left == null && node.right == null) { return true; } return false; } private void addLeftBound(Node root, ArrayList<Integer> ans) { // Go left left and no left then right but again // check from left root = root.left; while (root != null) { if (!isLeaf(root)) { ans.add(root.data); } if (root.left != null) { root = root.left; } else { root = root.right; } } } private void addRightBound(Node root, ArrayList<Integer> ans) { // Go right right and no right then left but again // check from right root = root.right; // As we need the reverse of this for Anticlockwise Stack<Integer> stk = new Stack<>(); while (root != null) { if (!isLeaf(root)) { stk.push(root.data); } if (root.right != null) { root = root.right; } else { root = root.left; } } while (!stk.isEmpty()) { ans.add(stk.peek()); stk.pop(); } } // its kind of predorder private void addLeaves(Node root, ArrayList<Integer> ans) { if (root == null) { return; } if (isLeaf(root)) { ans.add(root.data); // just store leaf nodes return; } addLeaves(root.left, ans); addLeaves(root.right, ans); } ArrayList<Integer> boundary(Node root) { ArrayList<Integer> ans = new ArrayList<>(); if (root == null) { return ans; } if (!isLeaf(root)) { ans.add(root.data); // if leaf then its done by // addLeaves } addLeftBound(root, ans); addLeaves(root, ans); addRightBound(root, ans); return ans; } public static void main(String[] args) { // Let us construct the tree given in the above // diagram BinaryTree tree = new BinaryTree(); tree.root = new Node(20); tree.root.left = new Node(8); tree.root.left.left = new Node(4); tree.root.left.right = new Node(12); tree.root.left.right.left = new Node(10); tree.root.left.right.right = new Node(14); tree.root.right = new Node(22); tree.root.right.right = new Node(25); ArrayList<Integer> ans = tree.boundary(tree.root); for (int i = 0; i < ans.size(); i++) { System.out.print(ans.get(i) + " "); } System.out.println(); }}// This code is contributed by Snigdha Patil |
Python3
# Python program to print boundary traversal of binary tree# A binary tree node has data, pointer to left child# and a pointer to right childclass Node: def __init__(self, key): self.data = key self.left = None self.right = Nonedef isLeaf(node): if node.left == None and node.right == None: return True return Falsedef addLeftBound(root, res): # Go left left and no left then right but again check from left root = root.left while(root is not None): if isLeaf(root) is not True: res.append(root.data) if(root.left is not None): root = root.left else: root = root.rightdef addRightBound(root, res): # Go right right and no right then left but again check from right root = root.right # As we need the reverse of this for Anticlockwise # refer above picture for better understanding stk = [] while(root is not None): if isLeaf(root) is not True: stk.append(root.data) if root.right is not None: root = root.right else: root = root.left while(len(stk) != 0): res.append(stk.pop(-1)) # its kind of preorderdef addLeaves(root, res): if root is None: return if isLeaf(root) is True: res.append(root.data) # just store leaf nodes return addLeaves(root.left, res) addLeaves(root.right, res)def boundary(root, res): # Your code here if root is None: return if isLeaf(root) is not True: res.append(root.data) # if leaf then its done by addLeaf addLeftBound(root, res) addLeaves(root, res) addRightBound(root, res)if __name__ == '__main__': root = Node(20) root.left = Node(8) root.left.left = Node(4) root.left.right = Node(12) root.left.right.left = Node(10) root.left.right.right = Node(14) root.right = Node(22) root.right.right = Node(25) res = [] boundary(root, res) for i in res: print(i)# This code is contributed by Yash Agarwal(yashagarwal2852002) |
C#
// C# program to print boundary traversal of binary treeusing System;using System.Collections.Generic;public class BinaryTree { class Node { public int data; public Node left, right; public Node(int val) { this.data = val; this.left = null; this.right = null; } } static bool isLeaf(Node node) { if (node.left == null && node.right == null) { return true; } return false; } static void addLeftBound(Node root, List<int> ans) { // Go left left and no left then right but again // check from left root = root.left; while (root != null) { if (!isLeaf(root)) ans.Add(root.data); if (root.left != null) root = root.left; else root = root.right; } } static void addRightBound(Node root, List<int> ans) { // Go right right and no right then left but again // check from right root = root.right; Stack<int> stk = new Stack<int>(); while (root != null) { if (!isLeaf(root)) stk.Push(root.data); if (root.right != null) root = root.right; else root = root.left; } while (stk.Count != 0) { ans.Add(stk.Peek()); stk.Pop(); } } static void addLeaves(Node root, List<int> ans) { if (root == null) return; if (isLeaf(root)) { ans.Add(root.data); return; } addLeaves(root.left, ans); addLeaves(root.right, ans); } static void boundary(Node root, List<int> ans) { if (root == null) return; if (!isLeaf(root)) ans.Add(root.data); // if leaf then its done by // addLeaf addLeftBound(root, ans); addLeaves(root, ans); addRightBound(root, ans); } static public void Main() { Node root = new Node(20); root.left = new Node(8); root.left.left = new Node(4); root.left.right = new Node(12); root.left.right.left = new Node(10); root.left.right.right = new Node(14); root.right = new Node(22); root.right.right = new Node(25); List<int> ans = new List<int>(); boundary(root, ans); foreach(var i in ans) { Console.Write(i + " "); } }}// This code is contributed by Yash// Agarwal(yashagarwal2852002) |
Javascript
// JavaScript Program for the above approachclass Node{ constructor(data){ this.data = data; this.left = null; this.right = null; }}function isLeaf(node){ if(node.left == null && node.right == null) return true; return false;}function addLeftBound(root, ans){ // Go left left and not left then right but again check from left root = root.left; while(root){ if(!isLeaf(root)) ans.push(root.data); if(root.left) root = root.left; else root = root.right; }}function addRightBound(root, ans){ // Go right right and no right then left but again check from right root = root.right; // As we need the reverse of this for Anticlockwise // refer above picture for better understanding let stk = []; while(root){ if(!isLeaf(root)) stk.push(root.data); if(root.right) root = root.right; else root = root.left; } while(stk.length != 0){ ans.push(stk.pop()); }}// its kind of preorderfunction addLeaves(root, ans){ if(root == null) return; if(isLeaf(root)){ ans.push(root.data); // just store leaf nodes return; } addLeaves(root.left, ans); addLeaves(root.right, ans);}function boundary(root){ // Your Code here let ans = []; if(root == null) return ans; if(!isLeaf(root)) ans.push(root.data); // if leaf then its done by addLeaf addLeftBound(root,ans); addLeaves(root,ans); addRightBound(root,ans); return ans;}// Let us construct the tree given in the above diagramlet root = new Node(20);root.left = new Node(8);root.left.left = new Node(4);root.left.right = new Node(12);root.left.right.left = new Node(10);root.left.right.right = new Node(14);root.right = new Node(22);root.right.right = new Node(25);let ans = boundary(root);for(let i = 0; i < ans.length; i++){ console.log(ans[i] + " ");}// this code is contributed by Yash Agarwal(yashagarwal2852002) |
Output
20 8 4 10 14 25 22
Time Complexity: O(n) where n is the number of nodes in binary tree.
Auxiliary Space: O(n)
Using Morris Traversal:
The basic idea behind the Morris traversal approach is to traverse a binary tree in a way that does not use any extra space other than the tree itself.
The approach uses the fact that each node in a binary tree has a maximum of two pointers, which can be used to traverse the tree in a specific manner without using any extra space. Specifically, we can modify the structure of the tree itself in a way that allows us to traverse it without using any extra space.
Follow the steps below to implement above idea:
- Initialize the current node as the root of the tree.
- While the current node is not null:
a. If the current node has no left child, print its data and move to its right child.
b. If the current node has a left child:
i. Find the rightmost node in the left subtree of the current node. This node is the inorder predecessor of the current node.
ii. If the right child of the inorder predecessor is null, set it to the current node and move to the left child of the current node.
iii. If the right child of the inorder predecessor is not null (i.e., it points back to the current node), set it to null and print the data of the current node. Then move to the right child of the current node.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Definition of a binary tree nodestruct Node { int data; Node *left, *right;};// Function to create a new binary tree nodeNode* newNode(int data){ Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp;}// Function to print the left boundary nodes of a binary// treevoid printLeftBoundary(Node* root){ while (root) { if (root->left || root->right) { cout << root->data << " "; } if (root->left) { root = root->left; } else { root = root->right; } }}// Function to print the right boundary nodes of a binary// treevoid printRightBoundary(Node* root){ if (!root) { return; } Node* curr = root->right; while (curr) { if (curr->left || curr->right) { cout << curr->data << " "; } if (curr->right) { curr = curr->right; } else { curr = curr->left; } }}// Function to print the leaves of a binary treevoid printLeaves(Node* root){ if (!root) { return; } printLeaves(root->left); if (!root->left && !root->right) { cout << root->data << " "; } printLeaves(root->right);}// Function to print the boundary nodes of a binary tree in// anticlockwise ordervoid printBoundary(Node* root){ if (!root) { return; } cout << root->data << " "; printLeftBoundary(root->left); printLeaves(root->left); printLeaves(root->right); printRightBoundary(root);}// Driver codeint main(){ // Creating the binary tree Node* root = newNode(20); root->left = newNode(8); root->left->left = newNode(4); root->left->right = newNode(12); root->left->right->left = newNode(10); root->left->right->right = newNode(14); root->right = newNode(22); root->right->right = newNode(25); // Printing the boundary nodes of the binary tree printBoundary(root); return 0;}// This code is contributed by Veerendra_Singh_Rajpoot |
Java
// Java code to implement the above approachimport java.util.*;// Definition of a binary tree nodeclass Node { int data; Node left, right; // Constructor to create a new binary tree node Node(int data) { this.data = data; this.left = this.right = null; }}class BinaryTree { // Function to print the left boundary nodes of a binary tree static void printLeftBoundary(Node root) { if (root == null) { return; } if (root.left != null || root.right != null) { System.out.print(root.data + " "); } if (root.left != null) { printLeftBoundary(root.left); } else { printLeftBoundary(root.right); } } // Function to print the right boundary nodes of a binary tree static void printRightBoundary(Node root) { if (root == null) { return; } if (root.right != null) { printRightBoundary(root.right); } else { printRightBoundary(root.left); } if (root.left != null || root.right != null) { System.out.print(root.data + " "); } } // Function to print the leaves of a binary tree static void printLeaves(Node root) { if (root == null) { return; } printLeaves(root.left); if (root.left == null && root.right == null) { System.out.print(root.data + " "); } printLeaves(root.right); } // Function to print the boundary nodes of a binary tree in anticlockwise order static void printBoundary(Node root) { if (root == null) { return; } System.out.print(root.data + " "); printLeftBoundary(root.left); printLeaves(root.left); printLeaves(root.right); printRightBoundary(root.right); } // Driver code public static void main(String[] args) { // Creating the binary tree Node root = new Node(20); root.left = new Node(8); root.left.left = new Node(4); root.left.right = new Node(12); root.left.right.left = new Node(10); root.left.right.right = new Node(14); root.right = new Node(22); root.right.right = new Node(25); // Printing the boundary nodes of the binary tree printBoundary(root); }} |
Python3
# Definition of a binary tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# Function to print the left boundary nodes of a binary treedef printLeftBoundary(root): while root: if root.left or root.right: print(root.data, end=" ") if root.left: root = root.left else: root = root.right# Function to print the right boundary nodes of a binary treedef printRightBoundary(root): if not root: return curr = root.right while curr: if curr.left or curr.right: print(curr.data, end=" ") if curr.right: curr = curr.right else: curr = curr.left# Function to print the leaves of a binary treedef printLeaves(root): if not root: return printLeaves(root.left) if not root.left and not root.right: print(root.data, end=" ") printLeaves(root.right)# Function to print the boundary nodes of a binary tree in anticlockwise orderdef printBoundary(root): if not root: return print(root.data, end=" ") printLeftBoundary(root.left) printLeaves(root.left) printLeaves(root.right) printRightBoundary(root)# Driver codeif __name__ == '__main__': # Creating the binary tree root = Node(20) root.left = Node(8) root.left.left = Node(4) root.left.right = Node(12) root.left.right.left = Node(10) root.left.right.right = Node(14) root.right = Node(22) root.right.right = Node(25) # Printing the boundary nodes of the binary tree printBoundary(root) |
C#
// C# code to implement the above approachusing System;// Definition of a binary tree nodepublic class Node { public int data; public Node left, right; // Constructor public Node(int data) { this.data = data; this.left = this.right = null; }}public class GFG { // Function to print the left boundary nodes of a binary // tree static void PrintLeftBoundary(Node root) { while (root != null) { if (root.left != null || root.right != null) { Console.Write(root.data + " "); } if (root.left != null) { root = root.left; } else { root = root.right; } } } // Function to print the right boundary nodes of a // binary tree static void PrintRightBoundary(Node root) { if (root == null) { return; } Node curr = root.right; while (curr != null) { if (curr.left != null || curr.right != null) { Console.Write(curr.data + " "); } if (curr.right != null) { curr = curr.right; } else { curr = curr.left; } } } // Function to print the leaves of a binary tree static void PrintLeaves(Node root) { if (root == null) { return; } PrintLeaves(root.left); if (root.left == null && root.right == null) { Console.Write(root.data + " "); } PrintLeaves(root.right); } // Function to print the boundary nodes of a binary tree // in anticlockwise order static void PrintBoundary(Node root) { if (root == null) { return; } Console.Write(root.data + " "); PrintLeftBoundary(root.left); PrintLeaves(root.left); PrintLeaves(root.right); PrintRightBoundary(root); } // Driver code public static void Main() { // Creating the binary tree Node root = new Node(20); root.left = new Node(8); root.left.left = new Node(4); root.left.right = new Node(12); root.left.right.left = new Node(10); root.left.right.right = new Node(14); root.right = new Node(22); root.right.right = new Node(25); // Printing the boundary nodes of the binary tree PrintBoundary(root); }} |
Javascript
// JavaScript implementation of the approach// Definition of a binary tree nodeclass Node { constructor(data) { this.data = data; this.left = null; this.right = null; }}// Function to print the left boundary nodes of a binary treefunction printLeftBoundary(root) { while (root) { if (root.left || root.right) { console.log(root.data + " "); } root = root.left ? root.left : root.right; }}// Function to print the right boundary nodes of a binary treefunction printRightBoundary(root) { if (!root) { return; } let curr = root.right; while (curr) { if (curr.left || curr.right) { console.log(curr.data + " "); } curr = curr.right ? curr.right : curr.left; }}// Function to print the leaves of a binary treefunction printLeaves(root) { if (!root) { return; } printLeaves(root.left); if (!root.left && !root.right) { console.log(root.data + " "); } printLeaves(root.right);}// Function to print the boundary nodes of a binary tree in anticlockwise orderfunction printBoundary(root) { if (!root) { return; } console.log(root.data + " "); printLeftBoundary(root.left); printLeaves(root.left); printLeaves(root.right); printRightBoundary(root);}// Driver code// Creating the binary treeconst root = new Node(20);root.left = new Node(8);root.left.left = new Node(4);root.left.right = new Node(12);root.left.right.left = new Node(10);root.left.right.right = new Node(14);root.right = new Node(22);root.right.right = new Node(25);// Printing the boundary nodes of the binary treeprintBoundary(root);// by phasing17 |
Output
20 8 4 10 14 25 22
Time complexity: O(n), where n is the number of nodes in the binary tree.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
