Why does a left-boundary node sometimes continue through its right child?

If no left child exists, the right child becomes the outermost node on that side and therefore inherits the left-boundary role.

What happens when the root is the only node in the tree?

The root is also a leaf in this case, but it must appear only once. Both approaches handle this case so that no duplicate is produced.

What happens when the root is the only node in the tree?

The root itself is also a leaf and should appear only once. Both approaches handle this case separately to avoid duplication.

Which approach is preferable in an interview?

The three-part approach is usually easier to explain and implement correctly. The single-DFS approach has the same O(N) time complexity and avoids separate boundary traversals, but its boundary-flag propagation requires more careful handling.

Boundary Traversal of a Binary Tree

Given the root of a binary tree, return its boundary traversal in anti-clockwise order, starting from the root.

The boundary consists of:

The root node.
The left boundary, excluding leaf nodes.
All leaf nodes from left to right.
The right boundary, excluding leaf nodes, added in reverse order.

Each node must appear only once in the traversal.

Example 1

Input: root = [1, 2, 3, 4, 5, 6, 7]

Output: [1, 2, 4, 5, 6, 7, 3]

Explanation: The root 1 is added first. The left boundary contributes 2, the leaf nodes from left to right are 4, 5, 6, 7, and the right boundary contributes 3 in bottom-up order.

Example 2

Input: root = [1, 2, 3, null, 4, 5, null]

Output: [1, 2, 4, 5, 3]

Explanation: Node 2 belongs to the left boundary, leaves 4 and 5 are added from left to right, and node 3 forms the right boundary. Leaf nodes are not repeated in the side boundaries.

Practice it by yourself before moving onto the solutionTry now

Approach 1

The anti-clockwise boundary can naturally be divided into three sections after the root:

Left Boundary → Leaf Nodes → Reversed Right Boundary

Different traversal rules are required for these sections.

For the left boundary, the outermost nodes are followed from top to bottom by preferring the left child. If a left child is unavailable, the right child is followed instead. Leaf nodes are excluded because they are collected separately.

For the right boundary, the outermost nodes are similarly followed by preferring the right child. However, these nodes are discovered from top to bottom while the required boundary order is bottom to top. Therefore, a temporary array called rightBoundary is used. It stores the right-boundary nodes during downward traversal so that they can later be added in reverse order.

Leaf nodes are collected separately through DFS from left to right. By excluding leaves from both side boundaries, every node is guaranteed to appear only once.

Algorithm

An empty result is returned when the tree is empty. The root is added separately when it is not a leaf so that it is not duplicated during leaf collection.
Starting from root.left, the left boundary is followed by preferring the left child and using the right child only when the left child is absent. Only non-leaf nodes are added because leaf nodes are handled separately.
A DFS traversal of the complete tree is performed so that all leaf nodes are collected from left to right.
Starting from root.right, the right boundary is followed by preferring the right child and using the left child when the right child is absent. Non-leaf nodes are stored in the temporary rightBoundary array as they are encountered from top to bottom.
The values stored in rightBoundary are then appended in reverse order so that the right boundary appears from bottom to top and the anti-clockwise traversal is completed.

Dry Run

Boundary Traversal Appraoch 1 Dry Run.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  // Checks whether a node
  // has no children.
  bool isLeaf(TreeNode* node) {
      return node != nullptr
          && node->left == nullptr
          && node->right == nullptr;
  }
25
  // Adds non-leaf nodes from the
  // left boundary in top-down order.
  void addLeftBoundary(
      TreeNode* root,
      vector<int>& boundary
  ) {
      TreeNode* current = root->left;
33
      // The outermost available child
      // continues the left boundary.
      while (current != nullptr) {
          // Leaves are collected separately,
          // so they are skipped here.
          if (!isLeaf(current)) {
              boundary.push_back(current->val);
          }
42
          if (current->left != nullptr) {
              current = current->left;
          } else {
              current = current->right;
          }
      }
  }
50
  // Collects all leaf nodes
  // from left to right.
  void addLeaves(
      TreeNode* node,
      vector<int>& boundary
  ) {
      if (node == nullptr) {
          return;
      }
60
      // A leaf belongs directly
      // to the leaf section.
      if (isLeaf(node)) {
          boundary.push_back(node->val);
          return;
      }
67
      addLeaves(node->left, boundary);
      addLeaves(node->right, boundary);
  }
71
  // Adds the right boundary
  // in required bottom-up order.
  void addRightBoundary(
      TreeNode* root,
      vector<int>& boundary
  ) {
      TreeNode* current = root->right;
      vector<int> rightBoundary;
80
      // rightBoundary stores nodes top-down.
      // They are reversed for bottom-up order.
      while (current != nullptr) {
          // Leaves are collected separately,
          // so they are skipped here.
          if (!isLeaf(current)) {
              rightBoundary.push_back(current->val);
          }
89
          if (current->right != nullptr) {
              current = current->right;
          } else {
              current = current->left;
          }
      }
96
      // Reverse traversal places the
      // right boundary from bottom to top.
      for (
          int i = rightBoundary.size() - 1;
          i >= 0;
          i--
      ) {
          boundary.push_back(rightBoundary[i]);
      }
  }
107
108public:
  // Returns the anti-clockwise
  // boundary traversal of the tree.
  vector<int> boundaryTraversal(TreeNode* root) {
      if (root == nullptr) {
          return {};
      }
115
      vector<int> boundary;
117
      // A non-leaf root is added here.
      // A single-node root is added as a leaf.
      if (!isLeaf(root)) {

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the binary tree. The boundary and leaf traversals together process every node only a constant number of times.

Space Complexity: O(H), excluding the output array, where H is the height of the binary tree. The recursive leaf traversal can use up to O(H) call-stack space, and the temporary rightBoundary array can also contain up to O(H) nodes.

Approach 2

The three boundary sections can also be generated during a single DFS by carrying information about whether the current node belongs to the outer left or right boundary.

Two boolean variables are used for this purpose:

isLeftBoundary indicates whether the current node lies on the outer left boundary of the remaining subtree. Such a node must be added before its descendants because the left boundary is required from top to bottom.
isRightBoundary indicates whether the current node lies on the outer right boundary. Such a node must be added after its descendants because the right boundary is required from bottom to top.

These flags are propagated carefully. When a node belongs to the left boundary, its left child continues that boundary whenever it exists; otherwise, the right child becomes the new outermost left-boundary node. The opposite rule is applied for isRightBoundary.

Leaf nodes are handled separately inside the same DFS. Once a leaf is added, processing of that node is completed immediately so that it cannot also be inserted as a left- or right-boundary node.

Algorithm

An empty result is returned when root is null. The root is added first, and processing is completed immediately when it is the only node.
DFS is started on root.left with isLeftBoundary = true and on root.right with isRightBoundary = true, so the outer boundary roles of both sides are identified from the beginning.
When a leaf node is reached, its value is added immediately and that call is completed so that the same node cannot be added again as a side-boundary node.
A node marked by isLeftBoundary is added before its children are processed, because the left boundary must appear from top to bottom.
The boundary flags are propagated according to the outermost available child: the left-boundary role is passed to the left child when possible and otherwise to the right child, while the symmetric rule is applied to the right-boundary role.
A node marked by isRightBoundary is added only after its children have been processed, causing right-boundary nodes to appear automatically in bottom-up order.

Dry Run

Boundary Traversal Appraoch 2 Dry Run.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  // Checks whether a node
  // has no children.
  bool isLeaf(TreeNode* node) {
      return node != nullptr
          && node->left == nullptr
          && node->right == nullptr;
  }
25
  // Builds the complete boundary
  // using boundary-role flags.
  void dfs(
      TreeNode* node,
      bool isLeftBoundary,
      bool isRightBoundary,
      vector<int>& boundary
  ) {
      if (node == nullptr) {
          return;
      }
37
      // Leaves are added exactly once
      // and need no boundary-role handling.
      if (isLeaf(node)) {
          boundary.push_back(node->val);
          return;
      }
44
      // Left-boundary nodes are added before
      // descendants for top-down order.
      if (isLeftBoundary) {
          boundary.push_back(node->val);
      }
50
      // A missing left child makes the
      // right child continue the left boundary.
      bool leftChildIsLeftBoundary =
          isLeftBoundary;
55
      bool rightChildIsLeftBoundary =
          isLeftBoundary
          && node->left == nullptr;
59
      // A missing right child makes the
      // left child continue the right boundary.
      bool leftChildIsRightBoundary =
          isRightBoundary
          && node->right == nullptr;
65
      bool rightChildIsRightBoundary =
          isRightBoundary;
68
      dfs(
          node->left,
          leftChildIsLeftBoundary,
          leftChildIsRightBoundary,
          boundary
      );
75
      dfs(
          node->right,
          rightChildIsLeftBoundary,
          rightChildIsRightBoundary,
          boundary
      );
82
      // Right-boundary nodes are added after
      // recursion for bottom-up order.
      if (isRightBoundary) {
          boundary.push_back(node->val);
      }
  }
89
90public:
  // Returns the anti-clockwise
  // boundary using a single DFS.
  vector<int> boundaryTraversal(TreeNode* root) {
      if (root == nullptr) {
          return {};
      }
97
      // A single-node tree contains
      // only one boundary node.
      if (isLeaf(root)) {
          return {root->val};
      }
103
      vector<int> boundary;
      boundary.push_back(root->val);
106
      dfs(
          root->left,
          true,
          false,
          boundary
      );
113
      dfs(
          root->right,
          false,
          true,
          boundary
      );
120

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node is processed once during the DFS traversal.

Space Complexity: O(H), excluding the output array, where H is the height of the binary tree. The recursion stack stores at most one root-to-leaf path at a time. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Interview follow-up Questions

Leaf nodes are collected separately from left to right. Excluding them from the side boundaries prevents the same node from appearing more than once.

Boundary Traversal of a Binary Tree

Example 1

Example 2

Approach 1

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Parent and Distance - Introduction

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree

Boundary Traversal of a Binary Tree

Example 1

Example 2

Approach 1

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Why are leaf nodes excluded from the left and right boundaries?

Why does a left-boundary node sometimes continue through its right child?

What happens when the root is the only node in the tree?

What happens when the root is the only node in the tree?

Which approach is preferable in an interview?

Read Similar Blogs

Parent and Distance - Introduction

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree