Open In App

Boundary Traversal of binary tree

Last Updated : 24 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Given a binary tree, print boundary nodes of the binary tree Anti-Clockwise starting from the root.

Boundary-Traversal-of-Binary-Tree--banner

 The boundary includes 

  1. left boundary (nodes on left excluding leaf nodes)
  2. leaves (consist of only the leaf nodes)
  3. 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. 

We break the problem in 3 parts: 

  • Print the left boundary in top-down manner. 
  • Print all leaf nodes from left to right, which can again be sub-divided into two sub-parts: 
    • Print all leaf nodes of left sub-tree from left to right. 
    • Print all leaf nodes of right subtree from left to right. 
  • 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 child
and a pointer to right child */
struct Node {
    int data;
    struct Node *left, *right;
};

// Utility function to create a new tree node
Node* 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 tree
void 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 manner
void 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 manner
void 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
// tree
void 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 functions
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);

    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 child
and a pointer to right child */
struct node {
    int data;
    struct node *left, *right;
};

// A simple function to print leaf nodes of a binary tree
void 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 manner
void 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 manner
void 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 tree
void 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 node
struct 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 functions
int 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 child
and 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);
    }
}
Python 
# Python3 program for binary traversal of binary tree

# A binary tree node
class 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 Tree
def 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 manner
def 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 manner
def 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 tree
def 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 function
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)
printBoundary(root)

# This code is contributed by 
# Nikhil Kumar Singh(nickzuck_007)
C# 
// C# program to print boundary traversal
// of binary tree
using 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:

  1. Right Boundary – Go Right Right until no Right. Dont Include Leaf nodes. (as it leads to duplication)
  2. Left Boundary – Go Left Left until no Left. Dont Include Leaf nodes. (as it leads to duplication)
  3. Leaf Boundary – Do inorder/preorder, if leaf node add to the List.
  4. 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 child
and a pointer to right child */
struct Node {
    int data;
    struct Node *left, *right;
};
 
// Utility function to create a new tree node
Node* 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 preorder
void 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 tree

import java.io.*;
import java.util.*;

class BinaryTree {
    Node root;
    /* A binary tree node has data, pointer to left child
and 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
Python 
# Python program to print boundary traversal of binary tree

# A binary tree node has data, pointer to left child
# and a pointer to right child
class Node:
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None


def isLeaf(node):
    if node.left == None and node.right == None:
        return True
    return False


def 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.right


def 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 preorder
def 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 tree

using 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 approach
class 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 preorder
function 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 diagram
let 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 node
struct Node {
    int data;
    Node *left, *right;
};

// Function to create a new binary tree node
Node* 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
// tree
void 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
// tree
void 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 tree
void 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 order
void printBoundary(Node* root)
{
    if (!root) {
        return;
    }
    cout << root->data << " ";
    printLeftBoundary(root->left);
    printLeaves(root->left);
    printLeaves(root->right);
    printRightBoundary(root);
}

// Driver code
int 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 approach
import java.util.*;

// Definition of a binary tree node
class 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);
    }
}
Python 
# Definition of a binary tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function to print the left boundary nodes of a binary tree


def 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 tree


def 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 tree


def 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 order


def printBoundary(root):
    if not root:
        return
    print(root.data, end=" ")
    printLeftBoundary(root.left)
    printLeaves(root.left)
    printLeaves(root.right)
    printRightBoundary(root)


# Driver code
if __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 approach

using System;

// Definition of a binary tree node
public 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 node
class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

// Function to print the left boundary nodes of a binary tree
function 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 tree
function 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 tree
function 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 order
function 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 tree
const 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);


// 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)



https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
Improve
Previous Article
Diagonal Traversal of Binary Tree
Next Article
Calculate depth of a full Binary tree from Preorder

Similar Reads

Iterative Boundary Traversal of Complete Binary tree
Given a complete binary tree, traverse it such that all the boundary nodes are visited in Anti-Clockwise order starting from the root. Example: Input: 18 / \ 15 30 / \ / \ 40 50 100 20 Output: 18 15 40 50 100 20 30 Approach: Traverse left-most nodes of the tree from top to down. (Left boundary)Traverse bottom-most level of the tree from left to rig
9 min read
Boundary Level order traversal of a Binary Tree
Given a Binary Tree, the task is to print all levels of this tree in Boundary Level order traversal. Boundary Level order traversal: In this traversal, the first element of the level (starting boundary) is printed first, followed by last element (ending boundary). Then the process is repeated for the second and last-second element, till the complet
11 min read
Boundary Root to Leaf Path traversal of a Binary Tree
Given a Binary Tree, the task is to print all Root to Leaf path of this tree in Boundary Root to Leaf path traversal. Boundary Root to Leaf Path Traversal: In this traversal, the first Root to Leaf path(Left boundary) is printed first, followed by the last Root to Leaf path (Right boundary) in Reverse order. Then the process is repeated for the sec
15+ min read
Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree
Given two arrays that represent Preorder traversals of a full binary tree and its mirror tree, we need to write a program to construct the binary tree using these two Preorder traversals.A Full Binary Tree is a binary tree where every node has either 0 or 2 children. Note: It is not possible to construct a general binary tree using these two traver
12 min read
Level order traversal of Binary Tree using Morris Traversal
Given a binary tree, the task is to traverse the Binary Tree in level order fashion.Examples: Input: 1 / \ 2 3 Output: 1 2 3 Input: 5 / \ 2 3 \ 6 Output: 5 2 3 6 Approach: The idea is to use Morris Preorder Traversal to traverse the tree in level order traversal.Observations: There are mainly two observations for the traversal of the tree using Mor
11 min read
Pre Order, Post Order and In Order traversal of a Binary Tree in one traversal | (Using recursion)
Given a binary tree, the task is to print all the nodes of the binary tree in Pre-order, Post-order, and In-order in one iteration. Examples: Input: Output: Pre Order: 1 2 4 5 3 6 7 Post Order: 4 5 2 6 7 3 1 In Order: 4 2 5 1 6 3 7 Input: Output: Pre Order: 1 2 4 8 12 5 9 3 6 7 10 11 Post Order: 12 8 4 9 5 2 6 10 11 7 3 1 In Order: 8 12 4 2 9 5 1 6
9 min read
Check if a binary tree is subtree of another binary tree using preorder traversal : Iterative
Given two binary trees S and T, the task is the check that if S is a subtree of the Tree T. For Example: Input: Tree T - 1 / \ 2 3 / \ / \ 4 5 6 7 Tree S - 2 / \ 4 5 Output: YES Explanation: The above tree is the subtree of the tree T, Hence the output is YES Approach: The idea is to traverse both the tree in Pre-order Traversal and check for each
11 min read
Sum of all the Boundary Nodes of a Binary Tree
Given a binary tree, the task is to print the sum of all the boundary nodes of the tree. Examples: Input: 1 / \ 2 3 / \ / \ 4 5 6 7 Output: 28 Input: 1 / \ 2 3 \ / 4 5 \ 6 / \ 7 8 Output: 36 Approach: We have already discussed the Boundary Traversal of a Binary tree. Here we will find the sum of the boundary nodes of the given binary tree in four s
10 min read
Given level order traversal of a Binary Tree, check if the Tree is a Min-Heap
Given the level order traversal of a Complete Binary Tree, determine whether the Binary Tree is a valid Min-Heap Examples: Input : level = [10, 15, 14, 25, 30] Output : True The tree of the given level order traversal is 10 / \ 15 14 / \ 25 30 We see that each parent has a value less than its child, and hence satisfies the min-heap property Input :
6 min read
Complexity of different operations in Binary tree, Binary Search Tree and AVL tree
In this article, we will discuss the complexity of different operations in binary trees including BST and AVL trees. Before understanding this article, you should have a basic idea about Binary Tree, Binary Search Tree, and AVL Tree. The main operations in a binary tree are: search, insert and delete. We will see the worst-case time complexity of t
4 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox