Boundary Traversal of Binary Tree

Problem Statement

A binary tree will be given in the problem and we need to find the boundary traversal of that binary tree.
Boundary traversal of a binary tree means traversing the binary tree along the boundary. The boundary includes the left boundary, right boundary and leaf nodes. Therefore in the boundary traversal of binary trees we will first include the left boundary then leaf nodes and then right boundary.

Important Terms in Boundary Traversal of Binary Tree

In order to solve the above problem we need to know certain terms like:

• The left boundary is the path from the root to the left most node.
• Right boundary is the path from the root to the right most node.
• Leftmost node is a leaf node that we can reach by traversing the left subtree first everytime, if it exists. If there is no left subtree then we go to the right subtree. This we do until we reach the leaf node. This leaf node is known as the rightmost node.
• Similarly we can get the rightmost most node by traversing the right subtree in the above given manner.

Example

Input

Output

1, 7, 2, 5, 11, 5, 9, 9

Example Explanation

We need to find the boundary traversal of binary tree given above, we will do it in following manner:

• Visit root (1)
• Path to leftmost node (7,2)
• Leafs nodes (5,11,5)
• Path to rightmost node (9,9)

Thus the boundary traversal of the binary tree becomes : ( 1, 7, 2, 5, 11, 5, 9, 9)

Constraints

• $ 1 <= n <=$ $10^5$
• $-10^4$ <= node.val $<= 10^4$

Approach 1: Traversing the Boundary in Three Parts: Left Boundary, Leaf Nodes, and Right Boundary

The approach to find the boundary traversal of binary tree is simple and can be done by following these three steps :

• Traverse the left boundary in a top down manner, that is we start from the root and then we go towards the leaf node. In this step we keep traversing the tree until we reach the leftmost node.
• Then we traverse all the leaf nodes from left to right. That is, from the leftmost node we move towards the right and only print the leaf nodes.
• Lastly we traverse the right boundary in a bottom up manner, that is we start from the rightmost node and go towards the root node by following the right boundary path.

Code for Boundary Traversal of Binary Tree

Let’s look into the code of boundary traversal of a binary tree.
We will create the given below binary tree in the code and then we will find its boundary traversal.

C++ Code implementation

#include <iostream>
using namespace std;


struct Node{
    int data;
    Node *left, *right;

    Node(int data){
        this->data = data;
        this->left = this->right = nullptr;
    }

public:
    bool checkLeaf(){
        return this->left == nullptr && this->right == nullptr;
    }
};


void LeftBoundary(Node* root){
    if (!root)
        return;

    Node* node = root;

    while (!node->checkLeaf()){
        cout << node->data << ' ';
        node = (node->left) ? node->left: node->right;
    }
}

void RightBoundary(Node* root){
    if (!root || root->checkLeaf()) {
        return;
    }
    RightBoundary(root->right ? root->right: root->left);
    cout << root->data << ' ';
}

void printLeafNodes(Node* root){
    if (root == nullptr) {
        return;
    }

    printLeafNodes(root->left);

    if (root->checkLeaf()) {
        cout << root->data << ' ';
    }

    printLeafNodes(root->right);
}

void BoundaryTraversal(Node* root){
    if (root == nullptr) {
        return;
    }
    cout << root->data << ' ';
    LeftBoundary(root->left);

    if (!root->checkLeaf()) {
        printLeafNodes(root);
    }
    RightBoundary(root->right);
}

int main(){
    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);

    BoundaryTraversal(root);
    return 0;
}

Java Code Implementation

class Node
{
    int data;
    Node left, right;

    Node(int data){
        this.data = data;
        this.left = this.right = null;
    }

    boolean checkLeaf() {
        return this.left == null && this.right == null;
    }
}

class Main{
    public static void LeftBoundary(Node root){
        if (root == null) {
            return;
        }

        Node node = root;

        while (!node.checkLeaf()){
            System.out.print(node.data + " ");
            node = (node.left != null) ? node.left: node.right;
        }
    }

    public static void RightBoundary(Node root){
        if (root == null || root.checkLeaf()) {
            return;
        }

        RightBoundary(root.right != null ? root.right: root.left);

        System.out.print(root.data + " ");
    }

    public static void printLeaf(Node root){

        if (root == null) {
            return;
        }


        printLeaf(root.left);


        if (root.checkLeaf()) {
            System.out.print(root.data + " ");
        }

        printLeaf(root.right);
    }


    public static void BoundaryTraversal(Node root){
        if (root == null) {
            return;
        }


        System.out.print(root.data + " ");

        LeftBoundary(root.left);


        if (!root.checkLeaf()) {
            printLeaf(root);
        }

        RightBoundary(root.right);
    }

    public static void main(String[] args){

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

        BoundaryTraversal(root);
    }
}

Python Code Implementation

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def areLeaf(self):
        return self.left is None and self.right is None

def LeftBoundary(root):
    if root is None:
        return

    node = root

    while not node.areLeaf():
        print(node.val, end=' ')
        node = node.left if node.left else node.right


def RightBoundary(root):
    if root is None or root.areLeaf():
        return

    RightBoundary(root.right if root.right else root.left)

    print(root.val, end=' ')


def LeafNodes(root):
    if root is None:
        return
    LeafNodes(root.left)

    if root.areLeaf():
        print(root.val, end=' ')
    LeafNodes(root.right)


def BoundaryTraversal(root):
    if root is None:
        return
    print(root.val, end=' ')

    LeftBoundary(root.left)

    if not root.areLeaf():
        LeafNodes(root)

    RightBoundary(root.right)


if __name__ == '__main__':

    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)

    BoundaryTraversal(root)

Output :

1 2 4 8 12 13 10 6 14 11 7 3

As discussed above, we will find boundary traversal of binary tree in three steps:

The left boundary in top down manner that is,
1,2,4,8
The leaf nodes from left to right that is,
12,13,10,6, 14
And finally the right boundary in bottom up manner , that is,
11,7,3

Thus the final output for boundary traversal of binary tree is:
1 2 4 8 12 13 10 6 14 11 7 3

Time complexity: O(n), n is the number of nodes in the tree. Since we are traversing each node at most once thus the worst case time complexity in this case would be the time taken to traverse each node once.

Space Complexity: O(h), h is the height of a tree.Because at any time the maximum number of nodes in the recursion call stack would be the height of the tree.

Conclusion

The important things that we have discussed so far are:

• We can do boundary traversal of a binary tree in three simple steps: traverse left boundary, traverse the leaf nodes and traverse right boundary.
• Left boundary is the path from root to the leftmost node.
• Right boundary is the path from root to the rightmost node.
• Leftmost node is the leaf node of the left boundary.
• Rightmost node is the leaf node of the right boundary.
• We need to take care that the same nodes are not printed multiple times.
• The time complexity is O(n) where n is the number of nodes and space complexity is O(h) where h is the height of the tree.