Boundary Traversal of Binary Tree

Dec 18, 2024 • 5 mins read

Dhaval Trivedi

Co-founder, Airtribe

Problem Overview

The problem at hand is LeetCode 545, "Boundary of Binary Tree." This problem involves a binary tree, and the task is to return the values of its boundary in a specific order. The boundary is defined as the sequence of nodes visible from outside the binary tree when viewed from the left to the right in a counter-clockwise direction.

Understanding the Problem

To solve this problem, we need to understand what constitutes the "boundary" of a binary tree. The boundary includes:

The root node.
The left boundary — the path from the root to the left-most node.
The leaves — nodes with no children, collected from left to right.
The right boundary — the path from the root to the right-most node (excluding the root if already considered).

Constraints:

All values in the nodes are unique.

We need to traverse the tree in a manner that collects these nodes in the specified order. It is important to handle edge cases such as trees with only left or only right subtrees.

Key DSA Concepts and Theory

Binary Tree

A binary tree is a tree data structure where each node has at most two children, termed as the left child and the right child.

Tree Traversal

In tree data structures, traversal refers to the process of visiting each node in the tree. There are several types of tree traversal methods like Inorder, Preorder, Postorder, and Level-order traversal, which are used based on the requirement.

Depth-First Search (DFS)

Depth-First Search is a graph traversal technique used for traversing or searching tree or graph data structures. The algorithm starts at the root and explores as deep as possible along each branch before backtracking.

Solution Approach

The solution to the problem involves a three-step DFS approach to collect nodes for each part of the boundary.

Step by Step Solution

Traverse the Left Boundary:
- Start from the root and iterate the left children. Stop if a leaf is reached and skip leaves in this path.
Collect the Leaves:
- Perform DFS to collect leaf nodes, starting from the root. Add them to the boundary list.
Traverse the Right Boundary:
- Start from the root and iterate the right children, storing them in a transient structure, and finally add to the result in reverse order to maintain the correct sequence.

C++ and Java Code Solution

C++ Code

#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        if (!root) return {};
        vector<int> boundary;
        if (!isLeaf(root)) boundary.push_back(root->val);
        
        addLeftBoundary(root->left, boundary);
        addLeaves(root, boundary);
        addRightBoundary(root->right, boundary);
        
        return boundary;
    }
    
private:
    bool isLeaf(TreeNode* node) {
        return !node->left && !node->right;
    }
    
    void addLeftBoundary(TreeNode* node, vector<int>& boundary) {
        while (node) {
            if (!isLeaf(node)) boundary.push_back(node->val);
            node = node->left ? node->left : node->right;
        }
    }
    
    void addRightBoundary(TreeNode* node, vector<int>& boundary) {
        vector<int> temp;
        while (node) {
            if (!isLeaf(node)) temp.push_back(node->val);
            node = node->right ? node->right : node->left;
        }
        for (int i = temp.size() - 1; i >= 0; --i) {
            boundary.push_back(temp[i]);
        }
    }
    
    void addLeaves(TreeNode* node, vector<int>& boundary) {
        if (isLeaf(node)) {
            boundary.push_back(node->val);
            return;
        }
        if (node->left) addLeaves(node->left, boundary);
        if (node->right) addLeaves(node->right, boundary);
    }
};

Java Code

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> boundary = new ArrayList<>();
        if (root == null) return boundary;
        if (!isLeaf(root)) boundary.add(root.val);
        
        addLeftBoundary(root.left, boundary);
        addLeaves(root, boundary);
        addRightBoundary(root.right, boundary);
        
        return boundary;
    }
    
    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }
    
    private void addLeftBoundary(TreeNode node, List<Integer> boundary) {
        while (node != null) {
            if (!isLeaf(node)) boundary.add(node.val);
            node = node.left != null ? node.left : node.right;
        }
    }
    
    private void addRightBoundary(TreeNode node, List<Integer> boundary) {
        LinkedList<Integer> temp = new LinkedList<>();
        while (node != null) {
            if (!isLeaf(node)) temp.addFirst(node.val);
            node = node.right != null ? node.right : node.left;
        }
        boundary.addAll(temp);
    }
    
    private void addLeaves(TreeNode node, List<Integer> boundary) {
        if (isLeaf(node)) {
            boundary.add(node.val);
            return;
        }
        if (node.left != null) addLeaves(node.left, boundary);
        if (node.right != null) addLeaves(node.right, boundary);
    }
}

Time and Space Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the tree.
- Each node is visited exactly once, i.e., first in the left boundary, leaves collection, or right boundary.
Space Complexity: O(N) for storing the boundary list.
- Auxiliary recursion stack space can also go up to O(H), where H is the height of the tree.

Common Mistakes to Avoid

Incorrect Leaf Handling: Ensure that non-leaf nodes at the left and right boundaries are not included as leaves.
Boundary Order: Be cautious with the order of right boundary nodes. They need to be added in reverse.
Root Check: Ensure the root is not redundantly added if it is already included in left or right boundary processing.

Additional Resources and References

Introduction to Binary Trees: GeeksforGeeks - Binary Tree
Depth-First Search Explanation: Wikipedia - Depth-First Search
Tree Traversal Methods: Topcoder - Tree Traversals

This article guides you through understanding and solving the Boundary of Binary Tree problem using efficient algorithms and clean implementations in both C++ and Java.