Boundary Traversal of binary tree

Last Updated : 16 Dec, 2024

Try it on GfG Practice

Given a binary tree, the task is to find the boundary nodes of the binary tree Anti-Clockwise starting from the root.

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

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 we could reach when you always firstly travel to the left subtree if it exists. If not, travel to the right subtree. Repeat until we reach a leaf node.
The right-most node is also defined in the same way with left and right exchanged.

Table of Content

Using Recursion – O(n) Time and O(n) Space

The idea is to traverse the boundary of the binary tree in three parts: left boundary (excluding leaf nodes), all leaf nodes, and right boundary (excluding leaf nodes but added in reverse order). By combining these parts, we achieve the desired boundary traversal. Each part is collected using recursive functions for left boundary, leaf nodes, and right boundary traversal.

C++

// C++ implementation for Boundary 
// Traversal of Binary Tree using recursion
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int x) {
        data = x;
        left = right = nullptr;
    }
};

// Function to collect leaf nodes
void collectLeaves(Node* root,
                    vector<int>& result) {
  
    if (root == nullptr) {
        return;
    }

    collectLeaves(root->left, result);

    // If it's a leaf node, add to result
    if (root->left == nullptr && 
        root->right == nullptr) {
        result.push_back(root->data);
    }

    collectLeaves(root->right, result);
}

// Function to collect left boundary nodes
// (top-down order)
void collectBoundaryLeft(Node* root, 
                         vector<int>& result) {
    if (root == nullptr) {
        return;
    }

    if (root->left) {
        result.push_back(root->data);
        collectBoundaryLeft(root->left, result);
    }
    else if (root->right) {
        result.push_back(root->data);
        collectBoundaryLeft(root->right, result);
    }
}

// Function to collect right boundary nodes
// (bottom-up order)
void collectBoundaryRight(Node* root, 
                          vector<int>& result) {
    if (root == nullptr) {
        return;
    }

    if (root->right) {
        collectBoundaryRight(root->right, result);
        result.push_back(root->data);  
    } 
    else if (root->left) {
        collectBoundaryRight(root->left, result);
        result.push_back(root->data);
    }
}

// Function to perform boundary traversal
vector<int> getBoundary(Node* root) {
    vector<int> result;

    if (root == nullptr) {
        return result;
    }

    // Add root data
    result.push_back(root->data);

    // Collect left boundary
    collectBoundaryLeft(root->left, result);

    // Collect leaf nodes
    collectLeaves(root->left, result);
    collectLeaves(root->right, result);

    // Collect right boundary
    vector<int> rightBoundary;
    collectBoundaryRight(root->right, rightBoundary);
    result.insert(result.end(), 
                  rightBoundary.begin(), 
                  rightBoundary.end());

    return result;
}


int main() {
  
    // Hardcoded Binary tree
    //        20
    //       /  \
    //      8    22
    //     / \     \
    //    4   12    25
    //       /  \
    //      10   14
    Node* root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    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->right = new Node(25);

    vector<int> boundary = getBoundary(root);
    for (int x : boundary) {
        cout << x << " ";
    }

    return 0;
}

Java

// Java implementation for Boundary 
// Traversal of Binary Tree using recursion
import java.util.*;

class Node {
    int data;
    Node left, right;

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

class GfG {

    // Function to collect leaf nodes
    static void collectLeaves(Node root,
                              List<Integer> result) {
        if (root == null) {
            return;
        }

        collectLeaves(root.left, result);

        // If it's a leaf node, add to result
        if (root.left == null && 
            root.right == null) {
            result.add(root.data);
        }

        collectLeaves(root.right, result);
    }

    // Function to collect left boundary nodes
    // (top-down order)
    static void collectBoundaryLeft(Node root, 
                                    List<Integer> result) {
        if (root == null) {
            return;
        }

        if (root.left != null) {
            result.add(root.data);
            collectBoundaryLeft(root.left, result);
        } 
        else if (root.right != null) {
            result.add(root.data);
            collectBoundaryLeft(root.right, result);
        }
    }

    // Function to collect right boundary nodes
    // (bottom-up order)
    static void collectBoundaryRight(Node root, 
                                     List<Integer> result) {
        if (root == null) {
            return;
        }

        if (root.right != null) {
            collectBoundaryRight(root.right, result);
            result.add(root.data);
        } else if (root.left != null) {
            collectBoundaryRight(root.left, result);
            result.add(root.data);
        }
    }

    // Function to perform boundary traversal
    static List<Integer> getBoundary(Node root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        // Add root data
        result.add(root.data);

        // Collect left boundary
        collectBoundaryLeft(root.left, result);

        // Collect leaf nodes
        collectLeaves(root.left, result);
        collectLeaves(root.right, result);

        // Collect right boundary
        List<Integer> rightBoundary = new ArrayList<>();
        collectBoundaryRight(root.right, rightBoundary);
        result.addAll(rightBoundary);

        return result;
    }

    public static void main(String[] args) {
      
        // Representing the tree as:
        //         20
        //        /  \
        //       8    22
        //      / \     \
        //     4   12    25
        //        /  \
        //       10   14
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        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.right = new Node(25);
      
        List<Integer> boundary = getBoundary(root);

        for (int x : boundary) {
            System.out.print(x + " ");
        }
    }
}

Python

# Python implementation for Boundary 
# Traversal of Binary Tree using recursion
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None


# Function to collect leaf nodes
def collectLeaves(root, result):
    if root is None:
        return

    collectLeaves(root.left, result)

    # If it's a leaf node, add to result
    if root.left is None and root.right is None:
        result.append(root.data)

    collectLeaves(root.right, result)


# Function to collect left boundary nodes
# (top-down order)
def collectBoundaryLeft(root, result):
    if root is None:
        return

    if root.left:
        result.append(root.data)
        collectBoundaryLeft(root.left, result)
    elif root.right:
        result.append(root.data)
        collectBoundaryLeft(root.right, result)


# Function to collect right boundary nodes
# (bottom-up order)
def collectBoundaryRight(root, result):
    if root is None:
        return

    if root.right:
        collectBoundaryRight(root.right, result)
        result.append(root.data)
    elif root.left:
        collectBoundaryRight(root.left, result)
        result.append(root.data)


# Function to perform boundary traversal
def getBoundary(root):
    result = []

    if root is None:
        return result

    # Add root data
    result.append(root.data)

    # Collect left boundary
    collectBoundaryLeft(root.left, result)

    # Collect leaf nodes
    collectLeaves(root.left, result)
    collectLeaves(root.right, result)

    # Collect right boundary
    rightBoundary = []
    collectBoundaryRight(root.right, rightBoundary)
    result.extend(rightBoundary)

    return result


if __name__ == "__main__":
  
    # Hardcoded Binary tree
    #        20
    #       /  \
    #      8    22
    #     / \     \
    #    4   12    25
    #       /  \
    #      10   14
    root = Node(20)
    root.left = Node(8)
    root.right = Node(22)
    root.left.left = Node(4)
    root.left.right = Node(12)
    root.left.right.left = Node(10)
    root.left.right.right = Node(14)
    root.right.right = Node(25)

    boundary = getBoundary(root)

    for x in boundary:
        print(x, end=" ")

C#

// C# implementation for Boundary 
// Traversal of Binary Tree using recursion
using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = right = null;
    }
}

class GfG {

    // Function to collect leaf nodes
    static void CollectLeaves(Node root, 
                                   List<int> result) {
        if (root == null) {
            return;
        }

        CollectLeaves(root.left, result);

        // If it's a leaf node, add to result
        if (root.left == null &&
            root.right == null) {
            result.Add(root.data);
        }

        CollectLeaves(root.right, result);
    }

    // Function to collect left boundary nodes
    // (top-down order)
    static void CollectBoundaryLeft(Node root,
                                      List<int> result) {
        if (root == null) {
            return;
        }

        if (root.left != null) {
            result.Add(root.data);
            CollectBoundaryLeft(root.left, result);
        } 
        else if (root.right != null) {
            result.Add(root.data);
            CollectBoundaryLeft(root.right, result);
        }
    }

    // Function to collect right boundary nodes
    // (bottom-up order)
    static void CollectBoundaryRight(Node root,
                                      List<int> result) {
        if (root == null) {
            return;
        }

        if (root.right != null) {
            CollectBoundaryRight(root.right, result);
            result.Add(root.data);
        } else if (root.left != null) {
            CollectBoundaryRight(root.left, result);
            result.Add(root.data);
        }
    }

    // Function to perform boundary traversal
    static List<int> GetBoundary(Node root) {
        List<int> result = new List<int>();

        if (root == null) {
            return result;
        }

        // Add root data
        result.Add(root.data);

        // Collect left boundary
        CollectBoundaryLeft(root.left, result);

        // Collect leaf nodes
        CollectLeaves(root.left, result);
        CollectLeaves(root.right, result);

        // Collect right boundary
        List<int> rightBoundary = new List<int>();
        CollectBoundaryRight(root.right, rightBoundary);
        result.AddRange(rightBoundary);

        return result;
    }

    static void Main(string[] args) {
      
        // Representing the tree as:
        //         20
        //        /  \
        //       8    22
        //      / \     \
        //     4   12    25
        //        /  \
        //       10   14
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        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.right = new Node(25);

        List<int> boundary = GetBoundary(root);

        foreach (int x in boundary) {
            Console.Write(x + " ");
        }
    }
}

JavaScript

// JavaScript implementation for Boundary 
// Traversal of Binary Tree using recursion
class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

// Function to collect leaf nodes
function collectLeaves(root, result) {
    if (root === null) {
        return;
    }

    collectLeaves(root.left, result);

    // If it's a leaf node, add to result
    if (root.left === null && root.right === null) {
        result.push(root.data);
    }

    collectLeaves(root.right, result);
}

// Function to collect left boundary nodes
// (top-down order)
function collectBoundaryLeft(root, result) {
    if (root === null) {
        return;
    }

    if (root.left) {
        result.push(root.data);
        collectBoundaryLeft(root.left, result);
    } else if (root.right) {
        result.push(root.data);
        collectBoundaryLeft(root.right, result);
    }
}

// Function to collect right boundary nodes
// (bottom-up order)
function collectBoundaryRight(root, result) {
    if (root === null) {
        return;
    }

    if (root.right) {
        collectBoundaryRight(root.right, result);
        result.push(root.data);
    } else if (root.left) {
        collectBoundaryRight(root.left, result);
        result.push(root.data);
    }
}

// Function to perform boundary traversal
function getBoundary(root) {
    const result = [];

    if (root === null) {
        return result;
    }

    // Add root data
    result.push(root.data);

    // Collect left boundary
    collectBoundaryLeft(root.left, result);

    // Collect leaf nodes
    collectLeaves(root.left, result);
    collectLeaves(root.right, result);

    // Collect right boundary
    const rightBoundary = [];
    collectBoundaryRight(root.right, rightBoundary);
    result.push(...rightBoundary);

    return result;
}


// Hardcoded Binary tree
//        20
//       /  \
//      8    22
//     / \     \
//    4   12    25
//       /  \
//      10   14
const root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
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.right = new Node(25);

const boundary = getBoundary(root);
console.log(boundary.join(" "));

Output

20 8 4 10 14 25 22

Time Complexity: O(n), where n is the number of nodes in tree.
Auxiliary Space: O(n), for the recursion stack space and storing the result.

Using Iteration – O(n) Time and O(n) Space

The iterative approach collects the boundary of a binary tree by traversing its three parts: left boundary (in top-down order), all leaf nodes, and right boundary (in bottom-up order). Each part is handled iteratively using loops and a stack to ensure efficient traversal without recursion.

C++

// C++ implementation for Iterative Boundary 
// Traversal of Binary Tree
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int x) {
        data = x;
        left = right = nullptr;
    }
};

// Function to collect leaf nodes iteratively
void collectLeaves(Node* root, 
                   vector<int>& result) {
  
    if (!root) return;

    stack<Node*> stk;
    stk.push(root);

    while (!stk.empty()) {
        Node* curr = stk.top();
        stk.pop();

        // Check if it is a leaf node
        if (!curr->left && !curr->right) {
            result.push_back(curr->data);
        }

        // Push children to the stack
        if (curr->right) stk.push(curr->right);
        if (curr->left) stk.push(curr->left);
    }
}

// Function to collect left boundary 
// nodes iteratively
void collectBoundaryLeft(Node* root,
                         vector<int>& result) {
    Node* curr = root;

    while (curr) {
      
        // Add current node to result if it is not a leaf
        if (curr->left || curr->right) {
            result.push_back(curr->data);
        }

        // Move to the next left boundary node
        if (curr->left) {
            curr = curr->left;
        } 
        else {
            curr = curr->right;
        }
    }
}

// Function to collect right boundary 
// nodes iteratively
void collectBoundaryRight(Node* root, 
                          vector<int>& result) {
    vector<int> temp;
    Node* curr = root;

    while (curr) {
      
        // Add current node to temporary
        // result if it is not a leaf
        if (curr->left || curr->right) {
            temp.push_back(curr->data);
        }

        // Move to the next right boundary node
        if (curr->right) {
            curr = curr->right;
        } else {
            curr = curr->left;
        }
    }

    // Add right boundary nodes in reverse order
    result.insert(result.end(), 
                  temp.rbegin(), temp.rend());
}

// Function to perform boundary traversal
vector<int> getBoundary(Node* root) {
    vector<int> result;

    if (!root) return result;

    // Add root data
    result.push_back(root->data);

    // Collect left boundary
    collectBoundaryLeft(root->left, result);

    // Collect leaf nodes
    collectLeaves(root->left, result);
    collectLeaves(root->right, result);

    // Collect right boundary
    collectBoundaryRight(root->right, result);

    return result;
}

int main() {
  
    // Hardcoded Binary tree
    //        20
    //       /  \
    //      8    22
    //     / \     \
    //    4   12    25
    //       /  \
    //      10   14
    Node* root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    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->right = new Node(25);

    vector<int> boundary = getBoundary(root);

    for (int x : boundary) {
        cout << x << " ";
    }

    return 0;
}

Java

// Java implementation for Iterative Boundary 
// Traversal of Binary Tree
import java.util.*;

class Node {
    int data;
    Node left, right;

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

class GfG {

    // Function to collect leaf nodes iteratively
    static void collectLeaves(Node root, 
                              List<Integer> result) {

        if (root == null) return;

        Stack<Node> stk = new Stack<>();
        stk.push(root);

        while (!stk.isEmpty()) {
            Node curr = stk.pop();

            // Check if it is a leaf node
            if (curr.left == null && curr.right == null) {
                result.add(curr.data);
            }

            // Push children to the stack
            if (curr.right != null) stk.push(curr.right);
            if (curr.left != null) stk.push(curr.left);
        }
    }

    // Function to collect left boundary 
    // nodes iteratively
    static void collectBoundaryLeft(Node root,
                                   List<Integer> result) {
        Node curr = root;

        while (curr != null) {

            // Add current node to result if it is not a leaf
            if (curr.left != null 
                       || curr.right != null) {
              
                result.add(curr.data);
            }

            // Move to the next left boundary node
            if (curr.left != null) {
                curr = curr.left;
            } 
            else {
                curr = curr.right;
            }
        }
    }

    // Function to collect right boundary 
    // nodes iteratively
    static void collectBoundaryRight(Node root,
                                     List<Integer> result) {
      
        List<Integer> temp = new ArrayList<>();
        Node curr = root;

        while (curr != null) {

            // Add current node to temporary
            // result if it is not a leaf
            if (curr.left != null || curr.right != null) {
                temp.add(curr.data);
            }

            // Move to the next right boundary node
            if (curr.right != null) {
                curr = curr.right;
            } else {
                curr = curr.left;
            }
        }

        // Add right boundary nodes in reverse order
        for (int i = temp.size() - 1; i >= 0; i--) {
            result.add(temp.get(i));
        }
    }

    // Function to perform boundary traversal
    static List<Integer> getBoundary(Node root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) return result;

        // Add root data
        result.add(root.data);

        // Collect left boundary
        collectBoundaryLeft(root.left, result);

        // Collect leaf nodes
        collectLeaves(root.left, result);
        collectLeaves(root.right, result);

        // Collect right boundary
        collectBoundaryRight(root.right, result);

        return result;
    }


    public static void main(String[] args) {

        // Hardcoded Binary tree
        //        20
        //       /  \
        //      8    22
        //     / \     \
        //    4   12    25
        //       /  \
        //      10   14
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        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.right = new Node(25);

        List<Integer> boundary = getBoundary(root);

        for (int x : boundary) {
            System.out.print(x + " ");
        };
    }
}

Python

# Python implementation for Iterative Boundary 
# Traversal of Binary Tree
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

# Function to collect leaf nodes iteratively
def collectLeaves(root, result):
    if not root:
        return

    stk = [root]

    while stk:
        curr = stk.pop()

        # Check if it is a leaf node
        if not curr.left and not curr.right:
            result.append(curr.data)

        # Push children to the stack
        if curr.right:
            stk.append(curr.right)
        if curr.left:
            stk.append(curr.left)

# Function to collect left boundary 
# nodes iteratively
def collectBoundaryLeft(root, result):
    curr = root

    while curr:

        # Add current node to result if it is not a leaf
        if curr.left or curr.right:
            result.append(curr.data)

        # Move to the next left boundary node
        if curr.left:
            curr = curr.left
        else:
            curr = curr.right

# Function to collect right boundary 
# nodes iteratively
def collectBoundaryRight(root, result):
    temp = []
    curr = root

    while curr:

        # Add current node to temporary
        # result if it is not a leaf
        if curr.left or curr.right:
            temp.append(curr.data)

        # Move to the next right boundary node
        if curr.right:
            curr = curr.right
        else:
            curr = curr.left

    # Add right boundary nodes in reverse order
    result.extend(temp[::-1])

# Function to perform boundary traversal
def getBoundary(root):
    result = []

    if not root:
        return result

    # Add root data
    result.append(root.data)

    # Collect left boundary
    collectBoundaryLeft(root.left, result)

    # Collect leaf nodes
    collectLeaves(root.left, result)
    collectLeaves(root.right, result)

    # Collect right boundary
    collectBoundaryRight(root.right, result)

    return result


if __name__ == "__main__":

    # Hardcoded Binary tree
    #        20
    #       /  \
    #      8    22
    #     / \     \
    #    4   12    25
    #       /  \
    #      10   14
    root = Node(20)
    root.left = Node(8)
    root.right = Node(22)
    root.left.left = Node(4)
    root.left.right = Node(12)
    root.left.right.left = Node(10)
    root.left.right.right = Node(14)
    root.right.right = Node(25)

    boundary = getBoundary(root)

    print(" ".join(map(str, boundary)))

C#

// C# implementation for Iterative Boundary 
// Traversal of Binary Tree
using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = right = null;
    }
}

class GfG {

    // Function to collect leaf nodes iteratively
    static void CollectLeaves(Node root,
                                     List<int> result) {

        if (root == null) return;

        Stack<Node> stk = new Stack<Node>();
        stk.Push(root);

        while (stk.Count > 0) {
            Node curr = stk.Pop();

            // Check if it is a leaf node
            if (curr.left == null && curr.right == null) {
                result.Add(curr.data);
            }

            // Push children to the stack
            if (curr.right != null) stk.Push(curr.right);
            if (curr.left != null) stk.Push(curr.left);
        }
    }

    // Function to collect left boundary 
    // nodes iteratively
    static void CollectBoundaryLeft(Node root, 
                                        List<int> result) {
        Node curr = root;

        while (curr != null) {

            // Add current node to result if it is not a leaf
            if (curr.left != null || curr.right != null) {
                result.Add(curr.data);
            }

            // Move to the next left boundary node
            if (curr.left != null) {
                curr = curr.left;
            } 
            else {
                curr = curr.right;
            }
        }
    }

    // Function to collect right boundary 
    // nodes iteratively
    static void CollectBoundaryRight(Node root,
                                           List<int> result) {
        List<int> temp = new List<int>();
        Node curr = root;

        while (curr != null) {

            // Add current node to temporary
            // result if it is not a leaf
            if (curr.left != null || curr.right != null) {
                temp.Add(curr.data);
            }

            // Move to the next right boundary node
            if (curr.right != null) {
                curr = curr.right;
            } else {
                curr = curr.left;
            }
        }

        // Add right boundary nodes in reverse order
        for (int i = temp.Count - 1; i >= 0; i--) {
            result.Add(temp[i]);
        }
    }

    // Function to perform boundary traversal
    static List<int> GetBoundary(Node root) {
        List<int> result = new List<int>();

        if (root == null) return result;

        // Add root data
        result.Add(root.data);

        // Collect left boundary
        CollectBoundaryLeft(root.left, result);

        // Collect leaf nodes
        CollectLeaves(root.left, result);
        CollectLeaves(root.right, result);

        // Collect right boundary
        CollectBoundaryRight(root.right, result);

        return result;
    }

    static void Main(string[] args) {

        // Hardcoded Binary tree
        //        20
        //       /  \
        //      8    22
        //     / \     \
        //    4   12    25
        //       /  \
        //      10   14
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        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.right = new Node(25);
        List<int> boundary = GetBoundary(root);
        foreach (int x in boundary) {
            Console.Write(x + " ");
        }
    }
}

JavaScript

// JavaScript implementation for Iterative Boundary 
// Traversal of Binary Tree
class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

// Function to collect leaf nodes iteratively
function collectLeaves(root, result) {
    if (!root) return;

    const stk = [root];

    while (stk.length > 0) {
        const curr = stk.pop();

        // Check if it is a leaf node
        if (!curr.left && !curr.right) {
            result.push(curr.data);
        }

        // Push children to the stack
        if (curr.right) stk.push(curr.right);
        if (curr.left) stk.push(curr.left);
    }
}

// Function to collect left boundary nodes iteratively
function collectBoundaryLeft(root, result) {
    let curr = root;

    while (curr) {
    
        // Add current node to result if it is not a leaf
        if (curr.left || curr.right) {
            result.push(curr.data);
        }

        // Move to the next left boundary node
        if (curr.left) {
            curr = curr.left;
        } 
        else {
            curr = curr.right;
        }
    }
}

// Function to collect right boundary nodes iteratively
function collectBoundaryRight(root, result) {
    const temp = [];
    let curr = root;

    while (curr) {
    
        // Add current node to temporary result 
        // if it is not a leaf
        if (curr.left || curr.right) {
            temp.push(curr.data);
        }

        // Move to the next right boundary node
        if (curr.right) {
            curr = curr.right;
        } 
        else {
            curr = curr.left;
        }
    }

    // Add right boundary nodes in reverse order
    for (let i = temp.length - 1; i >= 0; i--) {
        result.push(temp[i]);
    }
}

// Function to perform boundary traversal
function getBoundary(root) {
    const result = [];

    if (!root) return result;

    // Add root data
    result.push(root.data);

    // Collect left boundary
    collectBoundaryLeft(root.left, result);

    // Collect leaf nodes
    collectLeaves(root.left, result);
    collectLeaves(root.right, result);

    // Collect right boundary
    collectBoundaryRight(root.right, result);

    return result;
}

// Hardcoded Binary tree
//        20
//       /  \
//      8    22
//     / \     \
//    4   12    25
//       /  \
//      10   14
const root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
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.right = new Node(25);

const boundary = getBoundary(root);
console.log(boundary.join(" "));

Output

20 8 4 10 14 25 22

Using Morris Traversal – O(n) Time and O(1) Space

The 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:
If the current node has no left child, print its data and move to its right child.
If the current node has a left child:
- Find the rightmost node in the left subtree of the current node. This node is the inorder predecessor of the current node.
- 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.
- 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.

C++

// C++ implementation for Boundary Traversal of Binary Tree
// using Morris Traversal
#include <iostream>
#include <vector>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int x) {
        data = x;
        left = right = nullptr;
    }
};

// Helper function to check if a node is a leaf
bool isLeaf(Node* node) {
    return node->left == nullptr && node->right == nullptr;
}

// Function to collect the left boundary nodes
void collectBoundaryLeft(Node* root, vector<int>& result) {
    Node* curr = root;
    while (curr) {
        if (!isLeaf(curr)) {
            result.push_back(curr->data);
        }

        if (curr->left) {
            curr = curr->left;
        } else {
            curr = curr->right;
        }
    }
}

// Function to collect the leaf nodes
void collectLeaves(Node* root, vector<int>& result) {
    if (!root) {
        return;
    }
    
    if (isLeaf(root)) {
        result.push_back(root->data);
        return;
    }

    collectLeaves(root->left, result);
    collectLeaves(root->right, result);
}

// Function to collect the right boundary nodes
void collectBoundaryRight(Node* root, 
                          vector<int>& result) {
    Node* curr = root;
    vector<int> temp;
    while (curr) {
        if (!isLeaf(curr)) {
            temp.push_back(curr->data);
        }

        if (curr->right) {
            curr = curr->right;
        } else {
            curr = curr->left;
        }
    }
    for (int i = temp.size() - 1; i >= 0; --i) {
        result.push_back(temp[i]);
    }
}

// Function to perform boundary traversal
vector<int> getBoundary(Node* root) {
    vector<int> result;

    if (!root) {
        return result;
    }

    // Add root data if it's not a leaf
    if (!isLeaf(root)) {
        result.push_back(root->data);
    }

    // Collect left boundary
    collectBoundaryLeft(root->left, result);

    // Collect leaf nodes
    collectLeaves(root, result);

    // Collect right boundary
    collectBoundaryRight(root->right, result);

    return result;
}


int main() {
  
    // Hardcoded Binary tree
    //        20
    //       /  \
    //      8    22
    //     / \     \
    //    4   12    25
    //       /  \
    //      10   14
    Node* root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    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->right = new Node(25);

    vector<int> boundary = getBoundary(root);

    for (int x : boundary) {
        cout << x << " ";
    }

    return 0;
}

Java

// Java implementation for Boundary Traversal of Binary Tree
// using Morris Traversal
import java.util.*;

class Node {
    int data;
    Node left, right;

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

class GfG {

    // Helper function to check if a node is a leaf
    static boolean isLeaf(Node node) {
        return node.left == null && node.right == null;
    }

    // Function to collect the left boundary nodes
    static void collectBoundaryLeft(Node root, 
                                    List<Integer> result) {
        Node curr = root;
        while (curr != null) {
            if (!isLeaf(curr)) {
                result.add(curr.data);
            }

            if (curr.left != null) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
    }

    // Function to collect the leaf nodes
    static void collectLeaves(Node root, List<Integer> result) {
        if (root == null) {
            return;
        }

        if (isLeaf(root)) {
            result.add(root.data);
            return;
        }

        collectLeaves(root.left, result);
        collectLeaves(root.right, result);
    }

    // Function to collect the right boundary nodes
    static void collectBoundaryRight(Node root, 
                                     List<Integer> result) {
        Node curr = root;
        List<Integer> temp = new ArrayList<>();

        while (curr != null) {
            if (!isLeaf(curr)) {
                temp.add(curr.data);
            }

            if (curr.right != null) {
                curr = curr.right;
            } else {
                curr = curr.left;
            }
        }

        for (int i = temp.size() - 1; i >= 0; --i) {
            result.add(temp.get(i));
        }
    }

    // Function to perform boundary traversal
    static List<Integer> getBoundary(Node root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        // Add root data if it's not a leaf
        if (!isLeaf(root)) {
            result.add(root.data);
        }

        // Collect left boundary
        collectBoundaryLeft(root.left, result);

        // Collect leaf nodes
        collectLeaves(root, result);

        // Collect right boundary
        collectBoundaryRight(root.right, result);

        return result;
    }

    public static void main(String[] args) {

        // Hardcoded Binary tree
        //        20
        //       /  \
        //      8    22
        //     / \     \
        //    4   12    25
        //       /  \
        //      10   14
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        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.right = new Node(25);
      
        List<Integer> boundary = getBoundary(root);

        for (int x : boundary) {
            System.out.print(x + " ");
        }
    }
}

Python

# Python implementation for Boundary Traversal 
# of Binary Tree using Morris Traversal
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None


# Helper function to check if a node is a leaf
def isLeaf(node):
    return node.left is None and node.right is None


# Function to collect the left boundary nodes
def collectBoundaryLeft(root, result):
    curr = root
    while curr:
        if not isLeaf(curr):
            result.append(curr.data)

        if curr.left:
            curr = curr.left
        else:
            curr = curr.right


# Function to collect the leaf nodes
def collectLeaves(root, result):
    if not root:
        return

    if isLeaf(root):
        result.append(root.data)
        return

    collectLeaves(root.left, result)
    collectLeaves(root.right, result)


# Function to collect the right boundary nodes
def collectBoundaryRight(root, result):
    curr = root
    temp = []
    while curr:
        if not isLeaf(curr):
            temp.append(curr.data)

        if curr.right:
            curr = curr.right
        else:
            curr = curr.left

    for i in reversed(temp):
        result.append(i)


# Function to perform boundary traversal
def getBoundary(root):
    result = []

    if not root:
        return result

    # Add root data if it's not a leaf
    if not isLeaf(root):
        result.append(root.data)

    # Collect left boundary
    collectBoundaryLeft(root.left, result)

    # Collect leaf nodes
    collectLeaves(root, result)

    # Collect right boundary
    collectBoundaryRight(root.right, result)

    return result
    
if __name__ == "__main__":
  
    # Hardcoded Binary tree
    #        20
    #       /  \
    #      8    22
    #     / \     \
    #    4   12    25
    #       /  \
    #      10   14
    root = Node(20)
    root.left = Node(8)
    root.right = Node(22)
    root.left.left = Node(4)
    root.left.right = Node(12)
    root.left.right.left = Node(10)
    root.left.right.right = Node(14)
    root.right.right = Node(25)

    boundary = getBoundary(root)
    print(" ".join(map(str, boundary)))

C#

// C# implementation for Boundary Traversal of Binary Tree
// using Morris Traversal
using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = right = null;
    }
}

class GfG {

    // Helper function to check if a node is a leaf
    static bool IsLeaf(Node node) {
        return node.left == null && node.right == null;
    }

    // Function to collect the left boundary nodes
    static void CollectBoundaryLeft(Node root,
                                           List<int> result) {
        Node curr = root;
        while (curr != null) {
            if (!IsLeaf(curr)) {
                result.Add(curr.data);
            }

            if (curr.left != null) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
    }

    // Function to collect the leaf nodes
    static void CollectLeaves(Node root, 
                                     List<int> result) {
        if (root == null) {
            return;
        }

        if (IsLeaf(root)) {
            result.Add(root.data);
            return;
        }

        CollectLeaves(root.left, result);
        CollectLeaves(root.right, result);
    }

    // Function to collect the right boundary nodes
    static void CollectBoundaryRight(Node root, 
                                            List<int> result) {
        Node curr = root;
        List<int> temp = new List<int>();

        while (curr != null) {
            if (!IsLeaf(curr)) {
                temp.Add(curr.data);
            }

            if (curr.right != null) {
                curr = curr.right;
            } else {
                curr = curr.left;
            }
        }

        for (int i = temp.Count - 1; i >= 0; --i) {
            result.Add(temp[i]);
        }
    }

    // Function to perform boundary traversal
    static List<int> GetBoundary(Node root) {
        List<int> result = new List<int>();

        if (root == null) {
            return result;
        }

        // Add root data if it's not a leaf
        if (!IsLeaf(root)) {
            result.Add(root.data);
        }

        // Collect left boundary
        CollectBoundaryLeft(root.left, result);

        // Collect leaf nodes
        CollectLeaves(root, result);

        // Collect right boundary
        CollectBoundaryRight(root.right, result);

        return result;
    }

    public static void Main(string[] args) {

        // Hardcoded Binary tree
        //        20
        //       /  \
        //      8    22
        //     / \     \
        //    4   12    25
        //       /  \
        //      10   14
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        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.right = new Node(25);

        List<int> boundary = GetBoundary(root);

        foreach (int x in boundary) {
            Console.Write(x + " ");
        }
    }
}

JavaScript

// JavaScript implementation for Boundary Traversal
// of Binary Tree using Morris Traversal
class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

// Helper function to check if a node is a leaf
function isLeaf(node) {
    return !node.left && !node.right;
}

// Function to collect the left boundary nodes
function collectBoundaryLeft(root, result) {
    let curr = root;
    while (curr) {
        if (!isLeaf(curr)) {
            result.push(curr.data);
        }

        if (curr.left) {
            curr = curr.left;
        } else {
            curr = curr.right;
        }
    }
}

// Function to collect the leaf nodes
function collectLeaves(root, result) {
    if (!root) {
        return;
    }

    if (isLeaf(root)) {
        result.push(root.data);
        return;
    }

    collectLeaves(root.left, result);
    collectLeaves(root.right, result);
}

// Function to collect the right boundary nodes
function collectBoundaryRight(root, result) {
    let curr = root;
    const temp = [];
    while (curr) {
        if (!isLeaf(curr)) {
            temp.push(curr.data);
        }

        if (curr.right) {
            curr = curr.right;
        } else {
            curr = curr.left;
        }
    }

    for (let i = temp.length - 1; i >= 0; i--) {
        result.push(temp[i]);
    }
}

// Function to perform boundary traversal
function getBoundary(root) {
    const result = [];

    if (!root) {
        return result;
    }

    // Add root data if it's not a leaf
    if (!isLeaf(root)) {
        result.push(root.data);
    }

    // Collect left boundary
    collectBoundaryLeft(root.left, result);

    // Collect leaf nodes
    collectLeaves(root, result);

    // Collect right boundary
    collectBoundaryRight(root.right, result);

    return result;
}

// Hardcoded Binary tree
//        20
//       /  \
//      8    22
//     / \     \
//    4   12    25
//       /  \
//      10   14
const root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
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.right = new Node(25);

const boundary = getBoundary(root);
console.log(boundary.join(" "));

Output

20 8 4 10 14 25 22

Calculate depth of a full Binary tree from Preorder

kartik

News

Improve

Similar Reads

Binary Tree Data Structure

A Binary Tree Data Structure is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. It is commonly used in computer science for efficient storage and retrieval of data, with various operations such as insertion, deletion, and

Introduction to Binary Tree

Binary Tree is a non-linear and hierarchical data structure where each node has at most two children referred to as the left child and the right child. The topmost node in a binary tree is called the root, and the bottom-most nodes are called leaves. Representation of Binary TreeEach node in a Binar

Properties of Binary Tree

In this post, the properties of a binary tree are discussed: 1. The maximum number of nodes at level 'l' of a binary tree is 2l: Note: Here level is the number of nodes on the path from the root to the node (including root and node). The level of the root is 0 This can be proved by induction: For ro

Applications, Advantages and Disadvantages of Binary Tree

A binary tree is a tree that has at most two children for any of its nodes. There are several types of binary trees. To learn more about them please refer to the article on "Types of binary tree" Real-time applications of Binary Trees DOM in HTML.File explorerEvaluate an expressionRouting Algorithms

Binary Tree (Array implementation)

Given an array that represents a tree in such a way that array indexes are values in tree nodes and array values give the parent node of that particular index (or node). The value of the root node index would always be -1 as there is no parent for root. Construct the standard linked representation o

Maximum Depth or Height of Binary Tree

Given a binary tree, the task is to find the maximum height of the tree. The height of the tree is the number of edges in the tree from the root to the deepest node. Examples: Example 1: The height of the below binary tree is 2. Example 2: The height of the below binary tree is 3 Table of Content [E

Insertion in a Binary Tree in level order

Given a binary tree and a key, the task is to insert the key into the binary tree at the first position available in level order manner. Examples: Input: key = 12 Output: Explanation: Node with value 20 is inserted into the binary tree at the first position available in level order manner. Approach:

Deletion in a Binary Tree

Given a binary tree, the task is to delete a given node from it by making sure that the tree shrinks from the bottom (i.e. the deleted node is replaced by the bottom-most and rightmost node). This is different from BST deletion. Here we do not have any order among elements, so we replace them with t

Enumeration of Binary Trees

A Binary Tree is labeled if every node is assigned a label and a Binary Tree is unlabelled if nodes are not assigned any label. Below two are considered same unlabelled trees o o / \ / \ o o o o Below two are considered different labelled trees A C / \ / \ B C A B How many different Unlabelled Binar

Article Tags :

Practice Tags :